Example 7.1.4

Here is the adjacency matrix of a "small-world" network on 200 nodes. Each node is connected to 4 neighbors, and then some edges are randomly changed to distant connections.

The adjacency matrix for this graph reveals the connections as mostly local (i.e., the nonzeros are near the diagonal).

Example 7.1.5

We will use a test image from the well-known skimage module.

The details vary by image type, but for the most part an image is an array of color values.

The three values at each pixel are for intensities of red, green, and blue. We can convert each of those "planes" into an ordinary matrix.

The values above go from zero (no red) to one (full red). It may also be convenient to convert the image to grayscale, which has just one "layer" from zero (black) to one (white).

Example 7.2.1

The eig function from scipy.linalg will return the eigenvalues as a vector, and a matrix of associated eigenvectors.

We can check the fact that this is an EVD.

The Bauer-Fike theorem provides an upper bound on the condition number of these eigenvalues.

The theorem suggests that eigenvalue changes may be up to 7 orders of magnitude larger than a perturbation to the matrix. A few random experiments show that effects of nearly that size are not hard to observe.

Example 7.2.3

Let's start with a known set of eigenvalues and an orthogonal eigenvector basis.

Now we will take the QR factorization and just reverse the factors.

It turns out that this is a similarity transformation, so the eigenvalues are unchanged.

What's remarkable is that if we repeat the transformation many times, the process converges to D.

Example 7.3.2

We verify some of the fundamental SVD properties using the function svd from scipy.linalg.

By default, the "full" type is returned. This can be a memory hog if one of the dimensions of is very large.

Both $U$ and $V$ are orthogonal (in the complex case, unitary). Note that it's that $V^*$ is returned, not $V$.

Next we test that we have the factorization promised by the SVD. The middle matrix is diagonal with the same size as $A$.

The 2-norm and condition number are typically computed from the singular values.

The "thin" SVD form is more memory efficient.

The thin form remains an exact factorization.

Example 7.4.1

The following matrix is not hermitian.

It has an eigenvalue decomposition with a unitary matrix of eigenvectors, though, so it is normal.

The eigenvalues are pure imaginary.

The singular values are the complex magnitudes of the eigenvalues.

Example 7.4.2

We construct a real symmetric matrix with known eigenvalues by using the QR factorization to produce a random orthogonal set of eigenvectors.

The condition number of these eigenvalues is one. Thus the effect on them is bounded by the norm of the perturbation to $A.$

Example 7.4.3

We construct a symmetric matrix with a known EVD.

The Rayleigh quotient of an eigenvector is its eigenvalue.

The Rayleigh quotient's value is much closer to an eigenvalue than its input is to an eigenvector. In this experiment, each additional digit of accuracy in the eigenvector estimate gives two more digits to the eigenvalue estimate.

Example 7.5.1

We make an image from some text, then reload it as a matrix.

Next we show that the singular values decrease exponentially, until they reach zero (more precisely, are about ). For all numerical purposes, this determines the rank of the matrix.

The rapid decrease suggests that we can get fairly good low-rank approximations.

Consider how little data is needed to reconstruct these images. For rank 8, for instance, we have 8 left and right singular vectors plus 8 singular values, for a compression ratio of better than 25:1.

Example 7.5.2

This matrix describes the votes on bills in the 111th session of the United States Senate. (The data set was obtained from voteview.com.) Each row is one senator and each column is a vote item.

If we visualize the votes (white is "yea," black is "nay," and gray is anything else), we can see great similarity between many rows, reflecting party unity.

We use singular value "energy" to quantify the decay rate of the values.

The first and second singular triples contain about 58% and 17% respectively of the energy of the matrix. All others have far less effect, suggesting that the information is primarily two-dimensional. The first left and right singular vectors also contain interesting structure.

Both vectors have values greatly clustered near $\pm C$ for a $C$ constant . These can be roughly interpreted as how partisan a particular senator or bill was, and for which political party. Projecting the senators' vectors into the first two $V$-coordinates gives a particularly nice way to reduce them to two dimensions. Political scientists label these dimensions "partisanship" and "bipartisanship." Here we color them by actual party affiliation (also given in the data file): red for Republican, blue for Democrat, and yellow for independent.