Funes el memorioso

March 31, 2016

Bipartite Graph Formulation of Circulant Matrix

funes matlab

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

circulant, hadamard, matlab, octave

Comments Off

August 25, 2015

Downshift and Upshift Matrix

funes matlab

% test matrix
>> A = [1 2 3 4 5;
 6 7 8 9 10;
 11 12 13 14 15; 
 16 17 18 19 20;
 21 22 23 24 25]

A =

    1    2    3    4    5
    6    7    8    9   10
   11   12   13   14   15
   16   17   18   19   20
   21   22   23   24   25

% downshift matrix
>> D = [0 0 0 0 1; 1 0 0 0 0; 0 1 0 0 0; 0 0 1 0 0; 0 0 0 1 0]
D =

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

% downshift test
>> D*A
ans =

   21   22   23   24   25
    1    2    3    4    5
    6    7    8    9   10
   11   12   13   14   15
   16   17   18   19   20

% downshift twice
>>  D*D*A
ans =

   16   17   18   19   20
   21   22   23   24   25
    1    2    3    4    5
    6    7    8    9   10
   11   12   13   14   15

% the trace of downshift is merely upshift
>>  D'
ans =

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

% which can be verified as follows:
>> A, D'*A
A =

    1    2    3    4    5
    6    7    8    9   10
   11   12   13   14   15
   16   17   18   19   20
   21   22   23   24   25

ans =

    6    7    8    9   10
   11   12   13   14   15
   16   17   18   19   20
   21   22   23   24   25
    1    2    3    4    5

% putting the input matrix to the left of the downshift matrix.
% then it became a left-shift operation.
>> A*D
ans =

    2    3    4    5    1
    7    8    9   10    6
   12   13   14   15   11
   17   18   19   20   16
   22   23   24   25   21

%% Combining together, D'*A*D is down-and-left shift.
>> D'*A*D
A =

    1    2    3    4    5
    6    7    8    9   10
   11   12   13   14   15
   16   17   18   19   20
   21   22   23   24   25

ans =

    7    8    9   10    6
   12   13   14   15   11
   17   18   19   20   16
   22   23   24   25   21
    2    3    4    5    1

hadamard, matlab, matrix

Comments Off

July 19, 2015

Lifts, eigenvalues and Hadamard matrices

funes matlab

% positive part
>> P=[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0;
1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1;
1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0; 
1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1; 
1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1; 
1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1; 
1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0; 
1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0; 
1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0; 
1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1; 
1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0; 
1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1]; 

% negative part
>> N = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1;
0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0;
0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1;
0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0;
0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0;
0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0;
0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1;
0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1;
0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1;
0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0;
0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1;
0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0];

% zero matrix
>> Z = zeros(size(N)(1));

% an signed adjacency matrix of a complete bipartite graph
>> H = [Z, P-N; P'-N', Z];

% eigenvalues of a signed adjacency matrix
>> eig(H)
ans =

  -3.4641
  -3.4641
  -3.4641
  -3.4641
  -3.4641
  -3.4641
  -3.4641
  -3.4641
  -3.4641
  -3.4641
  -3.4641
  -3.4641
   3.4641
   3.4641
   3.4641
   3.4641
   3.4641
   3.4641
   3.4641
   3.4641
   3.4641
   3.4641
   3.4641
   3.4641

% check that it's a sqrt(12)
>> 3.4641^2
ans =  12.000

% the leading principal sub-matrix of size 12
>> A12 = eig(H(1:12, 1:12)), size(A12)
A12 =

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

ans =

   12    1

% the leading principal sub-matrix of size 13
>> A13 = eig(H(1:13, 1:13)), size(A13)
A13 =

  -3.46410
   0.00000
   0.00000
   0.00000
   0.00000
   0.00000
   0.00000
   0.00000
   0.00000
   0.00000
   0.00000
   0.00000
   3.46410

ans =

   13    1

% the leading principal sub-matrix of size 14
>> A14 = eig(H(1:14, 1:14)), size(A14)
A14 =

  -3.4641e+00
  -3.4641e+00
  -2.2869e-16
  -5.1835e-17
  -3.1072e-32
  -9.8437e-33
  -9.1270e-34
  -1.6678e-48
   6.7204e-34
   2.6380e-33
   5.5511e-17
   1.0011e-16
   3.4641e+00
   3.4641e+00

ans =

   14    1

% the leading principal sub-matrix of size 15
>> A15 = eig(H(1:15, 1:15)), size(A15)
A15 =

  -3.4641e+00
  -3.4641e+00
  -3.4641e+00
  -1.2569e-16
  -5.2487e-17
  -2.7846e-17
   8.3967e-19
   2.9178e-17
   1.3011e-16
   2.6577e-16
   6.1994e-16
   7.9764e-16
   3.4641e+00
   3.4641e+00
   3.4641e+00

ans =

   15    1

% the leading principal sub-matrix of size 16
>> A16 = eig(H(1:16, 1:16)), size(A16)
A16 =

  -3.4641e+00
  -3.4641e+00
  -3.4641e+00
  -3.4641e+00
  -4.8088e-16
  -3.2142e-16
  -1.4036e-16
   1.4234e-17
   1.1284e-16
   2.6229e-16
   4.1426e-16
   4.6066e-16
   3.4641e+00
   3.4641e+00
   3.4641e+00
   3.4641e+00

ans =

   16    1

eigenvalues, hadamard, matlab

Comments Off

August 25, 2014

Spectrum of Hadamard Graphs

funes matlab

>> A=[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0;
1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1;
1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0; 
1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1; 
1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1; 
1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1; 
1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0; 
1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0; 
1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0; 
1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1; 
1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0; 
1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1]; 

>> B = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1;
0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0;
0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1;
0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0;
0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0;
0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0;
0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1;
0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1;
0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1;
0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0;
0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1;
0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0;]

>> G = [Z A Z B;A' Z B' Z;Z B Z A;B' Z A' Z];

>> eig(G)

ans =

  -12.0000
   -3.4641
   -3.4641
   -3.4641
   -3.4641
   -3.4641
   -3.4641
   -3.4641
   -3.4641
   -3.4641
   -3.4641
   -3.4641
   -3.4641
   -0.0000
   -0.0000
   -0.0000
   -0.0000
   -0.0000
   -0.0000
   -0.0000
   -0.0000
   -0.0000
   -0.0000
    0.0000
    0.0000
    0.0000
    0.0000
    0.0000
    0.0000
    0.0000
    0.0000
    0.0000
    0.0000
    0.0000
    0.0000
    3.4641
    3.4641
    3.4641
    3.4641
    3.4641
    3.4641
    3.4641
    3.4641
    3.4641
    3.4641
    3.4641
    3.4641
   12.0000

>> % 3.4641^2 = 12

>> A = [1 1 1 1; 1 1 0 0;1 0 1 0; 1 0 0 1];
>> B = [0 0 0 0; 0 0 1 1;0 1 0 1; 0 1 1 0];

>> (A-B)*(A-B)'

ans =

     4     0     0     0
     0     4     0     0
     0     0     4     0
     0     0     0     4

>> >> G = [Z A Z B;A' Z B' Z;Z B Z A;B' Z A' Z];

>> eig(G)

ans =

   -4.0000
   -2.0000
   -2.0000
   -2.0000
   -2.0000
   -0.0000
   -0.0000
   -0.0000
    0.0000
    0.0000
    0.0000
    2.0000
    2.0000
    2.0000
    2.0000
    4.0000

hadamard, matlab

Comments Off

January 26, 2013

Matlab: Cholesky Factorization and Reordering

funes matlab

>> A=100*eye(50);A(1,2:50)=1;A(2:50,1)=1;
>> subplot(2, 2, 1);
>> spy(A, 'b.');
>> title('A');
>> subplot(2, 2, 2);
>> spy(A([2:50,1],[2:50,1]'), 'b.');
>> title('reordered A');
>> subplot(2, 2, 3);
>> spy(chol(A), 'b.');
>> title('chol(A)');
>> subplot(2, 2, 4);
>> spy(chol(A([2:50,1], [2:50,1]')), 'b.');
>> title('chol(reordered A)');

cholesky, matlab, reordering

Comments Off

Running Matlab GUI on Cyberstar

funes matlab

[you@local] ssh -X -C id@cyberstar.psu.edu
Last login: Sat Jan 26 10:16:09 2013 from *.cse.psu.edu
[you@cyberstar] module load matlab 
[you@cyberstar] module list
Currently Loaded Modulefiles:
  1) realvnc/4.5r21561   3) intel/11.1.073      5) gstreamer/0.10.32
  2) java/1.6.0_20       4) pgi/10.9            6) matlab/R2012a

forward, matlab, ssh, Xwindows

Comments Off

April 17, 2011

Spectral Graph Theory

funes Uncategorized

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>

eigenvalue, graph, matlab, octave, spectral_graph_theory

Comments Off

He told me: I have more memories in myself alone than all men have had since the world was a world.

Funes el memorioso

Tags