Laplacian, eigen-values and eigen-vectors

Hi,

I want to graphically display eigen-vectors and eigen-values of a matrix

I have begined with this relatively basic 3x3 matrix given at Vecteurs propres et espaces propres d'une matrice 3x3 - YouTube

-1  2  2
 2  2 -1
 2 -1  2 

Eigen-values of this matrix are 3 and -3

Eigen vectors of this matrix are

E3 =    { 1/2 , 1 , 0 } and { 1/2 , 0 , 1 }

E-3 =    { -2 , 1, 1 }    

I have used the 3x3 matrix as three 3D coordinates for to display it as a triangle :
(since this is a symetric matrix, no need to handle the row or column major order)

x0 y0 z0
x1 y1 z1
x2 y2 z2

where (x0,y0,z0), (x1,y1,z1) and (x2,y2,z2) are 3D coordinates of the triangle vertices

After I have displayed eigen-vectors as 3D vectors for to try to understand what they really represent in 3D
(for this, I display each eigen-vector as a line in a different color)

But I don’t graphically see what is the rapport between the triangle and his eigen-vectors :frowning:
(the only think that I clearly see is that eigen-vectors are orthogonals but this is all)

Here is the basic code that I actually use for to display the triangle and his eigen-vectors


#include <GL/gl.h>
#include <GL/glut.h>

float angle = 0.0f;

float angleInc = 1;

GLfloat vertices[3][3];

void SetVertice( int idx, GLfloat x, GLfloat y, GLfloat z)
{
    vertices[idx][0] = x;
    vertices[idx][1] = y;
    vertices[idx][2] = z;
}

void MakeArrays()
{
    SetVertice(0, -1,  2,  2);
    SetVertice(1,  2,  2, -1);
    SetVertice(2,  2, -1,  2); 
}

void DrawAxes()
{
    glBegin(GL_LINES);

        glColor3f( 1.0f, 0.0f, 0.0f);
        glVertex3f( 0.0f, 0.0f, 0.0f);
        glVertex3f( 1.0f, 0.0f, 0.0f);
 
        glColor3f(0.0f, 1.0f, 0.0f);
        glVertex3f( 0.0f, 0.0f, 0.0f);
        glVertex3f( 0.0f, 1.0f, 0.0f);

        glColor3f( 0.0f, 0.0f, 1.0f);
        glVertex3f( 0.0f, 0.0f, 0.0f);
        glVertex3f( 0.0f, 0.0f, 1.0f);

    glEnd();
}

void DrawHeigenVectors()
{
    glBegin(GL_LINES);

        glColor3f( 1.0f, 0.0f, 0.0f);
        glVertex3f( 0.0f, 0.0f, 0.0f);
        glVertex3f( 0.5f, 1.0f, 0.0f);
 
        glColor3f(0.0f, 1.0f, 0.0f);
        glVertex3f( 0.0f, 0.0f, 0.0f);
        glVertex3f( 0.5f, 0.0f, 1.0f);

        glColor3f( 0.0f, 0.0f, 1.0f);
        glVertex3f( 0.0f, 0.0f, 0.0f);
        glVertex3f( -2.0f, 1.0f, 1.0f);

    glEnd();
}



void DrawTriangle()
{
    int i;
    
    glColor3f(1.0f, 1.0f, 1.0f);

    glBegin(GL_TRIANGLES);

        for( i = 0 ; i < 3 ; i++)
        {
            glVertex3fv(vertices[i]);
        }

    glEnd();
}

void renderScene(void) 
{

    // Clear Color and Depth Buffers
    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

    // Reset transformations
    glLoadIdentity();

    // Set the camera
    gluLookAt(    0.0f, 0.0f, 10.0f,
            0.0f, 0.0f,  0.0f,
            0.0f, 1.0f,  0.0f);

    glRotatef(angle, 1.0f, 1.0f, 1.0f);

    // DrawAxes();
    DrawTriangle();
    DrawHeigenVectors();

    angle += angleInc;

    glutSwapBuffers();
}


void changeSize(int w, int h) 
{

    // Prevent a divide by zero, when window is too short
    // (you cant make a window of zero width).
    if (h == 0)
        h = 1;

    float ratio =  w * 1.0 / h;

    // Use the Projection Matrix
    glMatrixMode(GL_PROJECTION);

    // Reset Matrix
    glLoadIdentity();

    // Set the viewport to be the entire window
    glViewport(0, 0, w, h);

    // Set the correct perspective.
    gluPerspective(45.0f, ratio, 0.1f, 100.0f);

    // Get Back to the Modelview
    glMatrixMode(GL_MODELVIEW);
}

void keyboardFunc( unsigned char key, int x, int y )
{
    switch ( key )
      {
            case 27: // Escape key

                  exit (0);
                  break;

   
            case ' ' : // pause/play key

            if( angleInc == 0.0f )
            {
                angleInc = 1.0f;
            }
            else
            {
                angleInc = 0.0f; 
            }
            break;
        
      }

      glutPostRedisplay();
}

int main(int argc, char **argv) 
{

    // init GLUT and create window
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_DEPTH | GLUT_DOUBLE | GLUT_RGBA);
    glutInitWindowPosition(100,100);
    glutInitWindowSize(640,480);
    glutCreateWindow("Lighthouse3D- GLUT Tutorial");

    // register callbacks
    glutDisplayFunc(renderScene);
    glutReshapeFunc(changeSize);
    glutKeyboardFunc(keyboardFunc);

    MakeArrays();

    // here is the idle func registration
    glutIdleFunc(renderScene);

    // enter GLUT event processing cycle
    glutMainLoop();

    return 0;
}

I plane after to use eigen-values and eigen-vectors for to can handle the spectral compression of a 3D object via his Laplacian matrix

For example, for the very basic example of a triangle :

The Adjency matrix is :

0 1 1 
1 0 1
1 1 0 

The Degree matrix is :

2 0 0
0 2 0
0 0 2

So, the symetric Laplacian matrix Ls = D - A

2-1 -1
-1 2 -1
-1 -1 2

And the “true” Laplacian matrix is
(this seem the same but divided by 2)

  1     -1/2     -1/2
-1/2      1    -1/2
-1/2    -1/2      1

But since I don’t see the rapport between the 3D coordinates of a triangle and his eigen-vector,
it’s again more difficult to imagine what is the rapport between a Laplacian matrix and his eigen-vectors :frowning:

=> someone can help me a little to understand in more depth how I can represent eigen-values and eigen-vectors on a OpenGL 3D fashion , please ?

For to begin, I have decided to only use a 2x2 matrix for the computation of eigen-values and eigen-vectors with this very simple 2x2 matrix

4 3
-2 -3



#include <stdio.h>
#include <math.h>
#include <GL/gl.h>
#include <GL/glut.h>

float angle = 0.0f;

float angleInc = 1;

GLfloat vertices[2][2];
GLfloat EigenVectors[2][2];
GLfloat EigenValues[2];

    
void SetVertice2( int idx, GLfloat x, GLfloat y)
{
    vertices[idx][0] = x;
    vertices[idx][1] = y;
}

void ComputeVertices2()
{
    int i;

    SetVertice2(0,   4,  3);
    SetVertice2(1,  -2,  -3);

    printf("
The 2x2 matrix is 

");
    for( i = 0 ; i < 2 ; i++)
    {
        printf("	 %f %f 
", vertices[i][0], vertices[i][1] );
    }
}


void SetEigenValue( int idx, GLfloat eigenvalue)
{
    EigenValues[idx] = eigenvalue;
}

GLfloat Trace2x2( GLfloat *mat2x2)
{
    return mat2x2[0] + mat2x2[3];
}

GLfloat Det2x2( GLfloat *mat2x2)
{
    return mat2x2[0] * mat2x2[3] - mat2x2[1] * mat2x2[2];
}




void ComputeEigenValues2()
{
    int i;

    GLfloat tr =  Trace2x2( (GLfloat *) &vertices[0][0] );
    GLfloat tr2 = tr * tr;
    GLfloat det = Det2x2( (GLfloat *) &vertices[0][0] );
    GLfloat gap = sqrt( tr2 - (4.0f * det) ); 

    printf("
 tr = %f , tr2 = %f, det= %f , gap = %f 

", tr, tr2, det, gap);
    SetEigenValue(0, (tr + gap) / 2.0f);
    SetEigenValue(1, (tr - gap) / 2.0f);     
 
    printf("
Eigenvalues of this 2x2 matrix are 

");
    for( i = 0 ; i < 2 ; i++)
    {
        printf("	 %f 
", EigenValues[i]);
    }

}


void SetEigenVector2( int idx, GLfloat x, GLfloat y)
{
    EigenVectors[idx][0] = x;
    EigenVectors[idx][1] = y;
}


void ComputeEigenVectors2()
{
    int i;

    SetEigenVector2(0, 3.0f, -1.0f);
    SetEigenVector2(1, 1.0f, -2.0f);

    printf("
Eigenvectors of this 2x2 matrix are 

");
    for( i = 0 ; i < 2 ; i++)
    {
        printf("	  (%f) %f %f 
", EigenValues[i], EigenVectors[i][0], EigenVectors[i][1] );
    }

}

void MakeArrays2()
{
    ComputeVertices2();
    ComputeEigenValues2();
    ComputeEigenVectors2();
}

void DrawAxes2()
{
    glBegin(GL_LINES);

        glColor3f( 1.0f, 0.0f, 0.0f);
        glVertex3f( 0.0f, 0.0f, 0.0f);
        glVertex3f( 1.0f, 0.0f, 0.0f);
 
        glColor3f(0.0f, 1.0f, 0.0f);
        glVertex3f( 0.0f, 0.0f, 0.0f);
        glVertex3f( 0.0f, 1.0f, 0.0f);

    glEnd();
}

void DrawHeigenVectors2()
{
    glBegin(GL_LINES);

        glColor3f( 1.0f, 0.0f, 0.0f);
        glVertex3f( 0.0f, 0.0f, 0.0f);
        glVertex3fv( &EigenVectors[0][0] );
 
        glColor3f(0.0f, 1.0f, 0.0f);
        glVertex3f( 0.0f, 0.0f, 0.0f);
        glVertex3fv( &EigenVectors[1][0] );

    glEnd();
}



void DrawVertices2()
{
    int i;
    
    glColor3f(1.0f, 1.0f, 1.0f);

    glBegin(GL_LINES);

        for( i = 0 ; i < 2 ; i++)
        {
            glVertex3f(0.0f, 0.0f, 0.0f);
            glVertex3fv(vertices[i]);
        }

    glEnd();
}


void renderScene(void) 
{

    // Clear Color and Depth Buffers
    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

    // Reset transformations
    glLoadIdentity();

    // Set the camera
    gluLookAt(    0.0f, 0.0f, 10.0f,
            0.0f, 0.0f,  0.0f,
            0.0f, 1.0f,  0.0f);

    // Rotatge the scene
    glScalef(0.7f, 0.7f, 0.7f);
    glRotatef(angle, 1.0f, 1.0f, 1.0f);

    // Set the line width to 2 for to have more visibles vectors
    glLineWidth(2.0f);

    // Draw X and Y 3D vectors 
    // DrawAxes2();

    // Draw the matrix 3x3 matrix as 3x {x, y, z} vectors 
    DrawVertices2();

    // Draw eigen vector of the matrix
    DrawHeigenVectors2();

    // update the animation for the next image 
    angle += angleInc;

    // display the current image
    glutSwapBuffers();
}


void changeSize(int w, int h) 
{

    // Prevent a divide by zero, when window is too short
    // (you cant make a window of zero width).
    if (h == 0)
        h = 1;

    float ratio =  w * 1.0 / h;

    // Use the Projection Matrix
    glMatrixMode(GL_PROJECTION);

    // Reset Matrix
    glLoadIdentity();

    // Set the viewport to be the entire window
    glViewport(0, 0, w, h);

    // Set the correct perspective.
    gluPerspective(45.0f, ratio, 0.1f, 100.0f);

    // Get Back to the Modelview
    glMatrixMode(GL_MODELVIEW);
}

void keyboardFunc( unsigned char key, int x, int y )
{
    switch ( key )
      {
            case 27: // Escape key

                  exit (0);
                  break;

   
            case ' ' : // pause/play key

            if( angleInc == 0.0f )
            {
                angleInc = 1.0f;
            }
            else
            {
                angleInc = 0.0f; 
            }
            break;
        
      }

      glutPostRedisplay();
}

int main(int argc, char **argv) 
{

    // init GLUT and create window
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_DEPTH | GLUT_DOUBLE | GLUT_RGBA);
    glutInitWindowPosition(100,100);
    glutInitWindowSize(640,480);
    glutCreateWindow("Lighthouse3D- GLUT Tutorial");

    // register callbacks
    glutDisplayFunc(renderScene);
    glutReshapeFunc(changeSize);
    glutKeyboardFunc(keyboardFunc);

    MakeArrays2();

    // here is the idle func registration
    glutIdleFunc(renderScene);

    // enter GLUT event processing cycle
    glutMainLoop();

    return 0;
}


It compute eigen-values using this formula and found goods eigen-values of 3 and -2 :slight_smile:



void ComputeEigenValues2()
{
    int i;

    GLfloat tr =  Trace2x2( (GLfloat *) &vertices[0][0] );
    GLfloat tr2 = tr * tr;
    GLfloat det = Det2x2( (GLfloat *) &vertices[0][0] );
    GLfloat gap = sqrt( tr2 - (4.0f * det) ); 

    printf("
 tr = %f , tr2 = %f, det= %f , gap = %f 

", tr, tr2, det, gap);
    SetEigenValue(0, (tr + gap) / 2.0f);
    SetEigenValue(1, (tr - gap) / 2.0f);     
 
    printf("
Eigenvalues of this 2x2 matrix are 

");
    for( i = 0 ; i < 2 ; i++)
    {
        printf("	 %f 
", EigenValues[i]);
    }
}


But I don’t find the formula for to give eigen-vector at this page :frowning:
So it does not really compute eigen-vector but only set them to value given at this page, so (1, -2) for the eigenvalue -2 and (3, -1) for the eigen-value 3



void ComputeEigenVectors2()
{
    int i;

    SetEigenVector2(0, 3.0f, -1.0f);
    SetEigenVector2(1, 1.0f, -2.0f);

    printf("
Eigenvectors of this 2x2 matrix are 

");
    for( i = 0 ; i < 2 ; i++)
    {
        printf("	  (%f) %f %f 
", EigenValues[i], EigenVectors[i][0], EigenVectors[i][1] );
    }
}


The output of the first code is this :



yannoo@Aerocool ~/Dev/Vpropre $ ./eigen2

The 2x2 matrix is 

     4.000000 3.000000 
     -2.000000 -3.000000 

 tr = 1.000000 , tr2 = 1.000000, det= -6.000000 , gap = 5.000000 


Eigenvalues of this 2x2 matrix are 

     3.000000 
     -2.000000 

Eigenvectors of this 2x2 matrix are 

      (3.000000) 3.000000 -1.000000 
      (-2.000000) 1.000000 -2.000000


What is the formula that I have to use for to compute eigen-vectors of the 2x2 matrix into the ComputeEigenVectors() func in a similar way of the computation of eigen-values into the ComputeEigenValues2() function ?

The 2x2 matrix example is from Eigenvalue algorithm - Wikipedia

Having found the eigenvalues λ[sub]1[/sub] and λ[sub]2[/sub], the columns of A-λ[sub]1[/sub]I are eigenvectors for λ[sub]2[/sub] and vice-versa (eigenvectors are only unique up to a scale factor). Some of those columns may be zero vectors (or very close to them), so you’d probably choose the column with the largest magnitude (as the columns will all be scaled multiples of each other, you only need to examine one element).

But it should be noted that finding eigenvalues and eigenvectors by solving the characteristic polynomial is impractical (and numerically unstable) for larger matrices. It’s feasible for 3x3 matrices; it’s theoretically possible for 4x4, but closed-form solutions for quartic polynomials are numerically unstable.

Most approaches use an iteration which converges either to an eigenvector or to a similar matrix (which will have the same eigenvalues as the original) which is triangular (the values along the diagonal of a triangular matrix are its eigenvalues). LAPACK uses the QR algorithm.

The thing about what I think is something like to transform the original Laplacian matrix to a matrix where the diagonal are degrees values (or 1 / degree values) and where only a directed graph is represented at the top of this diagonal, cf alls values on the bottom of this diagonal are zeroes and where only somes values at the top of the diagonal are vertex to vertex indications (where -1 or -1 / degree on the original Laplacian matrix become complex or hyper-complex values into the transformed matrix)

In this case, the diagonal represent vertices degrees = eigen-values and matrix values after this degree/eigenvalue in the line “represent” (I know that is very more complex that this) the eigen-vector for the vertice concerned on this line , no ?
(I never studied eigen-values/vector before the end ot the last week, so I’m a very very … very beginner in this domain :frowning: )

But for to begin, can LAPACK to be used as a eigen-values/vectors resolver that can be used via an API inside a C/C++ OpenGL program ?
(cf. to be used instead the rigid formula that only handle 2x2 matrix inside ComputeEigenValues() and ComputeEigenVectors() calls)