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, 2020 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, 2020 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, 2020 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, 2020 at 22:35
  • 1
    $\begingroup$ What about $D$ a permurtation matrix? $\endgroup$
    – RaphaelB4
    Nov 8, 2020 at 7:57

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .