An Orthonormal Eigenbasis For A* A

Why an Orthonormal Eigenbasis Matters

For a complex matrix, symmetry is expressed by the condition \(\mathbf{H}^{*}=\mathbf{H}\), where \(\mathbf{H}^{*}\) is the conjugate transpose. Such a matrix is called Hermitian. The key fact is that a Hermitian matrix can be described using mutually perpendicular unit eigenvectors: in that basis, its action is especially simple. Here we prove this fact directly, using an eigenvector and induction on the dimension. We then apply it to the complex Gram matrix \(\mathbf{A}^{*}\mathbf{A}\), the matrix that appears in the complex singular value decomposition.

All matrices and vector spaces in this tutorial are over \(\mathbb{C}\). We use the inner product \(\langle\mathbf{x},\mathbf{y}\rangle=\mathbf{x}^{\top}\overline{\mathbf{y}}\), which is linear in its first slot and conjugate-linear in its second. The norm is \(\|\mathbf{x}\|=\sqrt{\langle\mathbf{x},\mathbf{x}\rangle}\). In particular, \(\mathbf{x}\perp\mathbf{y}\) means \(\langle\mathbf{x},\mathbf{y}\rangle=0\).

Two Facts About Hermitian Matrices

Before the induction, we establish two properties that explain why the orthogonal-complement step works. First, every eigenvalue of a Hermitian matrix is real. Second, eigenvectors for distinct eigenvalues are orthogonal. The inner product must be used with conjugation in these arguments.

Proof. Since \(\mathbf{H}^{*}=\mathbf{H}\), the inner product identity \(\langle\mathbf{H}\mathbf{x},\mathbf{y}\rangle=\langle\mathbf{x},\mathbf{H}\mathbf{y}\rangle\) holds. Taking \(\mathbf{y}=\mathbf{x}\), we obtain \(\langle\mathbf{H}\mathbf{x},\mathbf{x}\rangle=\langle\mathbf{x},\mathbf{H}\mathbf{x}\rangle\). By conjugate symmetry, the right-hand side is the complex conjugate of the left-hand side, so \(\langle\mathbf{H}\mathbf{x},\mathbf{x}\rangle\) is real. But \(\mathbf{H}\mathbf{x}=\lambda\mathbf{x}\) and linearity in the first slot give \(\langle\mathbf{H}\mathbf{x},\mathbf{x}\rangle=\lambda\|\mathbf{x}\|^2\). As \(\|\mathbf{x}\|^2>0\), it follows that \(\lambda\) is real. \(\square\)

Proof. Suppose \(\mathbf{H}\mathbf{x}=\lambda\mathbf{x}\) and \(\mathbf{H}\mathbf{y}=\mu\mathbf{y}\), where \(\mathbf{x}\) and \(\mathbf{y}\) are nonzero and \(\lambda\ne\mu\). The eigenvalues are real by the preceding result. Using the Hermitian identity and the inner product conventions, we have \(\langle\mathbf{H}\mathbf{x},\mathbf{y}\rangle=\langle\mathbf{x},\mathbf{H}\mathbf{y}\rangle\), so \(\lambda\langle\mathbf{x},\mathbf{y}\rangle=\overline{\mu}\langle\mathbf{x},\mathbf{y}\rangle=\mu\langle\mathbf{x},\mathbf{y}\rangle\). Thus \((\lambda-\mu)\langle\mathbf{x},\mathbf{y}\rangle=0\). Since \(\lambda-\mu\ne0\), we get \(\langle\mathbf{x},\mathbf{y}\rangle=0\). \(\square\)

The Orthogonal-Complement Induction

We now prove the main result for every positive finite dimension. The induction step begins by selecting one eigenvector and normalizing it. Its orthogonal complement is the set of vectors perpendicular to it. The crucial point is that this complement is invariant under \(\mathbf{H}\): applying \(\mathbf{H}\) to a vector in the complement leaves the vector in the complement. The restriction to that smaller space is still Hermitian, so induction supplies the rest of the basis.

Proof. We use induction on \(n\). If \(n=1\), the sole standard basis vector is an eigenvector of the one-by-one matrix and can be chosen to have norm \(1\). Now let \(n>1\), and assume the theorem holds for Hermitian matrices of size \(n-1\).

The characteristic polynomial \(\det(\mathbf{H}-\lambda\mathbf{I}_n)\) has degree \(n\). By the Fundamental Theorem of Algebra, it has a complex root \(\lambda\). The determinant criterion for singularity then gives a nonzero vector \(\mathbf{x}\) satisfying \(\mathbf{H}\mathbf{x}=\lambda\mathbf{x}\). The eigenvalue is real by the theorem already proved. Normalize this eigenvector by setting \(\mathbf{u}=\mathbf{x}/\|\mathbf{x}\|\), so \(\|\mathbf{u}\|=1\) and \(\mathbf{H}\mathbf{u}=\lambda\mathbf{u}\).

Let \(W=\{\mathbf{w}\in\mathbb{C}^n:\langle\mathbf{w},\mathbf{u}\rangle=0\}\), the orthogonal complement of \(\mathbf{u}\). To show invariance, take any \(\mathbf{w}\in W\). Then \(\langle\mathbf{H}\mathbf{w},\mathbf{u}\rangle=\langle\mathbf{w},\mathbf{H}\mathbf{u}\rangle=\langle\mathbf{w},\lambda\mathbf{u}\rangle=\overline{\lambda}\langle\mathbf{w},\mathbf{u}\rangle=0\). Here \(\lambda\) is real, and the last equality follows from \(\mathbf{w}\in W\). Therefore \(\mathbf{H}\mathbf{w}\in W\).

The vector \(\mathbf{u}\) together with a basis of \(W\) is a basis of \(\mathbb{C}^n\): any \(\mathbf{z}\) decomposes as \(\mathbf{z}=\langle\mathbf{z},\mathbf{u}\rangle\mathbf{u}+(\mathbf{z}-\langle\mathbf{z},\mathbf{u}\rangle\mathbf{u})\), and the second term belongs to \(W\); the intersection of \(W\) with the span of \(\mathbf{u}\) is \(\{\mathbf{0}\}\). Thus \(W\) has dimension \(n-1\).

Choose an orthonormal basis \(\mathbf{q}_1,\dots,\mathbf{q}_{n-1}\) of \(W\). The restriction of \(\mathbf{H}\) to \(W\) has a Hermitian matrix in this basis: its entries are \(b_{ij}=\langle\mathbf{H}\mathbf{q}_j,\mathbf{q}_i\rangle\), and the identity \(\langle\mathbf{H}\mathbf{q}_j,\mathbf{q}_i\rangle=\langle\mathbf{q}_j,\mathbf{H}\mathbf{q}_i\rangle=\overline{b_{ji}}\) gives \(b_{ij}=\overline{b_{ji}}\). By the induction hypothesis, this restriction has an orthonormal eigenbasis of \(W\). Each vector in that basis is also an eigenvector of \(\mathbf{H}\) on \(\mathbb{C}^n\), because \(W\) is invariant. Appending \(\mathbf{u}\) gives an orthonormal eigenbasis of \(\mathbb{C}^n\): the vectors from \(W\) are mutually orthonormal, and each is perpendicular to \(\mathbf{u}\). This completes the induction. \(\square\)

Applying the Theorem to the Gram Matrix

For \(\mathbf{A}\in\mathbb{C}^{m\times n}\), the complex Gram matrix \(\mathbf{A}^{*}\mathbf{A}\) is an \(n\times n\) matrix. It is Hermitian because \((\mathbf{A}^{*}\mathbf{A})^{*}=\mathbf{A}^{*}\mathbf{A}\). It is also positive semidefinite: for every \(\mathbf{x}\in\mathbb{C}^n\), \(\langle\mathbf{A}^{*}\mathbf{A}\mathbf{x},\mathbf{x}\rangle=\langle\mathbf{A}\mathbf{x},\mathbf{A}\mathbf{x}\rangle=\|\mathbf{A}\mathbf{x}\|^2\ge0\). Consequently the theorem just proved gives \(\mathbf{A}^{*}\mathbf{A}\) an orthonormal eigenbasis. Its eigenvalues are nonnegative: for a nonzero eigenvector \(\mathbf{x}\) with eigenvalue \(\lambda\), \(\lambda\|\mathbf{x}\|^2=\|\mathbf{A}\mathbf{x}\|^2\ge0\), and \(\lambda\) is real.

Common Pitfall: Conjugation Is Essential

A common error is to check orthogonality of complex vectors using \(\mathbf{x}^{\top}\mathbf{y}\) instead of the inner product \(\langle\mathbf{x},\mathbf{y}\rangle=\mathbf{x}^{\top}\overline{\mathbf{y}}\). For the eigenvectors \(\mathbf{x}=(i,1)^{\top}\) and \(\mathbf{y}=(i,-1)^{\top}\) above, the wrong calculation gives \(\mathbf{x}^{\top}\mathbf{y}=i^2-1=-2\), which might suggest they are not orthogonal. The correct calculation is \(\langle\mathbf{x},\mathbf{y}\rangle=i\overline{i}+1\overline{-1}=1-1=0\). Complex orthogonality uses conjugation; omitting it invalidates both the check and the invariance argument.

The orthonormal eigenbasis theorem is the structural reason that the Gram matrix can be analyzed through its eigenvectors. In the examples, the eigenvectors give perpendicular directions, while the corresponding eigenvalues are real and, for \(\mathbf{A}^{*}\mathbf{A}\), nonnegative. The proof relies on one eigenvector at a time: its orthogonal complement remains inside the space under the Hermitian matrix, allowing the same reasoning to continue in one lower dimension.