6
$\begingroup$

• Let $A$ be a (real) dense (non-sparse) matrix with size $rp\times M$ ($M < rp$) with orthonormal columns (i.e. $A^TA = I_M$).

• Similarly, let $B$ be a dense matrix with size $rq\times N$ ($N < rq$) with orthonormal columns.

• Let $V=\bigoplus_{i=1}^qA.$ Equivalently, $V=I_q\bigotimes A,$ where $\bigoplus$ denotes the direct sum, and $\bigotimes$ denotes the Kronecker product.

• Let $W=\bigoplus_{j=1}^pB.$ Equivalently, $W=I_p\bigotimes B.$

• Let $R=V^TW,$ and therefore, $$ R=\big(\bigoplus_{i=1}^qA^T\big)\big(\bigoplus_{j=1}^pB\big) $$ $$ =\big(I_q\bigotimes A^T\big)\big(I_p\bigotimes B\big) $$

• Assume: $rpq > qM + pN$ (so that the augmented matrix $\left[\begin{array}{c|c}V & W\end{array}\right]$ is a tall matrix).

• Note: $p\neq q$, $p>1$ and $q>1$.


Prove that the singular values of $R$ come in $n$-tuples, with $$ n=\text{GCD}(p,q), $$ where $\text{GCD}(p,q)$ is the greatest common divisor of $p$ and $q$. In other words, prove that a singular value of $R$ has a multiplicity of $\text{GCD}(p,q)$.


Note: I am ONLY interested in proving that the largest singular value of $R$ is distinct when $p$ and $q$ are relatively prime ($\text{GCD}(p,q) = 1$). However, I think giving the larger picture of the behavior of the singular values of $R$ is far more interesting, and probably even helpful in proving the specific case I'm interested in. Please refer to the Matlab code below to verify that $n=\text{GCD}(p,q)$.


Matlab code:

clear all; close all;

r = 3; % integer >= 1

p = 12; q = 16; %17 % for the singular values of R to be distinct, p and q must be relatively prime integers and larger than 1 (i.e. GCD(p,q) = 1 and p > 1 and q > 1) 

M = 8; % # of columns of A
N = 14; % # of columns of B. M and N MUST satisfy 1 < M < rp, 1 < N < rq AND they must satisfy assumption that r*p*q/(q*M+p*N) > 1.

[A,~] = qr(rand(r*p,M),0); % size = rp X M (M < rp, A'A = I) % Note: you can orthonormalize (e.g. via Gram Schmidt or SVD) any arbitrary 
                       % (full rank) data matrix other than noise, I'm only using
                       % noise as a data matrix because it's conevniently easy to generate.
[B,~] = qr(rand(r*q,N),0); % size = rq X N (N < rq, B'B = I)

V = kron(eye(q),A); % size = q(rp) X qM
W = kron(eye(p),B); % size = p(rq) X pN

R = V'*W; % i.e. R = direct sum (over q) of (A') X direct sum (over p) of (B)

% assumption
r*p*q/(q*M+p*N) % check is greater than 1 % This assumption is required for the augmented matrix [V W] to be tall. 
gcd(p,q) % check for relative primeness of p and q. % This assumption is required for the singular values of R to be distinct.

figure;stem(svd(R));   
title 'note how the singular values of R come in GCD(p,q)-tuples'
$\endgroup$
1
$\begingroup$

Let me write \begin{align} V &= I_q \otimes A = \text{blkdiag}(A, ..., A), \\ W &= I_p \otimes B = \text{blkdiag}(B, ..., B). \end{align} We can write $$ V^TW = I_q \otimes (A^TB)=\text{blkdiag}(A^TB,...,A^TB) $$ only if $p=q$. But if $p \neq q$, we can still do the following: $$ R=V^TW = I_n \otimes (V_{\text{sub}}^TW_{\text{sub}})=\text{blkdiag}(V_{\text{sub}}^TW_{\text{sub}},...,V_{\text{sub}}^TW_{\text{sub}}), $$ with \begin{align} n &= \text{GCD}(p, q), \\ V_{\text{sub}} &= I_{q/n} \otimes A = \text{blkdiag}(A,...,A), \\ W_{\text{sub}} &= I_{p/n} \otimes B = \text{blkdiag}(B,...,B). \end{align} So in the end, it turns out that $R$ is a block diagonal matrix with $n=\text{GCD}(p,q)$ identical matrices. To compute the singular values of a block diagonal matrix, it suffices to compute the singular values of the matrices. Hence, the singular values of $R$ are simply $n$ times the singular values of $V_{\text{sub}}^TW_{\text{sub}}$.

Note that the fact that $A$ and $B$ are orthogonal is not used for this derivation. It also holds in case $A$ and $B$ are non-orthogonal.

$\endgroup$
  • $\begingroup$ First of all, thank you very much for your answer. But did you try to image $R$? For example, using the Matlab code above, add figure;imagesc(R); $R$ is not even square for it to be possibly a block-diagonal matrix. Yes, it does contain a submatrix (made up of 3 almost-diagonal blocks) repeated $n$ times, but overall $R$ is not block-diagonal. Looking forward for your feedback. (btw, what is $k$?). $\endgroup$ – seeker Nov 9 '17 at 10:15
  • $\begingroup$ Yes I did. Actually, it was the first thing I did. I do not really see the problem. I think I nowhere mention that R had to be square $\endgroup$ – EdG Nov 9 '17 at 10:23
  • $\begingroup$ Also, note that a diagonal matrix has to be square, BUT a block diagonal matrix does not need to be square $\endgroup$ – EdG Nov 9 '17 at 10:25
  • $\begingroup$ Oh sorry for $k$. That is supposed to be $n$. I will fix that $\endgroup$ – EdG Nov 9 '17 at 10:27
  • $\begingroup$ Ok, but do you agree that the submatrix: $V_{sub}^{T} W_{sub}$ is not block diagonal? $\endgroup$ – seeker Nov 9 '17 at 10: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.