How to decompose a square matrix into two non-square matrices?

Question

I want to know if there is any method that decomposes a square matrix into two non-square matrices. Most of the methods I've seen have square matrices, upper/lower triangular matrices(LU methods) or more than two matrices(SVD) as the end result. In particular, I am looking for matrix U such that

U'*U= A

where

A=[2 -1 -1
  -1  2 -1
  -1 -1  2]

U would be a 2x3 matrix in this case.

Answer 1

This is only possible if $A$ is not full rank. In that scenario, a low-rank decomposition would be what you are looking for. Conveniently, the SVD gives you one such low-rank decomposition. If you write out the SVD $A=USV^{T}$ as

$A=\sum_{k=1}^n s_{ii}u_i v_i^{T}$

where $u_i$ and $v_i$ are the columns of $U$ and $V$, and $s_{ii}$ is the corresponding singular value, then it becomes apparent that if any of the $s_{ii}$ are zero, the equality still holds even if that term is dropped. This corresponds directly to shaving off a column from $U$ and $V$ as desired. To get it down to two matrices, you can just take $(n-1) \times (n-1)$ diagonal matrix $S$ and find an appropriate square root of it $S^{1/2}$ (which is possible since $S$ has non-zero real values) and set the two factors as $M_1=US^{1/2}$ and $M_2=VS^{1/2}$. It will only be possible to make $M_1=M_2$ if $A$ is symmetric, in which case $U=V$.

Answer 2

The SVD will give you the decomposition you want. Simply, for a symmetric matrix, $A=U\Sigma U^T$. Take only the columns of $U$ that correspond to the nonzero singular values in $\Sigma$ and multiply them by the square root of the corresponding element in $\Sigma$. In other words:

> [u s v]=svd(A);
> i=find(diag(s)>0);
> B=(u(:,i)*diag(sqrt(diag(s)(i))))'
> norm(A-B'*B)
ans =    1.9117e-15
> B
B =

  -0.27236  -1.06564   1.33800
   1.38774  -0.92974  -0.45800