Tiny Volt22. Positive symmetric definite matrices
Symmetric matrices are the good kind of square matrices: they always have real eigenvalues and their eigenvectors are all perpendicular to each other. The previous chapter showed that multiplying a symmetric matrix with a vector amounts to projecting the vector on the eigenvectors and scaling each projection by its eigenvalue.
There is in fact an even better kind of symmetric matrix, a positive semi-definite matrix, in the sense that its eigenvalues are always non-negative.
22.1 Angle between the input and output vectors of a symmetric matrix
Consider a matrix-vector product for a symmetric matrix and a vector . We are interested in examining the angle between the input vector and the output vector .
- If the angle between and is less than or equal to 90°, the dot product would be non-negative. In other words, or simply .
- If the angle between the input and output vectors is more than 90°, we have .
A symmetric matrix for which we have for every is called a symmetric positive semi-definite matrix.
Let's see an example of a matrix that is symmetric but not positive semi-definite, and then an example of a positive semi-definite matrix.
First take .
Draw and its .
Now pick shown in gold, and in rose.
Show at the top left.
Now and watch the readout: dips below zero whenever the output swings more than 90° away from the input. So is not positive semi-definite. You can and replay.
Now take .
Draw and its .
Then in gold and in rose.
Show again.
: this time stays positive no matter where points, so is positive semi-definite. to replay.
22.2 Properties of symmetric PSD matrices
Just from one property, for all , we can deduce other properties of symmetric positive semi-definite (PSD) matrices.
22.2.1 All eigenvalues are non-negative
Since is symmetric, we know that its eigenvalues are real. Now for any eigenvalue and its corresponding eigenvector , we have:
Since is always positive, we have .
22.2.2 Sum of two symmetric PSD matrices is a symmetric PSD matrix
This also follows directly from the definition. Given two PSD matrices and :
- and , so
- which gives us
Thus, is also PSD.
22.2.3 Product of a symmetric PSD matrix and a non-negative scalar is a symmetric PSD matrix
Given a scalar and a PSD matrix , we have:
In other words, is also PSD.
22.2.4 is a symmetric PSD matrix for any matrix
This comes from the observation that:
Does this also imply that for any matrix , the matrix is PSD?
Yes. Apply the result above to the matrix : the matrix is PSD.
22.2.5 Diagonal elements of a symmetric PSD matrix are non-negative
To prove that the -th diagonal element , the element in the -th row and -th column, is non-negative, we just choose a special vector whose -th value is 1 and every other value is 0.
- We have . This gives us .
- This means that .
- Since , we have .
22.3 Symmetric PSD matrices induce a partial order over matrices
We can compare (and thus order) real numbers (eg ) but there is no good way to compare matrices. PSD matrices provide a way to compare some pairs of matrices and .
Given matrices and , we say that if is a PSD matrix.
In other words, if for all .
22.4 Visualizing
We can visualize how a matrix maps points on a circle to points on the real number line via the function . To show this mapping, we draw a line from the input, a point on the circle, to the output, the point on the x-axis.
First for the non-PSD matrix :
... draw a line on the unit circle to the number on the real line.
Note how the lines land on both sides of the origin.
To follow one pair, show in rose. Then : the output arrow keeps crossing to the negative side of the real line, confirming that for some inputs. to replay.
Now the same picture for the PSD matrix :
... draw a line on the unit circle to the number on the real line.
This time every line lands on the positive side. Show in rose. : the output arrow never leaves the positive real line, since for every . to replay.
22.5 Decomposition of a symmetric PSD matrix
The fact that the eigenvalues of a PSD matrix are all non-negative allows one to decompose a PSD matrix as for some matrix .
Since is symmetric, we can write it as . Here, the columns of are (unit) eigenvectors of and the diagonal values of the diagonal matrix are (non-negative) eigenvalues of . Since the diagonal values of are all non-negative, we can write where is also a diagonal matrix such that the -th diagonal value of is the square root of the -th diagonal value of .
Also note that since is a diagonal matrix, it is also symmetric. Thus . This gives us:
Writing , we get .
Note that here each column of is an eigenvector of scaled by the square root of its corresponding eigenvalue.
22.6 PSD matrices as analogues of positive numbers
A common way to introduce symmetric PSD matrices is to compare them with positive numbers: they are high-dimensional analogues of positive real numbers. I didn't want to start out using this analogy but the points below justify the comparison.
22.6.1 Product
Given a real number and a positive number , the value is always non-negative. Similarly for any vector and a PSD matrix , the dot product is always non-negative.
22.6.2 Square roots
A square root exists for a positive number . In other words, for some real number . Similarly we can write for a PSD matrix . The reverse is also true: the product of any number with itself is non-negative, . Similarly for any matrix , the matrix is always PSD.
22.6.3 Positive scalars become symmetric PSD matrices in higher dimensions
Variance of a random variable is always non-negative. In higher dimensions, the covariance matrix is always PSD. The diagonal values in a covariance matrix represent variances of the random variables in those corresponding dimensions.
22.7 Applications of symmetric PSD matrices
PSD matrices have a lot of applications in both pure and applied math. This is a rich area of math and this chapter only provides a basic introduction to symmetric positive semi-definite matrices.
22.7.1 Symmetric PSD matrices are everywhere
- The Laplacian matrix is a PSD matrix. It forms the basis of spectral geometry.
- As we mentioned earlier, the covariance matrix is also PSD.
- In machine learning, the kernel trick induces a similarity matrix over points in a dataset that is also PSD.
22.7.2 Optimization
There is a rich connection between convex optimization and PSD matrices. In fact, given a PSD matrix , the Hessian of the multi-variable function , where is the vector of variables of the function, is itself (up to a scale).
Semi-definite programming is an area of convex optimization where the properties of PSD matrices are used to optimize a linear function.
22.7.3 It defines a metric
Roughly speaking, a metric defined on a space (a set of points) is a function that takes two elements from that space and returns a non-negative number. The most common example of a metric is the notion of distance that we use in our daily lives. A metric has these properties:
- if
It is easy to define a metric using a (positive definite) matrix : given two elements the metric is defined as .