Matrix decompositions

In this section we examine ways in which a square matrix can be factored into the product of matrices derived from its eigenvectors; we refer to this process as matrix decomposition . Matrix decompositions similar to the ones in this section will form the basis of our principal text-analysis technique in Section 18.3 , where we will look at decompositions of non-square term-document matrices. The square decompositions in this section are simpler and can be treated with sufficient mathematical rigor to help the reader understand how such decompositions work. The detailed mathematical derivation of the more complex decompositions in Section 18.2 are beyond the scope of this book.

We begin by giving two theorems on the decomposition of a square matrix into the product of three matrices of a special form. The first of these, Theorem 18.1.1, gives the basic factorization of a square real-valued matrix into three factors. The second, Theorem 18.1.1, applies to square symmetric matrices and is the basis of the singular value decomposition described in Theorem 18.2.

Theorem. (Matrix diagonalization theorem) Let $S$ be a square real-valued $\lsinoterms\times \lsinoterms$ matrix with $\lsinoterms$ linearly independent eigenvectors. Then there exists an eigen decomposition

$$S=U\Lambda U^{-1},$$ (223)

where the columns of $U$ are the eigenvectors of $S$ and $\Lambda$ is a diagonal matrix whose diagonal entries are the eigenvalues of $S$ in decreasing order

$$\left( \begin{array}{cccc} \lambda_1 & & & \\ & \lambda_... ..._\lsinoterms \end{array} \right), \lambda_i\geq\lambda_{i+1}.$$ (224)

If the eigenvalues are distinct, then this decomposition is unique. End theorem.

To understand how Theorem 18.1.1 works, we note that $U$ has the eigenvectors of $S$ as columns

$$U=\left( \vec{u_1}\ \vec{u_2} \cdots \vec{u_\lsinoterms} \right).$$ (225)

Then we have

$$SU = S\left( \vec{u_1}\ \vec{u_2} \cdots \vec{u_\lsinoterms} \right)$$ (226)

$$= \left( \lambda_1\vec{u_1}\ \lambda_2\vec{u_2} \cdots \lambda_\lsinoterms\vec{u_\lsinoterms} \right)$$ (227)

$$= \left( \vec{u_1}\ \vec{u_2} \cdots \vec{u_\lsinoterms} \rig... ..._2 & & \\ & & \cdots & \\ & & & \lambda_\lsinoterms \end{array} \right).$$ (228)

Thus, we have $SU=U\Lambda$, or $S=U\Lambda U^{-1}$.

We next state a closely related decomposition of a symmetric square matrix into the product of matrices derived from its eigenvectors. This will pave the way for the development of our main tool for text analysis, the singular value decomposition (Section 18.2 ).

Theorem. (Symmetric diagonalization theorem) Let $S$ be a square, symmetric real-valued $\lsinoterms\times \lsinoterms$ matrix with $\lsinoterms$ linearly independent eigenvectors. Then there exists a symmetric diagonal decomposition

$$S=Q\Lambda Q^{T},$$ (229)

where the columns of $Q$ are the orthogonal and normalized (unit length, real) eigenvectors of $S$, and $\Lambda$ is the diagonal matrix whose entries are the eigenvalues of $S$. Further, all entries of $Q$ are real and we have $Q^{-1}=Q^T$. End theorem.

We will build on this symmetric diagonal decomposition to build low-rank approximations to term-document matrices.

Exercises.

• What is the rank of the $3\times 3$ diagonal matrix below?
  

  $$\left( \begin{array}{ccc} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 2 & 1 \\ \end{array}\right)$$ (230)

  
  

• Show that $\lambda=2$ is an eigenvalue of
  

  $$\lsimatrix=\left( \begin{array}{cc} 6 & -2 \\ 4 & 0 \\ \end{array} \right).$$ (231)

  
  
  Find the corresponding eigenvector.

• Compute the unique eigen decomposition of the $2\times 2$ matrix in (222).