Funes el memorioso

% A
>> A = [1  -1  -1  -1  -1;
-1   1  -1  -1  -1;
-1  -1   1  -1  -1;
-1  -1  -1   1  -1;
-1  -1  -1  -1   1];

>> B = A;

>> C = [-1  -1   1   1  -1
-1  -1  -1   1   1
 1  -1  -1  -1   1
 1   1  -1  -1  -1
-1   1   1  -1  -1];

>> D = [-1  1  -1  -1  1;
 1  -1   1  -1  -1
-1   1  -1   1  -1;
-1  -1   1  -1   1
 1  -1  -1   1  -1];

>> [eig(A), eig(B), eig(C), eig(D)]
ans =

  -3.00000  -3.00000  -3.23607  -3.23607
   2.00000   2.00000  -3.23607  -3.23607
   2.00000   2.00000  -1.00000  -1.00000
   2.00000   2.00000   1.23607   1.23607
   2.00000   2.00000   1.23607   1.23607

>> [eig(A^2), eig(B^2), eig(C^2), eig(D^2)]
ans =

    4.00000    4.00000    1.00000    1.00000
    4.00000    4.00000    1.52786    1.52786
    4.00000    4.00000    1.52786    1.52786
    4.00000    4.00000   10.47214   10.47214
    9.00000    9.00000   10.47214   10.47214

>> eig(A^2 + B^2 + C^2+ D^2)
ans =

   20
   20
   20
   20
   20

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>