Every real square matrix $M$ has a QR decomposition $M = QR$ where $Q^{-1}=Q^T$ and $R$ is an upper triangular matrix with non-negative reals on the diagonal. Call the function $f(QR)=RQ$ the Francis function. The Francis function is continuous over invertible matrices, and is well-behaved in a certain way over PSD matrices (see my video series; I'm not sure how to describe it formally). Is there a functional square root of the Francis function over PSD matrices? My visualisations suggest that there could be one.
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Is your Francis function uniquely defined if $M$ is singular? $\endgroup$– Paul TupperCommented Mar 20, 2022 at 21:15
-
1$\begingroup$ Does anyone know how to describe in formal terms how the "Francis function" is well-behaved over PSD matrices? $\endgroup$– Todd TrimbleCommented Mar 21, 2022 at 0:17
-
$\begingroup$ @GottfriedHelms The QR decomposition is only unique subject to the requirement that the diagonal entries of R be positive. This should be easy to fix in Matlab or Numpy, or whatever software you're using $\endgroup$– wladCommented Mar 26, 2022 at 16:00
-
$\begingroup$ @GottfriedHelms Make sure that the matrix R you get from your different algorithms has positive entries along its diagonal. $\endgroup$– wladCommented Mar 26, 2022 at 16:16
-
$\begingroup$ Uniqueness proof: $QR = Q'R'$ implies $Q^TQ' = R(R')^{-1}$. The LHS is orthogonal, and the RHS is upper triangular. By the orthogonality property, the inverse of the RHS is its transpose. But the inverse of an upper triangular matrix is upper triangular. Therefore the transpose of the RHS is upper triangular. Therefore the RHS is diagonal. A diagonal matrix which is orthogonal has $\pm 1$ along its diagonal. Therefore $R = R' \operatorname{diag}(\pm 1, \pm 1, \dotsc, \pm 1)$. Recall the claim about what $R$ is unique up to. From this, uniqueness of $Q$ is easy to show under the same conditions $\endgroup$– wladCommented Mar 26, 2022 at 16:28
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Look for the Toda flow; that should do exactly what you want.
answered Mar 20, 2022 at 22:31
$\begingroup$
$\endgroup$
Let $L_{n\times n}=L(t)$ being a real or complex matrix, with $t$ being a real number. You can define $$B(t)=L^*(t)_+-L(t)_-,$$ in which $L_+$ is the upper triangular part, and $L_-$ is the low triangular part of the matrix $L$, without the diagonal. It follows that $B^*=-B$.
Let us consider the function $U(t)$ as the solution to the initial value problem $$\frac{d\,U}{dt}=BU,\qquad U(0)=I,$$ in wich $I$ denotes the identity $n\times n$ matrix.
This means that $$\frac{d\,U^*U}{dt}=\left(\frac{d\,U}{dt}\right)^*U+U^*\frac{d\,U}{dt}=(BU)^*U+U^*BU=-U^*BU+U^*BU=0,$$ and follows that $U^*(t)U(t)=U^*(0)U(0)=I$, that is, $U(t)$ and $Q(t)=U^*(t)$ are bounded orthogonal matrix to each $t\in \mathbb{R}$.
It follows that the initial value problem $$\frac{d\,L}{dt}=BL-LB,\qquad L(0)=L_0,$$ has a unique solution $$L(t)=Q^*(t)L_0Q(t).$$
Lemma: If $L_0=L_0^*$, then $L(t)$ converges to a diagonal matrix, containing each eigenvalues of $L_0$, as $|t|\to \infty$.
Now, if you let $$B=B(t)=\left[G(L(t))^*\right]_+-G(L(t))_-,$$ to some analytical function $G(z)$, to $z$ in an open set of $\mathbb{C}$, containig the eigenvalues of $L_0$. It follows that $B^*=-B$, and that $$M(t)=G(L(t))=U(t)G(L_0)U^*(t)$$ is the solution to the initial value problem $$ \frac{d\,M}{dt}=BM-MB,\qquad M(0)=G(L_0).$$
Lemma: If $L_0=L_0^*$ and $G(z)$ is real and one to one. Then $e^{tG(L_0)}=Q(t)R(t)$, in which $R(t)$ is upper triangular with positive diagonal.
Theorem: $e^{G(L(m))}$ is the m-th iteration to the $QR$ iteration to $e^{G(L_0)}$. In particular, if $L_0=\pm A^*A$, we can choose $G(z)=\ln(\pm z)$.
You can find details in the paper "Nanda, T., Differential Equations and the QR Algorithm, SIAM Journal on Numerical Analysis Vol. 22, No. 2, 310--321, 1985".
You can find related results searching for "( \frac{dX}{dt} ,=, B(X)X-XB(X), \quad X(0),=, A, ) " and for "Toda Flow" on SearchOnMath.
