The Winding Number: symmetric matrix

Showing posts with label symmetric matrix. Show all posts

Geometry, positive definiteness, and Sylvester's law of inertia

Something I found absurdly dissatisfying when first studying linear algebra was the idea of a positive-definite matrix (or a nonnegative-definite one). Here are some explanations of the idea I found online:

it's a generalisation of a positive real number -- correct, but why? In what sense? Sure, you could say "all the eigenvalues are positive real numbers in an orthogonal eigenbasis" -- but why is this really important? It just doesn't feel complete. This will pretty much be our second motivation, but with more backstory.
it keeps vectors "roughly" near where they started -- this is by far the worst explanation I've found of the idea -- the condition that $x\cdot Ax > 0$ means that any vector remains within a right angle from where it started. Not only is this terrible because it seems absurdly arbitrary (to choose $\pi/2$ as our special angle), but it also fails to make clear why we're interested only in positive-definite symmetric matrices, analogous to positive real numbers. On the reals, certainly, there are plenty of transformations that achieve this with real vectors (rotations of less than $\pi/2$, for instance), but we don't care about them. The most serious problem with this explanation, though, is that it tries to reinterpret the condition $x^TAx>0$ in terms of the conventional Euclidean dot product, while the whole point is to look at generalised dot products, with bilinear forms other than the Euclidean one.

In this article, I'll motivate the idea of a positive-definite matrix by considering "generalised geometries" and generalised inner products -- through a series of exercises (well, I'll try to keep them exercises, but maybe I won't be able to stop myself from answering them myself).

"Definite geometries"

First, we come up with a definition of geometry (no pun intended). Much of the linear algebra we've dealt with -- specifically the dot product -- was with Euclidean geometry in mind, and it's interesting to think about what kind of linear algebra we would come up with if we considered other sorts of geometries.

The first image in your head when hearing of geometry is that of a space, or manifold -- perhaps $\mathbb{R}^n$. But a space is just a set of points. Most geometric properties you've dealt with deal with properties like length and angles and shapes. These properties don't depend on e.g. where you place an object on the manifold, i.e. translations -- as well as some other transformations. Can you characterise all the linear transformations under which geometric properties (like the ones we mentioned) are invariant under? -- i.e. the symmetries of Euclidean geometry.
These transformations are known as "rigid transformations" and form a group (prove it if you want, but come on -- they're symmetries, of course they form a group). Can you identify this group (discard translations if you prefer)?
So Euclidean geometry can be defined as a the symmetries of $\mathbb{R}^n$ under the group $O(n)$ acting on it. It is then natural to generally define a geometry as the symmetries of a manifold under a group acting on it.

Now that we have generalised our definition of a geometry, let's specialise to a specific sort of geometry somewhat "analogous" to the traditional orthogonal-group (i.e. Euclidean) geometry. We will let our space be $\mathbb{R}^n$ or $\mathbb{C}^n$ but experiment with our group. By analogous, we mean not that the geometries are identical, but at least that the same notions -- like lengths and angles and shapes -- can be defined for them, that the ideas in the geometry aren't completely foreign to us.

Much like the Orthogonal group can be defined by the invariance of the identity bilinear form $\mathrm{diag}(1,1,1,1)$ under a "bilinear form similarity transformation", more commonly known as a congruence (i.e. $A^T I A = I$), we can consider groups that are defined by some general $A^T M A = M$.
Obviously, not all matrix groups can be written this way -- for example, any subgroup of $O(n)$ cannot be. But groups of this form define in some sense geometries not very different from Euclidean geometry -- why? Because the form preserved by the Orthogonal group -- the identity form -- is the dot product on Euclidean geometry. Preservation of the identity form is equivalent to the preservation of the Euclidean dot product -- prove this -- which also means lengths and angles are preserved.
As any dot product is necessarily a bilinear form, it can be represented by a bilinear form $M$ called the metric as $v^T M w$, and its preservation is equivalent to the preservation of $M$ under bilinear form conjugation, i.e. $A^T M A = M$ -- prove this! (the proofs are absurdly trivial).
Examples of such groups include: the "indefinite orthogonal group", which you may know as the Lorentz group $O(1,3)$ from special relativity, the group of linear transformations that preserve the bilinear form $\mathrm{diag}(-1,1,1,1)$ (called the Minkowski metric). Indeed, Minkowskian geometry has notions of length (the spacetime interval) and angles (some combination of rapidity and angles).

Next, we are interested in thinking about when two geometries are "basically the same".

Try to write down some simple two-dimensional geometries -- consider e.g. $M = \left[ {\begin{array}{*{20}{c}}0&{ - 1}\\1&0\end{array}} \right]$. Study some of its properties. (this is "symplectic geometry", by the way) Do you think this is the "same" as Euclidean geometry?
Think about what kind of properties you looked at to establish the answer as "No". Use them to come up with a simple and snappy definition of two geometries being the same, or isomorphic.
You should have come to the conclusion -- two geometries on the same manifold are isomorphic iff their groups are isomorphic (If you read this before figuring out the answer for yourself, bleach your brain and try again.) (For legal reasons, that's a joke.)
Let's study some examples of such an isomorphism. The trivial case is where the groups are equal, e.g. if $M = kN$ or $M = N^T$ (prove these). What about some non-trivial isomorphism? Here's an idea: groups defined by congruent metrics are isomorphic. I.e. if $M=P^TNP$ for some change of basis matrix $P$, the groups $\{A^TMA=M\}$ and $\{A^TNA=N\}$ are isomorphic. Prove this (again, the proof is trivial) -- you will see that the isomorphism is a similarity relation $A \leftrightarrow P^{-1}AP$.
Is this an iff statement? If two groups bilinear form-preserving groups are isomorphic, is there a way to write them as $\{A^HMA=M\}$, $\{A^HNA=N\}$ such that $M$ and $N$ congruent? I'm not sure. It would suffice to prove that all isomorphisms of a matrix group are similarity transformations. Perhaps this is implied by Isomorphic iff potentially conjugate, but how do we know the conjugacy isn't in some weird group that $GL_{\mathbb{R}}(n)$ is homomorphic to?
One can also consider the case of non-invertible $P$ -- do we have an isomorphism between $M$-preservers and $N$-preservers if $M=P^TNP$ for non-invertible $P$? No? What about a homomorphism? In which direction?

So which geometries are isomorphic to Euclidean geometry? What matrices are congruent to the identity form?

No prizes for saying "metric tensors of the form $P^TP$ (or more generally $P^H P$)" for invertible $P$. These matrices -- those that are congruent to the identity matrix -- are called positive-definite matrices. Along the lines of part f above, one can also consider the case of non-invertible $P$ -- these are called positive-semidefinite or nonnegative-definite matrices, and Euclidean geometry is homomorphic to positive-semidefinite geometries.
To be fair, these aren't the only geometries isomorphic to Euclidean geometry -- remember the trivial isomorphisms? So for instance, negative-definite geometries are also isomorphic to Euclidean geometry.
A neat way to visualise these "isomorphisms and homomorphisms of geometries" is by looking at the contours of the geometries, i.e. the set $x^TMx = C$. Positive definite (and negative definite) matrices correspond to elliptical contours (while positive semidefinite matrices correspond to the degenerate cases -- a degenerate ellipse has all the symmetries of a non-degenerate one, but not vice versa), which can easily be stretched into a Euclidean circle. Other matrices, on the other hand, may have hyperbolic contours which cannot be similarly deformed into a Euclidean circle.

any symmetry of the ellipse/circle can be mapped homomorphically to a symmetry of the straight lines, but not vice versa.
Recall that the equation of an ellipse takes the form $\mathop \sum \limits_{i = 1}^n {a_i}{x_i}^2 = C$ for positive $a_i$. So our interpretation above is equivalent to stating that a matrix of the form $P^T P$ or $P^H P$ has positive (for invertible $P$) or non-negative (degenerate ellipse) real eigenvalues(this should be pretty easy to prove).
More generally, any two congruent matrices have the same numbers of positive, negative and zero eigenvalues (called the positive, negative and zero indices of inertia respectively). This is known as Sylvester's law of inertia (prove it!), and shows that all real-eigenvalued matrices are congruent to a diagonal matrix with some number of 1's, -1's and 0's (and arrangement doesn't matter) -- see also the metric signature. This gives us a condition to tell if any two matrices are congruent, or any two form-preserving geometries are isomorphic/homomorphic.

Is it really true, though -- that any geometry with elliptical contours is isomorphic to Euclidean geometry? Come up with a counter-example (and how did you come up with it?)

You might consider, e.g. $M=\left[\begin{array}{*{20}{c}}1&{ - 1}\\1&1\end{array}\right]$ -- this produces exactly the same contours as Euclidean geometry -- same unit circle, same everything. But it's not symmetric, and all positive-definite matrices are symmetric/Hermitian (proof is trivial). In fact, any $M$ produces the same contours as $\frac12 (M+M^T)$ -- its "symmetric part" (why?). What's going on? Does the norm (quadratic form) not completely define the dot product (bilinear form)?
If you think about this for a while, you might get an idea of what's going on -- the symmetric/Hermitian part of a matrix defines the contours on the real part of the vector space, but the antisymmetric/anti-Hermitian part begins to matter in $\mathbb{C}^n$. The contours of the quadratic form in $\mathbb{C}^n$ completely determine the dot product, i.e. if $v^HMv=v^HNv$ for all complex vectors $v$, then $v^HMw=v^HNw$ for all complex vectors $v$ and $w$, i.e. $M=N$. The proof is trivial.

Next, let's consider some properties and alternate characterisations of positive-definite matrices.

From the ellipse depiction, it's reasonable to wonder if a matrix is positive-definite if the norm it induces is positive for all non-zero real vectors, i.e. $v^TMv>0$ (certainly the forward implication -- only if -- is clear, from the $P^TP$ factorisation). As it turns out, though, there are other matrices -- such as a rotation by less than $\pi/2$, that also satisfy this condition. It is certainly clear that the condition $v^TMv>0$ combined with $A$ being symmetric imply a matrix is positive-definite -- by completing the square on a symmetric bilinear form -- but any matrix $A$ for which $(M+M^T)/2$ is positive-definite also satisfies $v^TMv>0$ by the same argument (if this seems anything but completely obvious, think about the corresponding quadratic expressions).
The reason for this annoyance is that in $\mathbb{R}^n$, you have matrices that are pure rotations, with no eigenvectors, so the non-positiveness of your eigenvalues don't have to matter. On the other hand, if you extend our domain to $\mathbb{C}^n$ -- i.e. $v^HMv>0$ for all complex vectors $v$, all the eigenvalues are "accounted for". Find a way to write this idea down precisely.
Here's another way to think about it: if $v^HMv\in\mathbb{R}$ for all complex vectors $v$, the matrix $M$ is Hermitian. The proof is basically just algebraic simplification, considering the imaginary part of $(v+iw)^HA(v+iw)$, which is $v^HAw-w^HAv$ -- which is the "symplectic part" of the general complex dot product. See this math stackexchange answer for a fuller explanation.

To be completely honest, I'm being disingenous in claiming that this is "the" motivation for positive-definite matrices. There is a completely independent motivation arising from optimisation in multivariable calculus (the second-derivative/Hessian test), a completely independent motivation arising from systems of differential equations, a completely independent motivation arising from covariance matrices, and so on.

Perhaps a way of thinking of this is that a positive-definite matrix is simply a normal matrix with positive eigenvalues, and much of this article is really a justification for why positive-definite metric tensors are (un-)interesting.

Null, row spaces, transpose, fundamental theorem of linear algebra

This is an exciting article, so pay close attention.

In the last article, we introduced the column space, and we are lead to wonder about the vectors that are mapped to the zero vector (let's call the set of these vectors the "null space"). Based on some of the transformations we've seen, we might wonder if the null space is essentially the subspace perpendicular to the column space, i.e. the set of all vectors perpendicular to every vector in the column space (we call this the "orthogonal complement" of the column space).

However, this is demonstrably wrong. Suppose one rotates the co-ordinate system before collapsing it onto a lower dimension. The "collapsing" matrix, the singular matrix, may be $\left[ {\begin{array}{*{20}{c}}1&0\\0&0\end{array}} \right]$, and the rotation matrix may be $\left[ {\begin{array}{*{20}{c}}0&{ - 1}\\1&0\end{array}} \right]$, then the composite transformation is $\left[ {\begin{array}{*{20}{c}}1&0\\0&0\end{array}} \right]\left[ {\begin{array}{*{20}{c}}0&{ - 1}\\1&0\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}0&{ - 1}\\0&0\end{array}} \right]$

In general in $\mathbb{R}^2$, if the "simple collapse" transformation looks like this:

$$\left[ {\begin{array}{*{20}{c}}{{{\cos }^2}\phi }&{\cos \phi \sin \phi }\\{\cos \phi \sin \phi }&{{{\sin }^2}\phi }\end{array}} \right]$$
(Show that the non-rotating collapses can be written in this way), and the rotation matrix looks like this:

$$\left[ {\begin{array}{*{20}{c}}{\cos \theta }&{\sin \theta }\\{ - \sin \theta }&{\cos \theta }\end{array}} \right]$$
Then their product

$$\left[ {\begin{array}{*{20}{c}}{{{\cos }^2}\phi }&{\cos \phi \sin \phi }\\{\cos \phi \sin \phi }&{{{\sin }^2}\phi }\end{array}} \right]\left[ {\begin{array}{*{20}{c}}{\cos \theta }&{\sin \theta }\\{ - \sin \theta }&{\cos \theta }\end{array}} \right] \\= \left[ {\begin{array}{*{20}{c}}{\cos \phi \cos (\phi - \theta )}&{\cos \phi \sin (\phi - \theta )}\\{\sin \phi \cos (\phi - \theta )}&{\sin \phi \sin (\phi - \theta )}\end{array}} \right]$$
Which is also a singular matrix with the same rank and column space as the original, but its null space is a rotated version of the original, and therefore no longer perpendicular to the column space.

We make the following observations:

The rotation has introduced an "asymmetry" in the components of the matrix -- the matrix is no longer symmetric across the principal diagonal, the rows and columns are no longer the same. In our original terminology before we introduced matrices, the "contribution of y to x" is no longer the same as "the contribution of x to y.
The span of the column vectors is not dependent on $\theta$ (proving again that the column space is not the space orthogonal to the null space), but the span of the row vectors is -- we'll call this the row space. The row space used to be the same as the column space, but is now rotated clockwise by an angle of $\theta$. Since the space is rotated counter-clockwise by $\theta$ before being collapsed, this means the null space is $\theta$ clockwise to what its position would have been without the rotation.

Hence, the null space is perpendicular to the row space, at least if the pre-collapse transformation is a rotation. It would be a very educated guess to say that this applies generally, that the null space of a transformation is always perpendicular to the row space.

Indeed, this is the case, and is pretty easy to show:

$$\left[ {\begin{array}{*{20}{c}}{{r_1}}\\ \vdots \\{{r_n}}\end{array}} \right]\vec x = 0\,\,\, \Rightarrow \,\,\,{r_i} \cdot \vec x = 0\,\,\,\,\,\,\forall i \in [1,n] \cap \mathbb{Z}$$
More interestingly, however, we made a pretty important observation about the symmetry of a matrix: asymmetry in the matrix seems to be a measure of "rotation-ish" a matrix is. The reason this makes sense is that while the values on the principal diagonal talk about how much each component is scaled in the resulting image, the off-diagonal elements talk about how much contribution there is to one component of a vector from the component in another direction, something that happens during rotations.

If the contribution from x to y is exactly the same as the contribution from y to x, then the xy-plane isn't really being rotated, but the basis vectors are rather being pulled closer to/apart from each other. On the other hand, when they are different, the "orientation" of the axes changes, and an actual rotation is induced.

The most "rotation-ish" effect is created when the values of the matrix are the negative of the their reflection across the principal diagonal, because it means the basis vectors are being rotated by the same angle in the same direction.

Quick exercise: plot how such a transformation looks in $\mathbb{R}^2$. You'll notice that the rotation isn't as "perfect" as you might've hoped -- the vectors change length, etc., and it's the orthogonal displacement in the basis vectors that is the same in orthogonal directions for the basis vectors, not the angles.

These changes in length are a result of scaling, i.e. the values along the principal diagonal.

Well, not exactly, because the values along the principal diagonal scale the part of the basis vectors in their original direction, not the overall length of the basis vectors. This is why (i) the resulting matrix not only eliminates the scaling, but also ensures the rotation is in right-angles, (ii) the resulting matrix is not actually just a bunch of pure rotation, as its rotations are still scaled, and (iii) why some otherwise-antisymmetric matrices with a principal diagonal, like$\left[ {\begin{array}{*{20}{c}}
{\cos \theta }&{ - \sin \theta } \\
{\sin \theta }&{\cos \theta }
\end{array}} \right]$, can still be rotations in some angle other than a right angle. Highly recommended reading: my answer to "Intuition behind the Speciality of Symmetric Matrices".

Therefore, it is useful to extract from the matrix the purely anti-symmetric part, with a zero principal diagonal:

$$\left[ {\begin{array}{*{20}{c}}0&{{b_{12}}}& \ldots &{{b_{1n}}}\\{ - {b_{12}}}&0& \ldots &{{b_{2n}}}\\ \vdots & \vdots & \ddots & \vdots \\{ - {b_{1n}}}&{ - {b_{2n}}}& \ldots &0\end{array}} \right]$$
This matrix is called a skew-symmetric matrix or an anti-symmetric matrix, and in $\mathbb{R}^n$ is essentially a combinations of scaled rotations around different axes.

Meanwhile, one may define a symmetric matrix in the following way:

$$\left[ {\begin{array}{*{20}{c}}b_{11}&{{b_{12}}}& \ldots &{{b_{1n}}}\\{{b_{12}}}&b_{12}& \ldots &{{b_{2n}}}\\ \vdots & \vdots & \ddots & \vdots \\{{b_{1n}}}&{{b_{2n}}}& \ldots &b_{nn}\end{array}} \right]$$
These matrices essentially scale and skew vectors -- the principal diagonal components do the scaling in each direction, and the other components do the skewing, i.e. tilting the basis vectors towards each other.

One may wonder if it would have been better to simply deal with diagonal matrices instead of symmetric ones. However, as we will see, it turns out that any matrix can be written as the sum of a symmetric matrix and an anti-symmetric matrix. It is also worth noting that we will eventually see that a symmetric matrix is a generalisation of a scaling matrix, where the scaling is done in some arbitrary directions that need not be the basis vectors. These vectors are called "eigenvectors".

Looking at the definitions of symmetric and antisymmetric matrices, it is clear that any matrix may be written as the sum of a symmetric matrix and an antisymmetric one. Specifically, one may write:

$$A = \underbrace {\frac{1}{2}(A + {A^T})}_{\scriptstyle{\rm{symmetric }}\atop\scriptstyle{\rm{part}}} + \underbrace {\frac{1}{2}(A - {A^T})}_{\scriptstyle{\rm{antisymmetric }}\atop\scriptstyle{\rm{part}}}$$
Where $A^T$ is the "transpose" of $A$, referring to the matrix formed upon taking flipping $A$'s entries across the principal diagonal. E.g. the row space of $A$ is the column space of $A^T$.

Does this all remind you of something?

Any entity can be written in two "parts" of a specific nature, which look curiously like the exponential form of the cosine and sine functions
These two parts represent scaling and scaled $\pi/2$ rotation respectively.

It should remind you of the Cartesian form of a complex number.

A symmetric matrix is "like" a real number, and an anti-symmetric matrix is "like" an imaginary number. A complex number can be thought of as an object to be transformed (like a vector) as well as as a transformation itself (like a matrix).

However, it is important to highlight the differences: (i) while a real number only scales things in their own direction (like a multiple of $I$), a symmetric matrix can skew things, which is equivalent to scaling across a different set of axes. Therefore while complex numbers can encode spiral transformations, matrices encode all linear transformations. (ii) complex numbers transform on the complex plane, which is a two dimensional plane like $\mathbb{R}^2$, while linear transformations can operate in any number of dimensions, and not necessarily even just in $\mathbb{R}^n$. An example of a consequence of this would be that an anti-symmetric matrix can encode a series of right-angle rotations with corresponding scalings in dimensions greater than three, but an imaginary number can only correspond to a rotation around an axis pointing out of the plane.

It is fair to say that linear algebra generalises complex numbers with matrices. For some examples of correspondence between specific complex numbers, see Introduction to symmetry, section "symmetry on the complex plane". We will formalise this whole idea of matrices being "like real numbers" and "like imaginary numbers" when we do eigenvalues and eigenbases -- in fact, antisymmetric matrices have imaginary eigenvalues.

The complex conjugate, similarly, is generalised to the transpose. Explain how. (Hint: $A^T$ does precisely the opposite rotation-ish, i.e. antisymmetric actions as $A$ while preserving the symmetric actions. What does this tell you about matrices whose transpose and inverse are equal? What does it tell you about matrices that are equal to their transpose?)

Watch the above Khan Academy video.
Come up with an intuitive explanation for why the row space solution is the shortest.

The three following results:

Row space is perpendicular to the null space
Row rank equals column rank
Rank plus nullity equals dimension (Rank-nullity theorem)

Together imply what is called the fundamental theorem of linear algebra -- that the row space is the orthogonal complement of the null space. Why? To be the orthogonal complement, you need to be orthogonal (implied by 1), and your dimensions need to add up to the total dimension of the space. The latter is implied by 3, but our intuition applies perhaps better to the dimension of the column space, and 2 implies that this has the same dimension as the row space, and we're done.

Among these three results, this article provides fairly solid intuition for the first and the third. The second is really assumed throughout this article, but if you want really solid intuition for it, read on.

Consider an $m$ by $n$ matrix $A$ with linearly independent rows (i.e. its row rank is $m$) (we can always turn matrices to this form with a bunch of zero rows at the end via row operations). Then the nullity of $A$, i.e. the number of solutions to $Ax=0$ is $n-m$, as there are $m$ equations in $n$ variables. Thus we have that row rank plus nullity equals the dimension. But we know from our "collapsing intuition" that column rank plus nullity equals the dimension. And we're done.

An obvious consequence of rank-nullity is that injectivity is equivalent to surjectivity. However, this is not true for infinite-dimensional spaces. Why not? You might find it's related to Hilbert's hotel.

It's worth noting that while we've pretended that having the column space equal to the row space is equivalent to being symmetric, this is not really true. There's a broader set of matrices for which the column and row spaces are equal, called "rank-symmetric" or EP matrices.

This article is extended in SVD, polar decomposition, normal matrices; a re-look at transposes and FTLA.