# Operator norm (induced $2$-norm) of a Kronecker tensor

Let $$A \in \mathcal M(n \times n; \mathbb R)$$ with $$\rho(A) < 1$$. Then we know $$I \otimes I - A^T \otimes A^T$$ is invertible where $$\otimes$$ denotes kronecker product. Let $$\text{vec}$$ denote the vectorization operation and $$\mathcal T = (I \otimes I - A^T \otimes A^T)^{-1} : \mathbb R^{n^2} \to \mathbb R^{n^2}$$. The operator norm of $$\mathcal T$$ is given by \begin{align*} \|\mathcal T\|_2 = \sup_{\|x\|_2=1} \|\mathcal Tx\|_2, \end{align*} where $$x \in \mathbb R^{n^2}$$. Let $$\text{mat}$$ denote the inverse operation of $$\text{vec}$$, i.e., stacking the elements into a matrix. Let $$X = \text{mat}(x)$$ where $$X \in \mathcal M(n \times n)$$. We note $$\mathcal Tx$$ is exactly the vectorization of $$Y$$ where $$Y$$ is the unique solution of \begin{align} \label{eq:1} \tag{\star} A^T Y A + X = Y. \end{align} The assumption on $$A$$ guarantees a unique solution.

My question is whether we can take $$X$$ to be symmetric to determine the operator norm of $$\mathcal T$$. That is, does the following hold \begin{align*} \|\mathcal T\|_2 = \sup \{\|Y\|_F: X \in \mathbb S_n, \|X\|_F=1\}, \end{align*} where $$Y$$ is the solution to \eqref{eq:1} and $$\mathbb S_n$$ denotes the set of symmetric matrices. If we let $$c = \sup \{\|Y\|_F: X \in \mathbb S_n, \|X\|_F=1\}$$, clearly $$c \le \|\mathcal T\|_2$$. Will the other way hold? $$\mathcal T$$ seems to have nice structure and it makes me wonder whether we can just consider supremum over this proper subset.

BOUNTY EDIT: This question has been a while. Loup Blanc has an excellent answer. I thought I understood his edit 2 before but actually it was misunderstanding. Now I am starting a bounty hoping someone (maybe loup himeself) could elaborate his Edit 2.

• One idea would be to use lagrange multipliers to find out which matrices $Y$ satisfy $\|Y\|_F^2$ subject to the constraint $\|Y - A^TYA\|_F^2=1$. In particular, such a matrix $Y$ satisfies $\|Y\|_F = \|\mathcal T\|_2$. – Omnomnomnom Jul 3 '18 at 17:01
• That should read which matrices $Y$ maximize $\|Y\|_F$ – Omnomnomnom Jul 3 '18 at 17:09

## 1 Answer

We work over $\mathbb{R}$ and not over $\mathbb{C}$.

Let $A\in M_n(\mathbb{R})$, $Z=\{Y\in M_n;g(Y)=tr((Y-A^TYA)^T(Y-A^TYA))-1=0\}$ and $f(Y)=tr(Y^TY)$. Note that $Z$ is a compact set as a reciprocal image of a closed ball by a homeomorphism. Here we stack the matrices row by row and we put $y=Vec(Y)$.

$\textbf{Proposition}$. If $(I-A\otimes A)(I-A^T\otimes A^T)$ has distinct eigenvalues, then $Max_{Y\in Z} tr(Y^TY)$ is reached for some symmetric (or skew-symmetric) matrix.

$\textbf{Proof}$. Clearly, the $\max$ is reached for some $Y\in Z$; necessarily, such a matrix satisfies the Lagrange condition: $Df_Y+\lambda Dg_Y=0$, that is, for every $H\in M_n$,

$tr(H^TY+\lambda (H-A^THA)^T(Y-A^TYA))=tr(H^TY+\lambda (H^T-A^TH^TA)(Y-A^TYA))=0$, that is equivalent to

$(*)$ $Y+\lambda(Y-A^TYA-A(Y-A^TYA)A^T)=0$,

or $y+\lambda(I-A^T\otimes A^T-A\otimes A+AA^T\otimes AA^T)y=0$,

or ($y\not=0$ implies that $\lambda\not= 0$)), equivalent to $\phi(y)=(I-A\otimes A)(I-A^T\otimes A^T)y=-\dfrac{1}{\lambda}y$.

Finally, $y$ is an eigenvector of $\phi$ associated to the eigenvalue $-\dfrac{1}{\lambda}$. -Note that $\phi$ is an invertible matrix in the form $UU^T$, and, consequently, is symmetric $>0$-

Here $\phi$ has distinct eigenvalues and, therefore, its eigenspaces $E_{-1/\lambda}$ have dimension $1$.

For a fixed $\lambda$, $y$ is defined up to a factor; since its length is defined by the condition $||(I-A^T\otimes A^T)y||_F=1$, $y$ (then $Y$) is defined up to a signum.

Since $Y$ is a solution of $(*)$, $Y^T$ is also a solution with same norm. Thus $Y^T=\pm Y$, that is, $Y$ is symmetric or skew-symmetric. $\square$

EDIT 1. We obtain $n^2$ candidates $(y_i)$ associated to the $n^2$ distinct eigenvalues $(-1/\lambda_i)$ and, moreover, these vectors are orthogonal ($y_i^Ty_j=0,i\not= j$); then the $n^2$ sym (or skew-sym) matrices $(Y_i)$ form an orthogonal basis of $M_{n^2}$ ($tr(Y_i^TY_j)=0,i\not= j$). We deduce that there are exactly $n^2(n^2-1)/2$ skew-sym $(Y_i)$ and exactly $n^2(n^2+1)/2$ sym $(Y_i)$.

** iris2017 , thanks for the bonus.

EDIT 2. I think that the $\max$ is always (for any $A$) obtained for at least one symmetric matrix $Y$ (that is, when $\phi$ has multiple eigenvalues, the $\max$ may be also reached by matrices $Y$ s.t. $Y^T\not= \pm Y$). For example, when $n=3$ and $A$ is skew-symmetric, the $\max$ may be reached by a matrix that is neither sym nor skew-sym; yet the $\max$ is also reached by a sym. matrix.

• Hi, loup. I am revisiting the problem. I am wondering whether you have any argument in mind to support your Edit $2$? Thanks. – user1101010 Sep 26 '18 at 16:48