Is the cone of symmetric diagonally dominant matrices invariant under the conjugation by orthogonal matrices

108 Views Asked by At

Suppose A is a symmetric $n\times n$ matrix. $A$ is diagonally dominant (dd) if:

$$ |A_{ii}| \ge \sum_{j=0, j\neq i}^n |A_{ij}| \ \ \forall i=1,2,\cdots ,n $$

Is $U^TAU$ dd for every dd $A$ and orthogonal $U$?

If we limit matrices $U$ to be permutation matrices instead of orthogonal matrices then $U^TAU$ is dd.

Proof: suppose $U=U_1 U_2 \cdots U_n$ where each $U_i$ is a transposition matrix. Then

$$U^TAU=U_n^T\cdots U_1^TAU_1^T\cdots U_n^T.$$

Suppose $\bar{A}=U_1^TAU_1^T$. We permute the rows and the columns $p$ and $q$ of the matrix $A$ by the conjugation by $U_1$. Then

$$ |A_{qq}| \ge \sum_{j=0, j\neq q}^n |A_{qj}|$$ implies $$ |\bar{A}_{pp}| \ge \sum_{j=0, j\neq q}^n |A_{qj}|= \sum_{j=0, j\neq q}^n |\bar{A}_{pj}|$$ and $$ |A_{pp}| \ge \sum_{j=0, j\neq p}^n |A_{pj}|$$ implies $$ |\bar{A}_{qq}| \ge \sum_{j=0, j\neq p}^n |A_{pj}|= \sum_{j=0, j\neq q}^n |\bar{A}_{qj}|$$

Hence, $\bar{A}$ is dd. By continuing this procedure, we see $U^TAU$ is dd.

However, I cannot prove for orthogonal matrices U.

2

There are 2 best solutions below

0
On BEST ANSWER

It should be easy to cook up a counterexample. Let $A=\operatorname{diag}(1,0,\ldots,0)$. Then $U^TAU=uu^T$ where $u$ is the first column of $U^T$. Now, whenever $0<|u_i|<|u_k|$ for some $i$ and $k$, the matrix $B=U^TAU=uu^T$ is not diagonally dominant, because $b_{ii}=u_i^2<|u_iu_j|=|b_{ik}|\le\sum_{j\ne i}|b_{ik}|$.

For instance, let $U^T=\pmatrix{\frac{\sqrt{3}}{2}&\frac{-1}{2}\\ \frac{1}{2}&\frac{\sqrt{3}}{2}}$ and $A=\pmatrix{1&0\\ 0&0}$. Then $U^TAU=\pmatrix{\frac{3}{4}&\frac{\sqrt{3}}{4}\\ \frac{\sqrt{3}}{4}&\frac{1}{4}}$ is not diagonally dominant on the second row.

Since the elements of $U^TAU$ are continuous in the elements of $A$, if you perturb $A$ slightly, such as by taking $A=\pmatrix{1&0\\ 0&\epsilon}$ or $\pmatrix{1&\epsilon\\ \epsilon&\epsilon}$ for some small $\epsilon>0$, you may obtain also a counterexample with the same $U$ but a strictly diagonally dominant $A$.

0
On

Counterexample:

$$ A = \begin{bmatrix} 3.38 & -0.592 & -0.765 & -0.372 \\ -0.592 & 3.384 & -0.048 & -0.922 \\ -0.765 & -0.048 & 2.636 & -0.83 \\ -0.372 & -0.922 & -0.83 & 2.219 \end{bmatrix}, \quad U = \begin{bmatrix} -0.064 & 0.16 & 0.855 & 0.489 \\ -0.307 & -0.051 & -0.481 & 0.819 \\ -0.943 & 0.117 & 0.079 & -0.3 \\ 0.107 & 0.979 & -0.175 & -0.001 \end{bmatrix}, $$ such that $$ U^\top A U = \begin{bmatrix} 2.79202 & 1.16264 & 0.629779 & 0.204777 \\ 1.16264 & 2.02517 & 0.255441 & -0.720253 \\ 0.629779 & 0.255441 & 3.70448 & 0.0196678 \\ 0.204777 & -0.720253 & 0.0196678 & 3.09056 \end{bmatrix}, $$ where in particular row 2 violates diagonal dominance.