# Solve $X^TX=A$ for $X$

Given symmetric matrix $$A \in \Bbb R^{n \times n}$$, how does one solve the following quadratic matrix equation in matrix $$X \in \Bbb R^{m \times n}$$?

$$X^T X = A$$

I know this must be simple, but I have been wrestling with it for some time now. Thanks in advance for any help.

• Have you tried to solve it for $n=1$ or $n=2$? What did you get? Jul 21, 2018 at 19:38
• I don't understand the $\mbox{rank}(A) < \min(m,n)$ part, so I removed it. Oct 11, 2022 at 11:09

Since $$A$$ is symmetric $$n \times n$$, we can write it as $$A=Q \Lambda Q^T$$, where $$Q$$ is an orthogonal matrix whose columns are the eigenvectors of $$A$$, and $$\Lambda$$ is a diagonal matrix whose entries are the eigenvalues of $$A$$.

We want to decompose $$A=X^TX$$, where $$X$$ is $$m \times n$$.

Let $$\mathbf{rank}(A)=r<\min(m, n)$$, therefore, $$A$$ is not full rank and have $$n-r$$ eigenvalues equal to $$0$$.

Thus, we can form and $$n \times r$$ matrix $$\tilde{Q}$$ by deleting the columns of $$Q$$ corresponding to the eigenvectors associated to the eigenvalues equal to $$0$$, and also form $$\tilde{\Lambda}$$, an $$r \times r$$ diagonal matrix whose entries are the non-zero eigenvalues of $$A$$. Thus, we have $$A=\tilde{Q} \tilde{\Lambda} \tilde{Q}^T = \tilde{Q} \sqrt{\tilde{\Lambda}} \sqrt{\tilde{\Lambda}} \tilde{Q}^T = (\sqrt{\tilde{\Lambda}} \tilde{Q}^T)^T \sqrt{\tilde{\Lambda}} \tilde{Q}^T = X^TX,$$

where $$X := \sqrt{\tilde{\Lambda}} \tilde{Q}^T$$, with dimensions $$r \times n$$.

The only problem is that $$\mathbf{rank}(A)=r=\min(m, n)$$, for $$m=r$$. To solve this issue, when forming $$\tilde{Q}$$, delete all but one of the columns of $$Q$$ corresponding eigenvectors associated to the eigenvalues equal to $$0$$. Doing this, $$X$$ will end up with dimensions $$(r+1) \times n$$, satisfying the inequality $$\mathbf{rank}(A)=r<\min(m, n)$$, for $$m=r+1$$.

• Great explanation, thank you. Jul 23, 2018 at 19:35

The solution can only exist for symmetric $A$. We can then write $A=O^T DO$ with $D$ diagonal (and with non-negative eigenvalues) and $O$ orthogonal. We can then define a square root of $D$ in the obvious way, obtaining $X=\sqrt{D}O$ as one solution. For orthogonal $O'$, a more general solution is $X=O'\sqrt{D}O$.

• Thanks for the answer. I am interested in cases where A is not square and potentially not full rank, meaning that svd must be used in lieu of eigendecomposition. In this case, we cannot write A as $O^TDO$. Jul 21, 2018 at 9:02
• @MichaelNew But $X^T X=A$ implies $A^T =A$. You're allowed $0$ as an eigenvalue, though.
– J.G.
Jul 21, 2018 at 9:16
• Symmetric is not enough. Solvable iff $A$ is positive semidefinte.
– A.Γ.
Jul 21, 2018 at 11:25
• @A.Γ., how solvability helps to decompose A? Oct 11, 2020 at 20:43

Assume $m=n$. The rows of $X$ are some $n$ vectors in $\mathbb{R}^n$, say, $v_1,\dots, v_n$. The $(i,j)$ element of $X^tX$ is the inner product $v_i\cdot v_j$. So there are at most ${n\choose 2}+n$ different entries in $X^tX$, but $n^2$ possible entries in a general $n\times n$ matrix $A$. As a result, one cannot expect to solve the equation $X^tX=A$ for every $A$.

• You are missing the fact that the rank of A is less than the (maximum possible) rank of X. I also forgot to specify that A is symmetrical, apologies for that (now included in the question). There is guaranteed to be a solution, I am just having trouble solving for it. Jul 21, 2018 at 8:24

I propose a solution of the case where potentially $$m \gg n$$.

Assume that $$\mathbf A$$ is positive semidefinite. By eigendecomposition, $$\mathbf A = \mathbf Q\mathbf S\mathbf Q^\top$$ where $$\mathbf Q$$ is an orthonormal matrix of shape $$n \times n$$. Consider another decomposition of $$\mathbf A$$ such that $$\mathbf A = \mathbf P|\mathbf M|^2\mathbf P^\top$$ where $$|\mathbf M|^2$$ is diagonal and $$\mathbf P$$ is an $$n \times m$$ matrix ($$m > n$$) defined as $$\mathbf P \triangleq \mathbf Q\boldsymbol\Pi^\top$$. Thus, if $$\mathbf X^\top \mathbf X = \mathbf A$$, then $$\mathbf X = |\mathbf M|\boldsymbol\Pi\mathbf Q^\top$$. Since $$\mathbf Q$$ is known given $$\mathbf A$$, we need only to find $$|\mathbf M|$$ and $$\boldsymbol\Pi$$.

$$\mathbf Q\mathbf S\mathbf Q^\top = \mathbf P|\mathbf M|^2\mathbf P^\top = \mathbf Q\boldsymbol\Pi^\top|\mathbf M|^2\boldsymbol\Pi\mathbf Q^\top$$

Naturally, our objective is to minimize $$L(|\mathbf M|,\boldsymbol\Pi)=\|\boldsymbol\Pi^\top|\mathbf M|^2\boldsymbol\Pi-\mathbf S\|_F^2$$, where $$\|\cdot\|_F$$ is the Frobenius norm. We need also apply an orthogonal constraint $$\boldsymbol\Pi^\top\boldsymbol\Pi=\mathbf I$$ to ensure that the column space of $$\mathbf P$$ is necessarily isometric to that of $$\mathbf Q$$. To apply orthogonal constraint in gradient method, see Section 1.1 Constraint-Preserving Update of this paper (too long to put it here).

The solution to such optimization could be nonunique (or must be nonunique?), but we may find a particular solution using coordinate gradient descent, namely first find a feasible $$\boldsymbol\Pi_0$$, fix $$\boldsymbol\Pi_0$$ and find a better $$|\mathbf M_1|$$, fix $$|\mathbf M_1|$$ and find a better $$\boldsymbol\Pi_1$$ subject to the constraint, fix $$\boldsymbol\Pi_1$$ and find a better $$|\mathbf M_2|$$, fix $$|\mathbf M_2|$$ and find a better $$\boldsymbol\Pi_2$$, etc. We may use one-step gradient descent (given a small learning rate) for each optimization step. To find the first feasible $$\boldsymbol\Pi_0$$, one may look into the doc of scipy.stats.ortho_group.

For the implementation, we may resort to PyTorch, which does the gradient things for us.

For example, given

$$\mathbf A = \begin{pmatrix} 0.38672121 & -0.72476649\\ -0.72476649 & 2.58435428\\ \end{pmatrix}\,,$$

here is what such algorithm gives for $$m=10$$:

$$\mathbf X = \begin{pmatrix} 3.02239738\times 10^{-1}& 8.15764615\times 10^{-2}\\ 1.55106782\times 10^{-1}& 1.21846205\times 10^{-1}\\ 4.31693560\times 10^{-2}&-3.22591722\times 10^{-1}\\ 9.10323361\times 10^{-2}&-2.12030684\times 10^{-1}\\ -1.48292760\times 10^{-2}&-7.20156447\times 10^{-2}\\ -1.26908969\times 10^{-1}&-1.17936127\times 10^{-1}\\ 1.47863458\times 10^{-1}&-2.93733723\times 10^{-1}\\ -5.72824350\times 10^{-2}&-6.42074711\times 10^{-2}\\ 4.68723305\times 10^{-1}&-1.51760316\times 10^{+0}\\ -9.26707466\times 10^{-4}& 3.47160090\times 10^{-2}\\ \end{pmatrix}\,.$$

One may verify that $$\mathbf X^\top \mathbf X$$ is numerically closed to $$\mathbf A$$.