9
$\begingroup$

Let $M \in \mathbb{R}^{k\times k}$ positive definite with $\operatorname{tr} M = m$, where $m$ is an integer such that $m \geq k$. I have found a way (using this answer) to decompose $M = AA^t$ with $A \in \mathbb{R}^{k \times m}$ such that $A = (a_1, \dots, a_m), a_i \in \mathbb{R}^k$ and $\|a_i\|_2 = 1, i=1,\dots,m$.

  1. Is there a name for such a decomposition? This is not Cholesky, although it looks similar.
  2. Is this decomposition unique? We can always take $\hat{A} := AD$ where $D$ is a permutation matrix with $\pm 1$ entries. Then $\hat{A}\hat{A}^t = M$ and $\hat{A}$'s columns have unit norm. I am not sure if there is any other obstruction to uniqueness.
  3. In my numerical experiments, I find that the some columns of $A$ are identical (up to a sign). Any reason for that?

Example

Let $M =diag(1.5,1.5)$. One can verify that $M=AA^t$ for

$$ A = \begin{pmatrix} \sqrt{3/4}& \sqrt{3/4}& 0 \\ -1/2& 1/2 & 1\\ \end{pmatrix} $$ P.S. The assumption on the trace above is necessary because $\text{tr} M = \text{tr} AA^t = \text{tr}A^tA$ and $A^tA\in \mathbb{R}^{m \times m}$ has unit diagonal.

Reference

Using Raphael's answer below I was able to find the reference:

Peter A. Fillmore, On sums of projections, Journal of functional analysis 4, 146-152 (1969).

$\endgroup$
16
  • $\begingroup$ @FedericoPoloni apart from positivity the OP is imposing a limit on $\mid M \mid$ by $|a_i|_2=1$. so it is unlike that every arbitrary positive matrix $M$ can be decomposed in the way OP required. he actually impose a boundedness condition on M. $\endgroup$ Oct 30 '20 at 18:56
  • 3
    $\begingroup$ @AliTaghavi Positive semidefinite + trace=m defines a bounded set. Once one assumes positivity I don't see any obvious obstructions to that kind of factorization. $\endgroup$ Oct 30 '20 at 19:11
  • 4
    $\begingroup$ In item 2, when you say "unique", do you mean "up to replacing $A$ by $AC$ where $C$ is orthonormal"? (If not, the decomposition is heavily non-unique even for $m=k$ and $M = I_m$.) $\endgroup$ Oct 30 '20 at 19:23
  • 1
    $\begingroup$ @AliTaghavi: I don't know what you mean. What I'm saying is that if $m = k$ and $M = I_m$, then $A$ can be any orthonormal $m\times m$-matrix. $\endgroup$ Oct 30 '20 at 22:35
  • 1
    $\begingroup$ What about $D$ a permurtation matrix? $\endgroup$
    – RaphaelB4
    Nov 8 '20 at 7:57
2
+50
$\begingroup$

This decomposition is equivalent to write $M$ as a sum of rank one orthogonal projection $$ M = \sum_{i=1}^m a_i a_i^* $$ with $\|a_i\|=1$. Indeed for any $x$ we have $$(Mx)_{s} = \sum_{i\leq m,t\leq k} A_{si}A^T_{it}x_t = \sum_{i\leq m} (a_i)_s \langle a_i,x\rangle $$ Remark that in form it is easy to see the invariance by permutation with $\pm 1$ entries and that $\text{Tr}(M)=m$.

We can consider the application $\phi:(\mathbb{S}^{k-1})^m\rightarrow \mathbb{R}^{k\times k}$, $\phi(a_1,\cdots,a_m)=AA^T=M$. Because $(\mathbb{S}^{k-1})^m$ is a manifold of dimension $m(k-1)$ and the subset of symetric matrices of trace $m$ is a manifold of dimension $\frac{k(k+1)}{2}-1$. It is clear that we don't have unicity in the general case if $m> \frac{k^2+k-2}{2(k-1)}=\frac{k+2}{2}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.