10
$\begingroup$

Can I find a solution for $C_{n\times n}$, explicitly, for the given $A_{n\times n}$ and $B_{n\times n}$ such that $AA^{T} + BB^{T} = CC^{T}$? Here $A^{T}$ denotes the transpose of $A$ and all the matrices ($A$, $B$, and $C$) are real.

I think there is a solution for $C$ as there are $n^2$ unknowns (the $n^2$ components $C$) and $n^2$ equations (comparing the components of LHS and RHS).

Note: If it can not be solved (explicitly), then one can assume mild conditions (like positive definiteness, symmetry) on $A$ and $B$.

$\endgroup$
  • $\begingroup$ What is $A'$ ? The transpose of $A$ ? $\endgroup$ – Peter May 20 '18 at 18:18
1
$\begingroup$

This can always be done.

The following is, by and large, written under the assumption that the matrices are taken over the complex field, assuming that

$A' = A^\dagger, \tag 1$

that is, $A'$ denotes the adjoint matrix of $A$, which of course is the transpose of the complex conjugate:

$A^\dagger = (\bar A)^T; \tag 2$

all the key steps of the argument, however, are valid when restricted solely to the reals, provided we limit the unitary matrix $U$ of (10), which diagonalizes $AA^\dagger + BB^\dagger$, to be in fact orthogonal; that such an orthogonal $U$ exists in the real case is a well-known result; then we of course also have $\bar A = A$, so (2) becomes $A^\dagger = A^T$.

By using the notation (1) we may write the given equation as

$AA^\dagger + BB^\dagger = CC^\dagger; \tag 3$

we are given $A$ and $B$ and we seek $C$ satisfying (3).

Now for any complex matrix such as $A$ we observe that $AA^\dagger$ is self-adjoint:

$(AA^\dagger)^\dagger = (A^\dagger)^\dagger A^\dagger = AA^\dagger, \tag 4$

since

$(A^\dagger)^\dagger = A; \tag 5$

furthermore, $AA^\dagger$ is positive semidefinite, viz,

$x^\dagger (AA^\dagger x) = (x^\dagger A)(A^\dagger x) = (A^\dagger x)^\dagger (A^\dagger x) \ge 0. \tag 6$

Now the matrix $AA^\dagger + BB^\dagger$ also enjoys these two properties, self-adjointness and positive semi-definiteness, as may easily be see in a fashion similar to (4)-(6):

$(AA^\dagger + BB^\dagger)^\dagger = (AA^\dagger)^\dagger + (BB^\dagger)^\dagger = AA^\dagger + BB^\dagger, \tag 7$

where we have deployed (4), and also

$x^\dagger ((AA^\dagger + BB^\dagger)x) = x^\dagger(AA^\dagger x + BB^\dagger x) = x^\dagger(AA^\dagger x) + x^\dagger (BB^\dagger x) \ge 0, \tag 8$

since each term on the right of this equation is non-negative by way of (6).

At this point we pause to note once again that if $A$ and $B$ are real matrices, everything we have done so far still binds; in the real case, we simply have $\bar A = A$ and hence

$A^\dagger = (\bar A)^T = A^T \tag 9$

etc.

The matrix $AA^\dagger + BB^\dagger$, being self-adjoint, may diagonalized by a unitary matrix $U$, as is well-known; that is, there is a complex matrix $U$ such that

$U^\dagger U = UU^\dagger = I, \tag{10}$

and

$U(AA^\dagger + BB^\dagger)U^\dagger = D, \tag{11}$

where $D$ is a diagonal matrix; furthermore, $D$ is itself is self-adjoint:

$D^\dagger = (U^\dagger)^\dagger(AA^\dagger + BB^\dagger)^\dagger U^\dagger = U(AA^\dagger + BB^\dagger)U^\dagger = D \tag{12}$

(where we have made use of (7)), which implies that all the entries of $D$ are real; obviously, the off-diagonal elements, being $0$, are real; furthermore, the diagonal elements of $D$ satisfy

$D_{ii} = (D^\dagger)_{ii} = ((\bar D)^T)_{ii} = \bar D_{ii}, \tag{13}$

hence they are also all real, and since it follows from (8) and (11) that

$x^\dagger D x = x^\dagger U^\dagger (AA^\dagger + BB^\dagger)Ux = (Ux)^\dagger (AA^\dagger + BB^\dagger)Ux \ge 0; \tag{14}$

we thus find that $D$ is positive semi-definite, and from here it is but an easy step to see that the diagonal entries of $D$ obey

$D_{ii} \ge 0. \tag{15}$

By virtue of (15) we may define the diagonal matrix $\sqrt D$ such that

$(\sqrt D)_{ij} = [\delta_{ij} (\sqrt D)_{ii}]; \tag{16}$

it is clear that

$(\sqrt D)^\dagger = \sqrt D, \tag{17}$

and furthermore that

$(\sqrt D)^2 = D; \tag{18}$

thus, from (11),

$(U^\dagger \sqrt D U)(U^\dagger \sqrt D U) = U^\dagger \sqrt D UU^\dagger \sqrt D U = U\dagger \sqrt D I \sqrt D U = U^\dagger (\sqrt D)^2 U = U^\dagger D U$ $= U^\dagger (U(AA^\dagger + BB^\dagger)U^\dagger)U = (U^\dagger U)(AA^\dagger + BB^\dagger)(U^\dagger U)$ $= I(AA^\dagger + BB^\dagger)I = AA^\dagger + BB^\dagger; \tag{19}$

if we now set

$C = U^\dagger \sqrt D U, \tag{20}$

we see that $C$ is self-adjoint:

$C^\dagger = (U^\dagger \sqrt D U)^\dagger = U^\dagger (\sqrt D)^\dagger (U^\dagger)^\dagger = U^\dagger \sqrt D U = C, \tag{21}$

and (19) yields

$C^\dagger C = C^2 = ( U^\dagger \sqrt D U)^2 = AA^\dagger + BB^\dagger, \tag{22}$

as desired. We note that the procedure followed above provides a de facto recipe for explicitly computing $C$.

$\endgroup$
2
$\begingroup$

I think you are saying: if we know A and B can we find a C such that the equation holds.

A Hermitian Positive Definite matrix M has a Cholesky decomposition $M=CC^{\ast}$. So, if $AA^T+BB^T$ is positive definite symmetric (implying real), then a C exists that satisfies the equation.

A sufficient condition is that A and B are both positive definite.

$\endgroup$
  • $\begingroup$ I think $AA^{T}$ and $BB^{T}$ are positive semi-definite matrices by construction. And the sum of two positive semi-definite matrices is also positive semi-definite. Hence I can find a $C$ using the Cholesky's decomposition of $(AA^{T} + BB^{T})$. Is the sufficient condition of positive definiteness of $A$ and $B$ necessary? $\endgroup$ – Shanks May 20 '18 at 21:05
  • $\begingroup$ @Shanks I don't know if its enough to be positive semidefinite to guarantee a Cholesky Decomposition. That is, I don't know if a positive semi-definite matrix always has a Cholesky decomposition. $\endgroup$ – NicNic8 May 20 '18 at 22:16
  • $\begingroup$ I think this will be a useful link: eprints.ma.man.ac.uk/1193/1/covered/MIMS_ep2008_56.pdf $\endgroup$ – Shanks May 20 '18 at 22:47
0
$\begingroup$

We assume that the matrices are real.

About a (false) remark by the OP; in fact, we consider a system of only $\approx n^2/2$ equations in $n^2$ unknowns, because $S=AA^T+BB^T$ is symmetric. Thus, there are an infinity of solutions (except when $A=B=0$).

In general, $\ker(A^T)\cap \ker(B^T)=\{0\}$ and $S$ is symmetric $>0$; note that there are two particular solutions that are interesting:

The symmetric $>0$ matrix $C=S^{1/2}$ and the triangular matrix $C$ obtained by the standard Choleski method.

Exceptionally, $S$ is not invertible; in this case, we can again calculate the above two matrices $C$, the second one, using the extended Choleski method. About that, the OP gave a good reference (dated 1990) by Higham. Higham is a very good mathematician who also writes very well; he has written a book on this subject that I recommend everyone read:

Handbook of writing for the mathematical sciences, Siam.

Our friend @Robert Lewis also writes perfectly; I do not know if he read this book...

Remark. Higham, as many other researchers, uses the expression "positive semidefinite". In my opinion, it's a fault of English; we should say "non-negative semidefinite"...

$\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.