[,1] [,2] [,3]
[1,] 0.74 0.49 0.07
[2,] 0.88 0.26 0.51
[3,] 0.63 0.24 0.59Matrix Eigendecomposition
The Asymmetric Matrix Case
In this lecture, we review the idea of an eigendecomposition of a square matrix. Let’s say we have the following matrix \(\mathbf{B}\) of dimensions \(3 \times 3\):
We use the R function runif (which stands for “random uniform”) to populate the matrix with random numbers in the zero to one interval.
Most matrices like this can be decomposed into two other matrices \(\mathbf{U}\) and \(\mathbf{\lambda}\), such that the following matrix multiplication equation is true:
\[ \mathbf{B} = \mathbf{U}\mathbf{\lambda}\mathbf{U}^{-1} \]
Both \(\mathbf{U}\) and \(\mathbf{\lambda}\) are of the same dimensions as the original, with \(\mathbf{U}\) having numbers in each cell and \(\mathbf{\lambda}\) being a matrix with values along the diagonals and zeros everywhere else.
The column values of \(\mathbf{U}\) are called the eigenvectors of \(\mathbf{B}\) and the diagonal values of \(\mathbf{\lambda}\) are called the eigenvalues of \(\mathbf{B}\).
In R you can find the values that yield the eigendecomposition of any square matrix (if one exists) using the function eigen.
So in our case this would be:
eigen() decomposition
$values
[1] 1.4256541 0.3195604 -0.1552145
$vectors
[,1] [,2] [,3]
[1,] -0.5148954 -0.4669390 0.4838633
[2,] -0.6388257 0.2808667 -0.8653808
[3,] -0.5716507 0.8384997 -0.1303551The function eigen returns a list with two components, one called values are the diagonal values of \(\mathbf{\lambda}\), and the other one called vectors is the eigenvector matrix \(\mathbf{U}\).
We can check that these two elements can help us reconstruct the original matrix as follows:
[,1] [,2] [,3]
[1,] 0.74 0.49 0.07
[2,] 0.88 0.26 0.51
[3,] 0.63 0.24 0.59Which are indeed the original values of \(\mathbf{B}\)!
The Symmetric Matrix Case
Now imagine that the matrix \(\mathbf{B}\) is symmetric:
[,1] [,2] [,3]
[1,] 0.74 0.88 0.63
[2,] 0.88 0.26 0.24
[3,] 0.63 0.24 0.59And let’s do the eigendecomposition of this matrix:
eigen() decomposition
$values
[1] 1.7709909 0.2757779 -0.4567688
$vectors
[,1] [,2] [,3]
[1,] -0.7200185 -0.2389854 0.6515054
[2,] -0.4963684 -0.4787344 -0.7241766
[3,] -0.4849657 0.8448073 -0.2260728The interesting thing here is that now the reconstruction equation boils down to:
\[ \mathbf{B} = \mathbf{U}\mathbf{\lambda}\mathbf{U}^T \]
Note that now we just need to post-multiply \(\mathbf{U}\mathbf{\lambda}\) by the transpose of \(\mathbf{U}\) rather than the inverse, which is a much simpler matrix operation.
We can check that this is true as follows:
[,1] [,2] [,3]
[1,] 0.74 0.88 0.63
[2,] 0.88 0.26 0.24
[3,] 0.63 0.24 0.59Which are indeed the original values of the symmetric version of \(\mathbf{B}\)!
Now, the idea is that we can perform the asymmetric or symmetric eigendecomposition with any matrix, including a network adjacency matrix or a proximity matrix derived from it.
In fact, we have already done a partial version of the matrix eigendecomposition many times before, because the reflective status game is a way to compute the first column (leading eigenvector) of the \(\mathbf{U}\) matrix for any proximity or adjacency matrix you feed into it.
Low Rank Approximation of the Original Matrix
The more important thing is that, once you have the eigendecomposition of a matrix, and the full set of eigenvectors stored in \(\mathbf{U}\), the first few columns of \(\mathbf{U}\), gives us the best low dimensional approximation of the original matrix.
For instance, in the above case, the one-dimensional (also called “rank one”) approximation of the original matrix is given by:
\[ \mathbf{B}_{1-dim} = u_1\lambda_1u_1^T \]
Where \(u\) is just the first column (eigenvector) of \(\mathbf{U}\), and \(\lambda_1\) is just the first eigenvalue.
In R we can do this approximation as follows:
[,1] [,2] [,3]
[1,] 0.92 0.63 0.62
[2,] 0.63 0.44 0.43
[3,] 0.62 0.43 0.42Which are not quite the same as the original values of \(\mathbf{B}\), but they are not wildly far off either.
If we wanted to be more accurate, however, we would use a two-dimensional approximation (rank two) and thus use more of the information:
\[ \mathbf{B}_{2-dim} = u_1\lambda_1u_1^T + u_2\lambda_2u_2^T \]
In R:
u.2 <- as.matrix(U[, 2])
B.2dim <- u.1 %*% lambda[1, 1] %*% t(u.1) + u.2 %*% lambda[2, 2] %*% t(u.2)
round(B.2dim, 2) [,1] [,2] [,3]
[1,] 0.93 0.66 0.56
[2,] 0.66 0.50 0.31
[3,] 0.56 0.31 0.61Which are not the same as the original, but are now a bit closer!
Of course, if we wanted to reconstruct the original matrix, all we have to do is add the product of the eigenvector, eigenvalue, and transpose of the eigenvector across all three dimensions of the matrix:
u.3 <- as.matrix(U[, 3])
B.3dim <-
u.1 %*% lambda[1, 1] %*% t(u.1) +
u.2 %*% lambda[2, 2] %*% t(u.2) +
u.3 %*% lambda[3, 3] %*% t(u.3)
round(B.3dim, 2) [,1] [,2] [,3]
[1,] 0.74 0.88 0.63
[2,] 0.88 0.26 0.24
[3,] 0.63 0.24 0.59Which reconstructs the original values.
So in general, if you have a symmetric square matrix \(\mathbf{B}\) of dimensions \(k \times k\), and you obtain an eigenvalue decomposition of \(\mathbf{B}\) with eigenvectors stored in the columns of \(\mathbf{U}\) and eigenvalues in \(\lambda\), then the rank-\(p\) approximation of the original matrix is given by:
\[ \mathbf{B}_{rank-p} = \sum_{m = 1}^p u_{m}\lambda_mu_m^T \]
When \(p = k\), the equation above gives you the original matrix back. When \(p<k\) you get the best guess as to what the original was, given \(p\) dimensions.