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 the Images package for working with images. We also load here the TestImages package for a large library of well-known standard images.

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

The elements here have four values, for red, green, blue, and alpha (opacity). 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).

Finally, we can save an image locally for reloading later.

Example 7.2.1

The eigvals command will return just the eigenvalues, as a vector.

If we also want the eigenvectors (returned as the matrix $V$), we use eigen.

We can check the fact that this is an EVD.

Even if the matrix is not diagonalizable, eigen will run successfully, but the matrix ${V}$ will not be invertible.

Example 7.2.2

We will confirm the Bauer-Fike theorem on a triangular matrix. These tend to be far from normal.

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 built-in Julia command svd.

Note that while the "full" SVD has a square $U$, the "thin" form is the default. Here the columns are orthonormal even though $U$ is not square.

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 $\sigma_1 \varepsilon_\text{mach}$). 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 constant $C$. 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.