4 ms·

> I actually had the latter one in mind: The one given by {Ax | x^T x = 1}. I am near certain that you did not mean this. > When the semi-axes are parallel t

> I actually had the latter one in mind: The one given by {Ax | x^T x = 1}. I am near certain that you did not mean this. > When the semi-axes are parallel to the coordinate axes, the matrix is diagonal. Let D = the matrix | 2 0 | | 0 1 | And let R be any 2-by-2 rotation matrix. A = D * R would give you a locus of points (under {Ax | x^T x = 1}) that has the semi-axes parallel to the coordinate axes. In general, A is not diagonal. For the condition you mention (axis-aligned semi-axes of ellipsoid iff matrix is diagonal) is true for {x | x^T * A * x = 1} .

ogogmad 5y ago
I only consider positive semi-definite symmetric matrices. A = D * R is almost certainly not such a matrix. The positive semi-definite symmetric case is the only one needed to compute SVDs. A proof of convergence for the algorithm is only known for certain families of matrices. These include the positive-definite symmetric matrices, all symmetric matrices (once suitable improvements to the algorithm are made), the Hermitian matrices, and perhaps some others. But a proof that's valid for all matrices isn't known, even though the algorithm (when improved using Wilkinson shifts) appears to converge everywhere.
- gugagore 5y ago
  Ah, okay. Sure. And PSD matrix A is diagonalizeable with orthogonal matrices i.e. A = Q^T * D * Q The ellipsoid visualization you meant is insensitive to the Q term (any rotation of a sphere is the same sphere), but not to the Q^T term. What I am still failing to understand is this sentence from the article: > The basic QR algorithm can be visualized in the case where A is a positive-definite symmetric matrix. It sounds like you can visualize the iterates A_{k} no matter what. Is the problem that there isn't a fixed point when the ellipsoid is axis-aligned? The article has: > Under certain conditions,[4] the matrices Ak converge to a triangular matrix, the Schur form of A. So am I to understand that for A positive semi-definite, the A_{k} converges to a diagonal matrix?
  - ogogmad 5y ago
    >> Under certain conditions,[4] the matrices Ak converge to a triangular matrix, the Schur form of A. > So am I to understand that for A positive semi-definite, the A_{k} converges to a diagonal matrix? Yes. Each iteration of QR (and LR) turns a PSD matrix into another PSD matrix. A PSD matrix in Schur form is necessarily a diagonal matrix. >> The basic QR algorithm can be visualized in the case where A is a positive-definite symmetric matrix. > It sounds like you can visualize the iterates A_{k} no matter what. Is the problem that there isn't a fixed point when the ellipsoid is axis-aligned? My visualization technique assumes that the matrix is PSD. In the PSD case, there is a one-to-one correspondence between ellipsoids and PSD matrices. I don't know what happens if you apply it to non-PSD matrices, but the one-to-one correspondence gets lost.

ogogmad 5y ago

I only consider positive semi-definite symmetric matrices. A = D * R is almost certainly not such a matrix. The positive semi-definite symmetric case is the only one needed to compute SVDs. A proof of convergence for the algorithm is only known for certain families of matrices. These include the positive-definite symmetric matrices, all symmetric matrices (once suitable improvements to the algorithm are made), the Hermitian matrices, and perhaps some others. But a proof that's valid for all matrices isn't known, even though the algorithm (when improved using Wilkinson shifts) appears to converge everywhere.

gugagore 5y ago
Ah, okay. Sure. And PSD matrix A is diagonalizeable with orthogonal matrices i.e. A = Q^T * D * Q The ellipsoid visualization you meant is insensitive to the Q term (any rotation of a sphere is the same sphere), but not to the Q^T term. What I am still failing to understand is this sentence from the article: > The basic QR algorithm can be visualized in the case where A is a positive-definite symmetric matrix. It sounds like you can visualize the iterates A_{k} no matter what. Is the problem that there isn't a fixed point when the ellipsoid is axis-aligned? The article has: > Under certain conditions,[4] the matrices Ak converge to a triangular matrix, the Schur form of A. So am I to understand that for A positive semi-definite, the A_{k} converges to a diagonal matrix?
- ogogmad 5y ago
  >> Under certain conditions,[4] the matrices Ak converge to a triangular matrix, the Schur form of A. > So am I to understand that for A positive semi-definite, the A_{k} converges to a diagonal matrix? Yes. Each iteration of QR (and LR) turns a PSD matrix into another PSD matrix. A PSD matrix in Schur form is necessarily a diagonal matrix. >> The basic QR algorithm can be visualized in the case where A is a positive-definite symmetric matrix. > It sounds like you can visualize the iterates A_{k} no matter what. Is the problem that there isn't a fixed point when the ellipsoid is axis-aligned? My visualization technique assumes that the matrix is PSD. In the PSD case, there is a one-to-one correspondence between ellipsoids and PSD matrices. I don't know what happens if you apply it to non-PSD matrices, but the one-to-one correspondence gets lost.