Eigenvectors from Eigenvalues – a NumPy implementation

I was intrigued by the recent splashy result showing how eigenvectors can be computed from eigenvalues alone. The finding was covered in Quanta magazine and the original paper is pretty easy to understand, even for a non-mathematician.

Being a non-mathematician myself, I tend to look for insights and understanding via computation, rather than strict proofs. What seems cool about the result to me is that you can compute the directions from simply the stretches (along with the stretches of the sub-matrices). It seems kind of magical (of course, it’s not 😉 ). To get a feel for it, I implemented the key identity in the paper in python and NumPy and confirmed that it gives the right answer for a random (real-valued, symmetric) matrix.

I posted the Jupyter Notebook here.

3 thoughts on “Eigenvectors from Eigenvalues – a NumPy implementation

  1. Thanks for this Corey. I was similarly intrigued by this result and was taking some time to go through it. Although I’ve not had time to go through the proof properly yet (hopefully soon) the application didn’t come to light until I went through your explanation and example. You inspired me to replicate what you did in numpy with R.

    https://scienceofdata.org/2019/11/18/eigenvectors-from-eigenvalues-application/

    It’s not as clean and efficient as your code but I think it gets the job done. Just wanted to thank you for writing this and making the result click in my brain. Keep up the excellent work.

  2. Very good post.

    The following is an R translation that may be useful for R users:

    # Academic paper proving the results
    # Ref: https://arxiv.org/pdf/1908.03795.pdf

    # Implementation in Python code by Corey Chivers
    # URL: http://predictivehealthcare.pennmedicine.org/Eigenvectors%20from%20Eigenvalues.html

    # Conversion of original Python code to R by Graham W Griffiths, Dec 2019

    # Generate a random Hermitian matrix
    n = 5
    N = n * n
    A = array(runif(N,0,1),c(n,n))
    for (i in 1:n){
    for (j in 1:n){
    A[j,i] = A[i,j]
    }
    }
    # Check if Hermitian
    print(isSymmetric(A))

    # Calculate eigenvalues using R built-in function
    r <- eigen(A)
    V <- r$vectors
    lam <- r$values

    print(lam)

    # This implementation is not meant to be optimized for computation, but
    # rather for readability. We first pre-compute the Eigenvalues of each
    # of the submatrices, We then build up the squared norms element by
    # element. Finally, we take the squareroot and compare it against the
    # Eigenvectors obtained from built-in function eigen().

    lambda_A <- lam
    lambda_M <- array(0,c(n,n-1))

    inds <- 1:n
    for (j in inds){
    idx <- inds[inds!=j] # [r for (r in 1:n) if r!=j]
    Mj <- A[idx,idx] # A[idx,:][:,idx]
    lambda_M[j,] = eigen(Mj)$values # LA.eigvals(Mj)
    }

    v_norm = array(0,c(n,n))
    for (i in inds){
    for (j in inds){
    numerator <- 1
    denominator <- 1
    for (k in 1:(n-1)){
    numerator <- numerator*(lambda_A[i] – lambda_M[j,k])
    }
    for (k in inds){
    if (k != i){
    denominator <- denominator*(lambda_A[i] – lambda_A[k])
    }
    }
    v_norm[i,j] <- numerator/denominator
    }
    }
    V_newMethod <- t(sqrt(v_norm))
    print(V_newMethod)

    print(abs(V))

    # Visual inspection suggests they are the same. Due to floating point errors,
    # confirm that the absolute difference between them is below some small error
    # tolerance.

    tol <- 1e-12
    print((V_newMethod – abs(V)) < tol)

Leave a Reply to Junaid Cancel reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s