2
$\begingroup$

I have a hypothesis on some relationship between matrices, but no proof for it. I have a feeling this should exist already, could anyone point me in the right direction?

If I have a square matrix $A$ (let's say full rank, but otherwise arbitrary) and calculate its QR decomposition as $A = QR$ so that the diagonal of R is positive (so R is unique), my hypothesis is that the diagonal of $R$, which gives its eigenvalues, also gives the singular values of $A$. In other words, $diag(R) = eig(R) = \sqrt{eig(R^T R)} = sing(A)$. This seems to imply that $eig(R)^2 = eig(R^2) = eig(R^T R)$.

This seems to be true in practice, but from what properties does this follow? I tested this by generating lots of matrices w. random values between -1 and 1 and calculating these numbers using this program:

import numpy as np
from utils import qr_pos

def is_diagonal(A):
    return np.count_nonzero(A - np.diag(np.diagonal(A))) == 0

def test_eig(n=30, tol=0.00001):
    M = np.random.rand(N, N) # Random matrix
    M = 2*M - 1              # Entries from -1 to 1
    Q, R = qr_pos(M)         # QR dec. so that diag(R) is positive
    if is_diagonal(R):
        print 'R is diagonal!'
    RTR = np.transpose(R) * R
    sinvals = np.sqrt(np.linalg.eigvals(RTR))
    diff = np.linalg.norm(sinvals - np.diag(R))

    # print 'Singular values:', sinvals
    # print 'Diagonal of R:', np.diag(R)
    # print 'Difference:', diff
    return diff < tol, M

success = True
N = 300
for i in range(N):
    equal, M = test_eig()
    print 'i',
    if not equal:
        print
        print 'Case found where the hypothesis does not hold:', M
        success = False
        break
if success:
    print
    print 'Hypothesis holds for', N, 'random test cases.'

Which outputs:

i i i i ... i i i
Hypothesis holds for 300 random test cases.
$\endgroup$
  • $\begingroup$ The QR decomposition does not by itself give either the singular values or the eigenvalues of a matrix. QR decomposition may well be used in an iterative procedure to find singular values or eigenvalues. $\endgroup$ – hardmath Jan 23 '18 at 16:58
  • 1
    $\begingroup$ The eigenvalues of $R$ are not usually the singular values of $A$ (in fact they can't be unless $R$ is diagonal). However, both $R$ and $A$ have the same singular values. $\endgroup$ – Omnomnomnom Jan 23 '18 at 17:10
  • $\begingroup$ @Omnomnomnom I added a program I used to test my hypothesis. It seems to be the case that the eigenvalues of $R$ are the singular values of $A$ in many cases, and in none of the cases is $R$ diagonal. How can this be the case? $\endgroup$ – nardi Jan 23 '18 at 22:05
  • $\begingroup$ Note that unless $R$ is diagonal, we cannot say $R^2 = R^T R$. Would it suffice to give an example where nonsingular $R^2$ and $R^T R$ have different eigenvalues? $\endgroup$ – hardmath Jan 23 '18 at 23:32
  • $\begingroup$ @nardi not sure what's wrong with your code, but I've put a specific example down into an answer $\endgroup$ – Omnomnomnom Jan 23 '18 at 23:56
3
$\begingroup$

Here's a quick example:

$$ M = \pmatrix{1&2\\1&1} \implies\\ Q = \frac 1{\sqrt{2}}\pmatrix{1 & 1\\1 & -1}, \quad R = \frac 1{\sqrt{2}} \pmatrix{2 & 3\\ 0 & 1} $$ The singular values of $M$ (and of $R$) are $\sqrt{\frac{7 \pm 3\sqrt{5}}{2}}$, which doesn't match the diagonal entries of $R$.

$\endgroup$
  • 1
    $\begingroup$ You're right, this is not true. I made an error in that I used * instead of np.dot, so I was not getting the proper matrix product. $\endgroup$ – nardi Jan 24 '18 at 16:26
0
$\begingroup$

Accepted answer is nice, this is just another way of seeing this.

Hypothesis : Assume the diagonal of $R$ contains the singular values.

If you use the Gram-Schmidt process to compute the $A = QR$, you have $r_{1,1} = \|a_1\|$ with $a_1$ the first column of $A$, meaning that $\|a_1\|$ is a singular value of $A$, which is not always true.

Moreover using every permutation of $A$ and of its transpose gives that the norm of each columns and rows of $A$ are singular values of $A$, which exceed the number of possible singular values.

So the hypothesis is wrong.

New contributor
matthiasbe is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\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.