Question

Question: If A is \(m \times n\), then the matrix \(G = {A^T}A\) is called the Gram matrix of A. In this case, the entries of G are the inner products of the columns of A. (See Exercises 9 and 10).

10. Show that if an \(n \times n\) matrix G is positive semidefinite and has rank r, then G is the Gram matrix of some \(r \times n\) matrix A. This is called a rank-revealing factorization of G. (Hint: Consider the spectral decomposition of G, and first write G as \(B{B^T}\) for an \(n \times r\) matrix B.)

Short answer

It is proved that the G is the Gram matrix of some \(r \times n\) matrix A.

Step-by-step solution

Rank Theorem

The Rank Theoremstates that a \(m \times n\) matrix \(A\) has the same dimensions of the row space and column space. The number of pivot position in \(A\) is exactly equal to the rank of \(A\) and satisfy the equation \({\mathop{\rm rank}\nolimits} A + \dim {\mathop{\rm Nul}\nolimits} A = n\).

Show that G is the Gram matrix of some \(r \times n\) matrix A

When \({\mathop{\rm rank}\nolimits} G = r\) then \(\dim {\mathop{\rm Nul}\nolimits} G = n - r\), according to the Rank theorem. Therefore, the eigenvalue of \(G\) is 0 of multiplicity \(n - r\) , and the spectral decomposition of \(G\) is given by \(G = {\lambda _1}{{\bf{u}}_1}{\bf{u}}_1^T + \ldots + {\lambda _r}{{\bf{u}}_r}{\bf{u}}_r^T\).

Moreover \({\lambda _1}, \ldots ,{\lambda _r}\) are positive since \(G\) is positive semidefinite. Then

\(G = \left( {\sqrt {{\lambda _1}} {{\bf{u}}_1}} \right)\left( {\sqrt {{\lambda _1}} {{\bf{u}}_1}^T} \right) + \ldots + \left( {\sqrt {{\lambda _r}} {{\bf{u}}_r}} \right)\left( {\sqrt {{\lambda _r}} {\bf{u}}_r^T} \right)\)

According to the column-row expansion of a matrix product, \(G = B{B^T}\), with \(B\) is the \(n \times r\) matrix \(B = \left( {\begin{array}{*{20}{c}}{\sqrt {{\lambda _1}} {{\bf{u}}_1}}& \ldots &{\sqrt {{\lambda _r}} {{\bf{u}}_r}}\end{array}} \right)\). Therefore, \(G = {A^T}A\) for \(A = {B^T}\).

Thus, it is proved that the G is the Gram matrix of some \(r \times n\) matrix A.