For any real \(m\times n\) matrix \(A\), the matrices \(A^TA\) and \(AA^T\) have the same non-zero eigenvalues.
The eigenvalues of \(A^TA\) (or those of \(AA^T\)) are non-negative. In particular, the non-zero eigenvalues must be strictly positive.
Let these positive eigenvalues be \(\lambda_1\), \(\lambda_2\), \(\ldots\), \(\lambda_r\) (where \(r\) is the rank of matrix \(A\)). Then, the singular values of the matrix \(A\) are the numbers \[\begin{matrix} \sigma_1 & = & \sqrt{\lambda_1} \\ \sigma_2 & = & \sqrt{\lambda_2} \\ & \vdots & \\ \sigma_r & = & \sqrt{\lambda_r} \end{matrix}\]
Work out the eigenvectors of \(A^TA\) associated with the eigenvalues \(\lambda_1\), \(\lambda_2\), \(\ldots\), \(\lambda_r\). Let them be \(v_1\), \(v_2\), \(\ldots\), \(v_r\). These are referred to as the right singular vectors of the matrix \(A\). Now extend this set, using Gram-Schimdt to an orthonormal set \[\{ v_1, v_2, \ldots, v_r, v_{r+1}, \ldots, v_n\}\] Construct the matrix \(V\) with these vectors as columns: \[V = \begin{bmatrix} \mid & \mid & & \mid \\ v_1 & v_2 & \ldots & v_n \\ \mid & \mid & & \mid \end{bmatrix}\]
Work out the eigenvectors of \(AA^T\) associated with the eigenvalues \(\lambda_1\), \(\lambda_2\), \(\ldots\), \(\lambda_r\). Let them be \(u_1\), \(u_2\), \(\ldots\), \(u_r\). These are referred to as the left singular vectors of the matrix \(A\). Now extend this set, using Gram-Schimdt to an orthonormal set \[\{ u_1, u_2, \ldots, u_r, u_{r+1}, \ldots, u_m\}\] Construct the matrix \(U\) with these vectors as columns: \[U = \begin{bmatrix} \mid & \mid & & \mid \\ u_1 & u_2 & \ldots & u_m \\ \mid & \mid & & \mid \end{bmatrix}\]
The SVD of \(A\) is then \[A = U \Sigma \ V^T\] where \({\displaystyle \Sigma}\) is an \(m \times n\) matrix having the structure: \[\Sigma = \begin{bmatrix} \sigma_1 & & & & \\ & \sigma_2 & & & \\ & & \ddots && \\ & & & \sigma_r & \\ & & & & 0 \end{bmatrix}_{m\times n}\]
In practice, however, we needn’t workout the eigenvectors for both \(A^TA\) and \(AA^T\). It is useful to do it only for one them. If \(m < n\), then the size of \(AA^T\) is smaller. Work out the left singular vectors \(u_i\)’s and then obtain \(r\) of the right singular vectors \(v_i\)’s using \[v_i = \dfrac{1}{\sigma_i} A^T u_i\] Then extend the set \(\{ v_1, v_2, \ldots, v_r\}\) to have \(n\) orthonormal vectors using Gram Schimdt orthogonalization.
If \(n < m\), then the size of \(A^TA\) is smaller. Work out the right singular vectors \(v_i\)’s and then obtain \(r\) of the left singular vectors \(u_i\)’s using \[u_i = \dfrac{1}{\sigma_i} A v_i\] Then extend the set \(\{ u_1, u_2, \ldots, u_r\}\) to have \(m\) orthonormal vectors using Gram Schimdt orthogonalization.
It is instructive to note that the columns of \(U\) and \(V\) give the orthonormal bases for all four fundamental subspaces of an \(m\times n\) matrix \(A\):
| first | \(r\) | columns of \(U\) : | column space of \(A\) |
| last | \(m-r\) | columns of \(U\) : | left nullspace of \(A\) |
| first | \(r\) | columns of \(V\) : | row space of \(A\) |
| last | \(n-r\) | columns of \(V\) : | nullspace of \(A\) |
We can write \(A\) as the sum of rank 1 matrices in the following way: \[A = \sigma_1 u_1v_1^T + \sigma_2 u_2v_2^T + \ldots + \sigma_r u_rv_r^T\]
Restricting the above sum to \(k\) terms (\(k \le r\)) gives the rank-\(k\) approximation of the matrix \(A\): \[A_k = \sigma_1 u_1v_1^T + \sigma_2 u_2v_2^T + \ldots + \sigma_k u_kv_k^T, \quad (k \le r)\] Specifically, the rank-1 approximation of matrix \(A\) is \[A_1 = \sigma_1 u_1 v_1^T\]
A geometrical aspect of SVD: Treat the rows of an \(m\times n\) matrix \(A\) as \(m\) points in \(n\)-dimensional space. Then for any column vector \(v\) such that \(\Vert v\Vert=1\), the quantity \(\Vert Av\Vert^2\) can be interpreted as the sum of the squared lengths of the projections of the rows of \(A\) along \(v\). And hence, the best fit line through the origin is the one maximizing \(\Vert Av\Vert^2\).
The first singular vector, \(v_1\), of \(A\), is the direction of the best fit line through the origin for the \(m\) points in the \(n\)-dimensional space that are the rows of the matrix \(A\). Thus, \[v_1 = \mathop{\mathrm{arg\,max}}_{\Vert v\Vert = 1} \Vert Av\Vert\]
The value \(\sigma_1 = \Vert Av_1\Vert\) is the first singular value of \(A\). Notice that \(\sigma_1^2\) is the sum of the projections of the points on the line determined by \(v_1\).
Similarly, the second singular vector \[v_2 = \mathop{\mathrm{arg\,max}}_{v\perp v_1, \Vert v\Vert = 1} \Vert Av\Vert\] and so on.
If the SVD of \(A=U\Sigma V^T\), then the pseudoinverse of \(A\) is \[A^\dagger = V\Sigma^\dagger U^T\] where \[\Sigma^\dagger = \begin{bmatrix} 1/\sigma_1 & & & & \\ & 1/\sigma_2 & & & \\ & & \ddots && \\ & & & 1/\sigma_r & \\ & & & & 0 \end{bmatrix}_{n\times m}\]
For any \(n\times n\) real, symmetric matrix \(A\), the product \(x^TAx\), where \(x\in \mathbb{R}^n\), is a pure quadratic form.
The real and symmetric matrix \(A\) is said to be positive definite if for every nonzero vector \(x\in \mathbb{R}^n\), \(x^TAx > 0\).
Each of the following tests is a necessary and sufficient condition for the real symmetric matrix \(A\) to be positive definite:
\(x^TAx>0\) for all non-zero vectors \(x\).
All the eigenvalues of \(A\) are positive: \(\lambda_i > 0\).
All the upper left submatrices \(A_k\) have positive determinants: \(\det(A_k) > 0\).
In the echelon form (without row exchanges) of the matrix \(A\), all the pivots entries are positive.
Each of the following tests is a necessary and sufficient condition for the real symmetric matrix \(A\) to be positive semidefinite:
\(x^TAx\ge 0\) for all vectors \(x\).
All the eigenvalues of \(A\) are nonnegative: \(\lambda_i \ge 0\).
All the principal submatrices have nonnegative determinants. A principal submatrix is obtained by eliminating some rows and the corresponding columns.
In the echelon form (without row exchanges) of the matrix \(A\), all the pivots entries are nonnegative.
For checking for negative definiteness (or negative semidefniteness) of real symmetric matrix \(A\), we can check for positive definiteness (or positive semidefiniteness) of \(-A\).
In case, the real symmetric matrix \(A\) is neither positive nor negative definite (or semidefinite), then it is an indefinite matrix.
If \(A\) is a positive definite matrix, then so are \(A^2\), \(A^3\), \(A^4\), …, and \(A^{-1}\).
If \(A\) and \(B\) are positive definite, then so is \(A+B\).