9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Omnomnomnom Jul 3 '18 at 17:01
  • $\begingroup$ That should read which matrices $Y$ maximize $\|Y\|_F$ $\endgroup$ – Omnomnomnom Jul 3 '18 at 17:09
3
+50
$\begingroup$

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.

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

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.