Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider two matrices $A$ and $B$ of the same size. Let $\text{vec}(A)$ denote the operator that maps $A$ to a column vector by stacking its columns. Is there a wy to express $\text{vec}(A) \text{vec}(B)^T$ in terms of the Kronecker (tensor) product of the original matrices?

More interestingly, can we give an upper bound on the operator norm of $\text{vec}(A) \text{vec}(B)^T$?

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

Let $$A = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{pmatrix}, ~~~~ B = \begin{pmatrix} b_{11} & b_{12} & \cdots & b_{1n} \\ b_{21} & b_{22} & \cdots & b_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ b_{n1} & b_{n2} & \cdots & b_{nn} \end{pmatrix}. $$ So we have $$\begin{align} \operatorname{vec}(A) \operatorname{vec}(B)^T &= \begin{pmatrix} a_{11} \\ \vdots \\ a_{n1} \\ a_{12} \\ \vdots \\ a_{n2} \\ \vdots \\ a_{1n} \\ \vdots \\ a_{nn} \end{pmatrix} \begin{pmatrix} b_{11} & \cdots & b_{n1} & b_{12} & \cdots & b_{n2} & \cdots & b_{1n} & \cdots & b_{nn} \end{pmatrix} \\ &= \begin{pmatrix} a_{11}b_{11} & a_{11}b_{21} & \cdots & a_{11}b_{nn} \\ a_{21}b_{11} & a_{21}b_{21} & \cdots & a_{21}b_{nn} \\ \vdots & \vdots & \ddots & \vdots \\ a_{nn}b_{11} & a_{nn}b_{21} & \cdots & a_{nn}b_{nn} \end{pmatrix} \end{align}$$

We see the rows of this $n^2 \times n^2$ matrix are $a_{ij} \operatorname{vec}(B)^T$. Taking a look at $$A \otimes B = \begin{pmatrix} a_{11} b_{11} & a_{11} b_{12} & \cdots & a_{11} b_{1n} & \cdots & \cdots & a_{1n} b_{11} & a_{1n} b_{12} & \cdots & a_{1n} b_{1n} \\ a_{11} b_{21} & a_{11} b_{22} & \cdots & a_{11} b_{2n} & \cdots & \cdots & a_{1n} b_{21} & a_{1n} b_{22} & \cdots & a_{1n} b_{2n} \\ \vdots & \vdots & \ddots & \vdots & & & \vdots & \vdots & \ddots & \vdots \\ a_{11} b_{n1} & a_{11} b_{n2} & \cdots & a_{11} b_{nn} & \cdots & \cdots & a_{1n} b_{p1} & a_{1n} b_{n2} & \cdots & a_{1n} b_{nn} \\ \vdots & \vdots & & \vdots & \ddots & & \vdots & \vdots & & \vdots \\ \vdots & \vdots & & \vdots & & \ddots & \vdots & \vdots & & \vdots \\ a_{n1} b_{11} & a_{n1} b_{12} & \cdots & a_{n1} b_{1n} & \cdots & \cdots & a_{nn} b_{11} & a_{nn} b_{12} & \cdots & a_{nn} b_{1n} \\ a_{n1} b_{21} & a_{n1} b_{22} & \cdots & a_{n1} b_{2n} & \cdots & \cdots & a_{nn} b_{21} & a_{nn} b_{22} & \cdots & a_{nn} b_{2n} \\ \vdots & \vdots & \ddots & \vdots & & & \vdots & \vdots & \ddots & \vdots \\ a_{n1} b_{n1} & a_{n1} b_{n2} & \cdots & a_{n1} b_{nn} & \cdots & \cdots & a_{nn} b_{n1} & a_{nn} b_{n2} & \cdots & a_{nn} b_{nn} \end{pmatrix}$$ we see that $a_{ij}\operatorname{vec}(B)^T$ is the transposed vectorization of the $n \times n$ submatrix at position $i, j$ in the $n^2 \times n^2$ matrix $A \otimes B$.

In other words, the rows of $\operatorname{vec}(A)\operatorname{vec}(B)^T$ are the transposed vectorizations of the $n \times n$ submatrices of $A \otimes B$ taken top to bottom, then left to right.

Especially, $\operatorname{vec}(A)\operatorname{vec}(B)^T$ and $A \otimes B$ have the same elements, but in different places, thus their Frobenius norm will be the same.

The norm $\|\operatorname{vec}(A)\operatorname{vec}(B)^T\|_\infty$ is the greatest absolute row sum of the matrix. The absolute row sum of a row is: $$|a_{ij}| \sum_{k, l} |b_{kl}|.$$ So, the maximum $|a_{ij}|$ will give the norm. A similar argument can be done for $\|\operatorname{vec}(A)\operatorname{vec}(B)^T\|_1$, which is the greatest absolute column sum.

$\operatorname{vec}(A)\operatorname{vec}(B)^T$ and $A \otimes B$ will in general have different ranks. $\operatorname{vec}(A)\operatorname{vec}(B)^T$ will have rank one and $A \otimes B$ will have rank $\operatorname{rank}(A)\operatorname{rank}(B)$.

Since $\operatorname{vec}(A)\operatorname{vec}(B)^T$ has rank one, it has only one non-zero singular value, which will decide its spectral norm. Of course, we have a spectral value decomposition given by $$\operatorname{vec}(A)\operatorname{vec}(B)^T = \|\operatorname{vec}(A)\| \|\operatorname{vec}(B)\| \frac{\operatorname{vec}(A)}{\|\operatorname{vec}(A)\| }\frac{\operatorname{vec}(B)^T}{\|\operatorname{vec}(B)\| },$$ i.e. the singular value, and the spectral norm, is $\|\operatorname{vec}(A)\| \|\operatorname{vec}(B)\|$. $\|\operatorname{vec}(A)\|$ is the same as the Frobenius norm of $A$, which is the square root of the sum of the squares of the singular values of $A$.

share|improve this answer
    
Thanks for taking the time to write this, and for the thorough response. I did not notice that the operator norm can be expressed exactly as the product of the Frobenius norms of $A$ and $B$. Thanks for pointing that out. –  passerby51 Jan 31 '13 at 15:57
    
You are welcome. :) –  Calle Jan 31 '13 at 18:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.