3
$\begingroup$

I hope my question is trivial for some of you but for the time being I’m lost somewhere between the generalized eigenproblem, simultaneous diagonalization of quadratic forms, simultaneous SVD, generalized SVD, etc., none of them matching my problem.

Let $A$ and $B$ be two symmetric, positive semi-definite (but not positive-definite) matrices in ${\mathbb{R}^{n \times n}}$. $\left[ {A,B} \right] \ne 0$ . Both of them are diagonalizable, one of them is diagonal. Find a pair of non-singular matrices $P$ and $Q$ such as

$\left\{ \begin{gathered} PAQ = {D_1} \hfill \\ PBQ = {D_2} \hfill \\ \end{gathered} \right.$

${D_1}$ and ${D_2}$ diagonal. No other property of $P$ and $Q$ is required.

$\endgroup$
  • 1
    $\begingroup$ What do you want to know about this problem? If its solution always exists? Or how to compute $D_1,D_2$ numerically? $\endgroup$ – Federico Poloni Apr 2 '18 at 9:48
4
$\begingroup$

From the theoretical point of view: there is a Jordan-like canonical form for pairs of Hermitian matrices $(A,B)$ under the equivalence relation $(A,B) \sim (PAP^T, PBP^T)$ (with a nonsingular $P$), see https://www.sciencedirect.com/science/article/pii/0024379576900215 . This is known today in my area as "(a variant of) the even Kronecker canonical form"; see e.g. my paper https://doi.org/10.1137/120861679 which contains a self-contained statement for Hermitian-anti-Hermitian (which is the same up to multiplication by $i$ of one of them).

It is easy to check that only a few of these blocks can be used to produce positive semidefinite $A$ and $B$: if I am not wrong, if $A,B$ are spd then you can only get in the canonical form size-1 blocks corresponding to purely real eigenvalues (E2), size-1 blocks corresponding to infinite eigenvalues (E3), and size-1 singular blocks (E4, corresponding to common kernel of the two matrices). All these blocks are size-1: in particular, this means that this decomposition will produce diagonal $PAP^T,PBP^T$, and hence it is the decomposition that you want. I.e., the form that you ask for exists for all pairs $(A,B)$, and you can obtain it even if you restrict to transformations with $Q=P^T$ (which is nice, since they preserve symmetry and definiteness).

Numerically, you can first identify the common kernel of $A$ and $B$ and then change basis to put it in evidence, to reduce the problem to $$ \begin{bmatrix}A_{11} & 0\\ 0 & 0\end{bmatrix}, \begin{bmatrix}B_{11} & 0\\ 0 & 0\end{bmatrix} $$ and then apply a generalized eigensolver (e.g., Matlab's eig(A11, B11)) to $A_{11}$ and $B_{11}$, which is now a nonsingular problem (i.e., $\det(A+Bz)$ is not identically zero) in view of the previous discussion.

$\endgroup$
  • 1
    $\begingroup$ @Frederico Thank you very much for your input. Give me some time to check your paper and I'll come back to you... In the meantime, to answer your comment, I'm interested in both: conditions on $A$ and $B$ for the existence of $D_1$, $D_2$, $P$ and $Q$ and numerical algorithms for computing them. I'm interested in exact and approximate solutions, minimizing off-diagonal elements. $\endgroup$ – Fabrice Pautot Apr 2 '18 at 11:45
  • $\begingroup$ @FabricePautot I have expanded my answer. $\endgroup$ – Federico Poloni Apr 2 '18 at 19:45
  • $\begingroup$ @Frederico I'm unfortunately unable to follow you, I probably miss something: the common kernel of my $A$ and $B$ is $\emptyset $ so that my pencil $A + Bz$ is already regular. Should $A$ or $B$ be pd/nonsingular then $D_1$ or $D_2$ can be set to $I_n$ so that $P$ are the generalized eigenvectors of $A$ and $B$. But when both $A$ and $B$ are spd/singular, the relationship between simultaneous diagonalization and the generalized eigenproblem is no more clear: basically, we would use reduced rank simultaneous diagonalization, but that's not what I need. $\endgroup$ – Fabrice Pautot Apr 3 '18 at 10:28
  • $\begingroup$ @FabricePautot Why do you say that when both $A$ and $B$ are singular the relationship between simultaneous diagonalization and the generalized eigenproblem is no more clear? It's exactly the same thing: there are two matrices $P,Q$ (containing left and right eigenvectors) such that $PAQ$ and $PBQ$ are diagonal. What is "reduced rank simultaneous diagonalization"? $\endgroup$ – Federico Poloni Apr 3 '18 at 12:40
  • $\begingroup$ @Frederico Grazie Mille. Ah, it seems like I was fooled by some numerical instabilities because $PAQ$ and $PBQ$ as obtained from Matlab eig(A,B) are not diagonal... $\endgroup$ – Fabrice Pautot Apr 3 '18 at 13:43

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.