Funes el memorioso

octave:1> size = 12
size =  12

octave:2> I = eye(size)
I =

Diagonal Matrix

   1   0   0   0   0   0   0   0   0   0   0   0
   0   1   0   0   0   0   0   0   0   0   0   0
   0   0   1   0   0   0   0   0   0   0   0   0
   0   0   0   1   0   0   0   0   0   0   0   0
   0   0   0   0   1   0   0   0   0   0   0   0
   0   0   0   0   0   1   0   0   0   0   0   0
   0   0   0   0   0   0   1   0   0   0   0   0
   0   0   0   0   0   0   0   1   0   0   0   0
   0   0   0   0   0   0   0   0   1   0   0   0
   0   0   0   0   0   0   0   0   0   1   0   0
   0   0   0   0   0   0   0   0   0   0   1   0
   0   0   0   0   0   0   0   0   0   0   0   1

octave:3> A = [I(12,:) ; I(1:11,:)] % downshift permutation
A =

   0   0   0   0   0   0   0   0   0   0   0   1
   1   0   0   0   0   0   0   0   0   0   0   0
   0   1   0   0   0   0   0   0   0   0   0   0
   0   0   1   0   0   0   0   0   0   0   0   0
   0   0   0   1   0   0   0   0   0   0   0   0
   0   0   0   0   1   0   0   0   0   0   0   0
   0   0   0   0   0   1   0   0   0   0   0   0
   0   0   0   0   0   0   1   0   0   0   0   0
   0   0   0   0   0   0   0   1   0   0   0   0
   0   0   0   0   0   0   0   0   1   0   0   0
   0   0   0   0   0   0   0   0   0   1   0   0
   0   0   0   0   0   0   0   0   0   0   1   0

octave:4> Z = zeros(size, size);

octave:5> G = [Z, A; A', Z];

octave:6> eig(G)
ans =

  -1
  -1
  -1
  -1
  -1
  -1
  -1
  -1
  -1
  -1
  -1
  -1
   1
   1
   1
   1
   1
   1
   1
   1
   1
   1
   1
   1

octave:7> eig([Z, A*A; (A*A)', Z])
ans =

  -1
  -1
  -1
  -1
  -1
  -1
  -1
  -1
  -1
  -1
  -1
  -1
   1
   1
   1
   1
   1
   1
   1
   1
   1
   1
   1
   1

octave:8> eig([Z, A*A*A; (A*A*A)', Z])
ans =

  -1
  -1
  -1
  -1
  -1
  -1
  -1
  -1
  -1
  -1
  -1
  -1
   1
   1
   1
   1
   1
   1
   1
   1
   1
   1
   1
   1

octave:9> eig([Z, eye(12); eye(12)', Z])
ans =

  -1
  -1
  -1
  -1
  -1
  -1
  -1
  -1
  -1
  -1
  -1
  -1
   1
   1
   1
   1
   1
   1
   1
   1
   1
   1
   1
   1

Let G be a d-regular bipartite graph and A_G is its adjacency matrix. Prove that the eigenvalue of A_G is -d.

One example:

• Let G be a graph where the left vertices are {1,3,5} and the right vertices are {2,4,6}.
• The undirected edges are (1,2), (1,4), (3,4), (3,6), (5,1), (5,6).

octave:1> B=zeros(6,6)
B =

   0   0   0   0   0   0
   0   0   0   0   0   0
   0   0   0   0   0   0
   0   0   0   0   0   0
   0   0   0   0   0   0
   0   0   0   0   0   0

octave:2> B(1,2)=1; B(1,4)=1; B(3,4)=1; B(3,6)=1; B(5,2)=1; B(5,6)=1
B =

   0   1   0   1   0   0
   0   0   0   0   0   0
   0   0   0   1   0   1
   0   0   0   0   0   0
   0   1   0   0   0   1
   0   0   0   0   0   0

octave:3> B = B + B'
B =

   0   1   0   1   0   0
   1   0   0   0   1   0
   0   0   0   1   0   1
   1   0   1   0   0   0
   0   1   0   0   0   1
   0   0   1   0   1   0

octave:4> [EVEC, EVAL] = eig(X)
EVEC =

  -0.50000   0.65328   0.50000  -0.27060
  -0.50000   0.27060  -0.50000   0.65328
  -0.50000  -0.27060  -0.50000  -0.65328
  -0.50000  -0.65328   0.50000   0.27060

EVAL =

Diagonal Matrix

   1.7413e-16            0            0            0
            0   5.8579e-01            0            0
            0            0   2.0000e+00            0
            0            0            0   3.4142e+00

octave:5>