--- title: "Simultaneous Diagonalization of Positive Semi-definite Matrices" author: "Jan de Leeuw" date: "Version 21, May 21, 2017" output: html_document: keep_md: yes number_sections: yes toc: yes pdf_document: keep_tex: yes number_sections: yes toc: yes toc_depth: 3 fontsize: 12pt graphics: yes bibliography: simul.bib abstract: We give necessary and sufficient conditions for solvability of $A_j=XW_jX'$, with the $A_j$ are $m$ given positive semi-definite matrices of order $n$. The solution $X$ is $n\times p$ and the $m$ solutions $W_j$ are required to be diagonal, positive semi-definite, and adding up to the identity. We do not require that $p\leq n$. --- {r function_code, echo = FALSE} #source("twogroup.R")  {r packages, echo = FALSE} options (digits = 10) library (captioner) mprint <- function (x, d = 6, w = 8, f = "") { print (noquote (formatC ( x, di = d, wi = w, fo = "f", flag = f ))) }  {r equation_numbering, echo = FALSE} figure_nums <- captioner (prefix = "Figure") theorem_nums <- captioner (prefix = "Theorem") lemma_nums <- captioner (prefix = "Lemma") corollary_nums <- captioner (prefix = "Corollary") definition_nums <- captioner (prefix = "Defintion") theorem_nums(name="lrank", caption = "[lrank]", display = FALSE) theorem_nums(name="drank", caption = "[drank]", display = FALSE) definition_nums(name="lrank", caption = "[lrank]", display = FALSE) definition_nums(name="drank", caption = "[drank]", display = FALSE) definition_nums(name="pextension", caption = "[pextension]", display = FALSE) lemma_nums(name="diagonal", caption = "[diagonal]", display = FALSE) lemma_nums(name="crossprod", caption = "[crossprod]", display = FALSE) lemma_nums(name="simultaneous", caption = "[simultaneous]", display = FALSE) lemma_nums(name="commute", caption = "[commute]", display = FALSE) corollary_nums(name="smalldrank", caption = "[small_d_rank]", display = FALSE) corollary_nums(name="m2", caption = "[m=2]", display = FALSE)  Note: This is a working paper which will be expanded/updated frequently. All suggestions for improvement are welcome. The directory [gifi.stat.ucla.edu/simul](http://gifi.stat.ucla.edu/simul) has a pdf version, the complete Rmd file, and the bib file. #Introduction There is by now a large literature on simultaneous diagonalization of matrices. The topic is of importance in blind source separation, chemometrics, psychometrics, nonlinear optimization, multilinear algebra, fast matrix multiplication, and quantum physics. We have no intention of giving a complete overview of the literature, our purpose is mainly to present and generalize the approach of @deleeuw_pruzansky_78. The problem is the following. If $A_1,\cdots,A_m$ are real symmetric matrices of order $n$, then we want to solve the system of equations $A_j=XW_jX'$, where $X$ is any $n\times p$ matrix and where the $W_j$ are diagonal of order $p$. In this paper we will restrict our attention to the case in which the $A_j$ are positive semi-definite and in which we require the $W_j$ to be positive semi-definite as well. There are several important special cases that can be distinguished. If $p\leq n$ then @schoenemann_72 presented the main algebraic result, in the context of psychometric data analysis. His computational approach, however, left something to be desired, and consequently it was improved, generalized, and implemented by @deleeuw_pruzansky_78. We also note the special case in which $m=2$, in which some additional results can be obtained (@deleeuw_A_82b). In this paper we generalize the approach of @schoenemann_72 and @deleeuw_pruzansky_78 to the case where we do not necessarily have $p\leq n$. As in the more restrictive case, we start by studying the decomposition $A_j=XW_jX'$ without the requirement that the $W_j$ are diagonal. We give necessary and sufficient conditions for the set of solutions to be non-empty, and we describe the complete set of solutions in the case in which the system is solvable. We then characterize the solutions, if any, in the set of all solutions which have diagonal $W_j$. #l-rank Start with a convenient defintion of the rank of a sequence of positive semi-definite matrices. **r definition_nums("lrank")** Suppose $A_j$ are $m$ positive semi-definite matrices of order $n$. The tuple $(A_1,\cdots,A_m)$ has *l-rank* less than or equal to $p$ if there is an $n\times p$ matrix $X$ and there are $p\times p$ positive semi-definite matrices $W_j$, with sum $W_\bullet=I$, such that $A_j=XW_jX'$. It has l-rank equal to $p$ if it has l-rank less than or equal to $p$, but not less than or equal to $p-1$. Note that we allow for $p>n$. It may not be immediately obvious why we require $W_\bullet=I$. Suppose $W_\bullet$ has rank $rn$. Clearly l-rank is less than or equal to d-rank, which implies by theorem r theorem_nums("lrank", display = "n") that d-rank is larger than or equal to $r=\mathbf{rank}(A_\bullet)$. In order to proceed we need another definition. **r definition_nums("pextension")** Any $p\times p$ symmetric matrix of order $p$ which has the $r\times r$ matrix $A$ as its leading principal submatrix is a *p-extension* of $A$. **r theorem_nums("drank")** The d-rank of $(A_1,\cdots.A_m)$ is less than or equal to $p$ if and only if there exist for each $j=1,\cdots,m$ pairwise commuting positive semi-definite p-extensions $C_j$ of $B_j=\Lambda^{-1}K'A_jK\Lambda^{-1}$ that add up to one. **Proof:** Equation $\eqref{E:wform}$ in the proof of theorem r theorem_nums("lrank", display = "n") shows there must exist $U_j$ and $V_j$ such that $$\begin{bmatrix}\Lambda^{-1}K'A_jK\Lambda^{-1}&U_j\\U_j'&V_j\end{bmatrix}=\begin{bmatrix}L'\\L_\perp'\end{bmatrix}W_j\begin{bmatrix}L&L_\perp\end{bmatrix}$$ But this is the same as saying there must be p-extensions of the $B_j$ that commute. **QED** It seems that in general for $p>n$ and $m>2$ commuting p-extensions are difficult to work with. But in some cases theorem r theorem_nums("drank", display = "n") simplifies. **r corollary_nums("smalldrank")** The d-rank of $(A_1,\cdots,A_m)$ is $r=\mathbf{rank}(A_\bullet)$ if and only if $A_jA_\bullet^+A_\ell=A_\ell A_\bullet^+A_j$ for all $j,\ell$. **Proof:** The $\Lambda^{-1}K'A_jK\Lambda^{-1}$ must commute without any p-extension. This translates to the condition in the theorem. **QED** Finally, we also have as a corollary a version of the basic result of @deleeuw_A_82b. **r corollary_nums("m2")** The d-rank of $(A_1,A_2)$ is $\mathbf{rank}(A_1+A_2)$. **Proof:** Because $\Lambda^{-1}K'A_1K\Lambda^{-1}+\Lambda^{-1}K'A_2K\Lambda^{-1}=I$ we see from lemma r lemma_nums("commute", display = "n") that $\Lambda^{-1}K'A_1K\Lambda^{-1}$ and $\Lambda^{-1}K'A_2K\Lambda^{-1}$ commute. **QED** #Appendix: Some Lemmas **r lemma_nums("diagonal")** If $A$ is positive semi-definite and $a_{ii}=0$ then $a_{ij}=a_{ji}=0$ for all $j$. **Proof:** Suppose $$A=\begin{bmatrix}0&r'\\r&S\end{bmatrix}$$ is positive semi-definite. Define $z=\begin{bmatrix}1&-\epsilon r\end{bmatrix}$ with $\epsilon>0$. Then $z'Az=-2\epsilon r'r+\epsilon^2r'Sr$. If $r'Sr=0$ and $r'r>0$ then $z'Az<0$ for all $\epsilon>0$, which contradicts that $A$ is positive semi-definite. If $r'Sr>0$ and $r'r>0$ then $$\min_{\epsilon>0}z'Az=-\frac{(r'r)^2}{r'Sr}<0,$$ which again contradicts that $A$ is positive semi-definite. Thus $r'r=0$, i.e. $r=0$. **QED** **r lemma_nums("crossprod")** Suppose the positive semi-definite matrix $A$ of order $n$ has eigenvalue decomposition $$A=\begin{bmatrix}K&K_\perp\end{bmatrix}\begin{bmatrix}\Lambda^2&0\\0&0\end{bmatrix}\begin{bmatrix}K'\\K_\perp'\end{bmatrix},$$ with $\Lambda^2$ a positive definite diagonal matrix of order $r=\mathbf{rank}(A)$. The equation $A=XX'$, with $X$ an $n\times p$ matrix has a solution if and only if $p\geq r$. All solutions are of the form $X=K\Lambda L'$, with $L$ is a $p\times r$ orthonormal matrix. **Proof:** Write $X$ as $$X=\begin{bmatrix}K&K_\perp\end{bmatrix}\begin{bmatrix}U\\V\end{bmatrix},$$ which gives $$XX'=\begin{bmatrix}K&K_\perp\end{bmatrix}\begin{bmatrix}UU'&UV'\\VU'&VV'\end{bmatrix}\begin{bmatrix}K'\\K_\perp'\end{bmatrix}.$$ Thus $XX'=A_\bullet$ if and only if $V=0$ and $UU'=\Lambda$. It follows that $X=K\Lambda L'$, with a $p\times r$ orthonormal $L$. Also $\mathbf{rank}(X)=\mathbf{rank}(A_\bullet)=r$ and $p\geq r$. **QED** **r lemma_nums("simultaneous")** Suppose $(A_1,\cdots,A_m)$ is a sequence of real symmetric matrices of order $n$. Then there exist a square orthonormal $X$ and diagonal $W_j$ such that $A_j=XW_jX'$ if and only if the $A_j$ commute in pairs, i.e. if and only if $A_jA_\ell=A_\ell A_j$ for all $j\not=\ell$. **Proof:** It is obvious that simultaneously diagonalizability implies that the $A_j$ commute in pairs. The interesting part of the proof is to show that pairwise commuting implies simultaneous diagonalizability. The standard proof, repeated most recently in @jiang_li_16, uses induction, starting from the fact that the lemma is trivially true for $m=1$. We give the proof in our notation and make it perhaps a bit more explicit and computational. So let us suppose the real symmetric matrices $(A_1,\cdots,A_m)$ commute in pairs. And suppose $A_m$ has eigenvalue decomposition $$A_m=\begin{bmatrix}K_1&K_2&\cdots&K_r\end{bmatrix}\begin{bmatrix}\lambda_1I&0&\cdots&0\\0&\lambda_2I&\cdots&\cdots\\\vdots&\vdots&\ddots&\vdots\\0&0&\cdots&\lambda_rI\end{bmatrix} \begin{bmatrix}K_1'\\K_2'\\\vdots\\K_r'\end{bmatrix},$$ with all $\lambda_s$ different. Set $K:=\begin{bmatrix}K_1&K_2&\cdots&K_r\end{bmatrix}$. Then for all $j=1,\cdots,m-1$ $$A_mA_jK_s=A_jA_mK_s=\lambda_1A_jK_s$$ and thus $A_jK_s$ are eigenvectors of $A_m$ with eigenvalue $\lambda_s$, i.e. $A_jK_s=K_s(K_s'A_jK_s)$. Write this as $$K'A_jK=\begin{bmatrix}K_1'A_jK_1&0&\cdots&0\\0&K_2'A_jK_2&\cdots&\cdots\\\vdots&\vdots&\ddots&\vdots\\0&0&\cdots&K_r'A_jK_r\end{bmatrix}.$$ Now obviously the matrices $K'A_jK$ commute in pairs, which implies that that the $m-1$ matrices $(K_s'A_1K_s,\cdots,K_s'A_{m-1}K_s)$ commute in pairs for each $s$. By the induction hypothesis there are square orthonormal $L_s$ and diagonal $\Phi_{js}$ such that $K_s'A_jK_s=L_s\Phi_{js} L_s'$. Define $L:=\begin{bmatrix}L_1&L_2&\cdots&L_r\end{bmatrix}$. Then $$L'K'A_jKL=\begin{bmatrix}\Phi_{j1}&0&\cdots&0\\0&\Phi_{j2}&\cdots&\cdots\\\vdots&\vdots&\ddots&\vdots\\0&0&\cdots&\Phi_{jr}\end{bmatrix},$$ for $j=1,\cdots,m-1$, while of course $$L'K'A_jKL=\begin{bmatrix}\lambda_1I&0&\cdots&0\\0&\lambda_2I&\cdots&\cdots\\\vdots&\vdots&\ddots&\vdots\\0&0&\cdots&\lambda_rI\end{bmatrix}.$$ **QED** **r lemma_nums("commute")** If $A$ and $B$ are symmetric matrices with $A+B=I$ then $A$ and $B$ commute. **Proof:** $AB=A(I-A)=A-A^2$, which is symmetric. Another way to see this is that $A$ and $B=I-A$ have the same eigenvectors $L$, and $L$ diagonalizes both matrices. **QED** #References