Minimizing the diagonal product of a special orthogonal matrix

147 Views Asked by At

For any $n > 1$, define $f: \textrm{SO}(n) \rightarrow \mathbb{R}$ as the diagonal product

$$f(A) = \prod_{i=1}^n A_{ii}$$

Based on some numerical experiments, it seems that

$$\min_{A \in \textrm{SO}(n)} f(A) = -\left(1-\frac2n\right)^n,$$

and this minimum is attained on matrices $(a_{ij})$ satisfying $|a_{ii}| = 1-2/n$ (with odd number of negative $a_{ii}$'s, of course) and $|a_{ij}| = 2/n$ for $i \neq j$. For illustration, here is one of such "diagonal-product-minimizing" matrices for the $n=5$ case: $$\frac{1}{5} \left( \begin{array}{rrrrr} -3 & -2 & -2 & -2 & -2 \\ 2 & 3 & -2 & -2 & -2 \\ 2 & -2 & 3 & -2 & -2 \\ 2 & -2 & -2 & 3 & -2 \\ 2 & -2 & -2 & -2 & 3 \end{array} \right)$$ Is that a known (let alone true) result? How can one prove it? I've managed to handle only the trivial $n=2$ case and the somewhat less trivial $n=3$ case using the Euler angle parametrization.

1

There are 1 best solutions below

5
On BEST ANSWER

When $n=2$, every matrix in $SO(2,\mathbb R)$ has two identical diagonal elements. Therefore $f(A)$ is always nonnegative. The minimum value $f(A)=0$ is attained by and only by $A=\pm\pmatrix{0&-1\\ 1&0}$.

When $n\ge3$, we shall show that a global minimiser is given by $$ A_\ast = (I-\tfrac{2}{n}ee^T)\operatorname{diag}(-1,1,\ldots,1) $$ and the other global minimisers are obtained by a series of operations involving negations of some rows or columns of $A_\ast$ (while keeping the result in $SO(n,\mathbb R)$) and/or simultaneous permutations of rows and columns of $A_\ast$.

Let $A_0=(a_{ij})_{i,j\in\{1,2,\ldots,n\}}$ be a global minimiser of $f$. We know that $f(A_0)$ is negative because $f(A_0)\le f(A_\ast)<0$. It follows that all diagonal elements of $A_0$ are nonzero and an odd number of them are negative. If $A_0$ has three or more negative diagonal elements, then by negating two rows with negative diagonal elements, one obtain a new global minimiser with two fewer negative diagonal elements. Therefore, we may assume that $A_0$ has exactly one negative diagonal element.

Let $M$ be the leading principal $2\times2$ submatrix of $A_0$ and let $K=\pmatrix{0&-1\\ 1&0}$. Define $$ g(t)=f\left((e^{tK}\oplus I_{n-2})A_0(e^{-tK}\oplus I_{n-2})\right) =f(e^{tK}Me^{-tK})\prod_{i=3}^na_{ii}. $$ Since $$ \begin{aligned} &e^{tK}Me^{-tK}\\ &=M+t(KM-MK)+t^2\left(\frac{1}{2}K^2M-KMK+\frac{1}{2}MK^2\right)+O(t^3)\\ &=M+t(KM-MK)-t^2(M+KMK)+O(t^3)\\ &=\pmatrix{a_{11}-t(a_{12}+a_{21})-t^2(a_{11}-a_{22})&\ast\\ \ast&a_{22}+t(a_{12}+a_{21})+t^2(a_{11}-a_{22})}+O(t^3), \end{aligned} $$ we see that $$ g(t)=\left\{a_{11}a_{22}+t(a_{11}-a_{22})(a_{12}+a_{21})+t^2[(a_{11}-a_{22})^2-(a_{12}+a_{21})^2]\right\}\prod_{i=3}^na_{ii}+O(t^3). $$ As $A_0$ minimises $f$, the function $g$ attains global minimum at $t=0$. So, we must have $g'(0)=0$ and $g''(0)\ge0$. Similar conclusions are also reached if we consider other principal submatrices of $A_0$. It follows that $$ \begin{align} &(a_{ii}-a_{jj})(a_{ij}+a_{ji})=0\tag{1}\\ \text{and}\quad &\left[(a_{ii}-a_{jj})^2-(a_{ij}+a_{ji})^2\right]\prod_{k\ne i,j}a_{kk}\ge0\tag{2} \end{align} $$ for all $i\ne j$.

Suppose that the only negative diagonal element of $A_0$ is located at the $(r,r)$-th position. If $r=i\ne j$, then $a_{rr}-a_{jj}<0$. Hence $(1)$ gives $$ a_{rj}=-a_{jr}\quad\text{ for all $j\ne r$}.\tag{3} $$ Next, suppose that $i,j,r$ are three distinct indices, then by $(1)$, we have $a_{ii}=a_{jj}$ or $a_{ij}+a_{ji}=0$. If $a_{ij}+a_{ji}=0$, then $(2)$ gives $(a_{ii}-a_{jj})^2\prod_{k\ne i,j}a_{kk}\ge0$. Since $r\ne i,j$, $\prod_{k\ne i,j}a_{kk}$ is negative. Hence we must have $a_{ii}=a_{jj}$. So, regardless of whether $a_{ij}+a_{ji}=0$ in $(1)$, we always have $a_{ii}=a_{jj}$. In other words, $$ \text{all positive diagonal elements of $A_0$ are identical to each other.}\tag{4} $$ Now, pick any index $s\ne r$. Let $D$ be the diagonal matrix obtained by modifying $r$-th and $s$-th diagonal elements of the identity matrix to $-1$. Then $\widetilde{A}=DA_0$ is also a global minimiser of $f$ with exactly one negative diagonal element. Therefore, $(3)$ and $(4)$ still hold if the elements of $A_0$ are replaced by those of $\widetilde{A}$. It follows that in $A_0$, we must have $$ \begin{align} &a_{ij}=a_{ji}\quad\text{whenever $i,j\ne r$},\tag{5}\\ &a_{rr}=-a_{ii}\quad\text{for all $i\ne r$}.\tag{6} \end{align} $$ So, by permuting the rows and columns of $A_0$ simultaneously, we may assume that $r=1$ and $$ A_0=\pmatrix{-c&-su^T\\ su&B_0} $$ where $0<c\le1,\, s=\sqrt{1-c^2}$, $u$ is some unit vector and $B_0=(b_{ij})_{i,j\in\{1,2,\ldots,n\}}$ is a symmetric matrix whose diagonal elements are all equal to $c$. Obviously, $c$ cannot be equal to $1$, otherwise, as all diagonal elements of $B_0$ are equal to $c=1$, $A_0$ is necessarily equal to $\operatorname{diag}(-1,1,\ldots,1)$, which is not a member of $SO(n,\mathbb R)$. Hence $0<c<1$ and the condition $A_0A_0^T=A_0^TA_0=I_n$ means precisely that $$ B_0u=-cu\quad\text{and}\quad B_0^2=I_{n-1}-s^2uu^T.\tag{7} $$ Moreover, $(7)$ implies that $\det(A_0)=(-c+s^2u^TB_0^{-1}u)\det(B_0)=-\frac{1}{c}\det(B_0)$. Therefore $A_0\in SO(n,\mathbb R)$ if and only if $(7)$ is satisfied with $\det(B_0)<0$.

We now claim that $-c$ is the only negative eigenvalue of $B_0$ and it is simple. Suppose the contrary. Since $\det(B_0)<0$, $B_0$ has at least three negative eigenvalues. Let $B_0=U\operatorname{diag}(-c,\lambda_2,\lambda_3,\lambda_4,\ldots,\lambda_{n-1})U^T$ be an orthogonal diagonalisation where the first column of $U$ is $u$ and $\lambda_2,\lambda_3<0$. Let $\widetilde{A}$ be the matrix modified from $A_0$ by switching $B_0$ to $\widetilde{B}=U\operatorname{diag}(-c,|\lambda_2|,|\lambda_3|,\lambda_4,\ldots,\lambda_{n-1})U^T$. Then $\det(\widetilde{B})<0$ and $(7)$ is satisfied by $\widetilde{B}$. Therefore $\widetilde{A}\in SO(n,\mathbb R)$. Yet, by construction, we have $\widetilde{b}_{ii}\ge b_{ii}$ for every $i$ and strict inequality holds for some $i$. Hence we arrive at the contradiction that $f(\widetilde{A})<f(A_0)$.

Thus $-c$ is the only negative eigenvalue of $B_0$ and it is simple. It follows from $(7)$ that $$ B_0=I_{n-1}-(1+c)uu^T. $$ Since $c=b_{ii}=1-(1+c)u_i^2$ for every $i$ and $u$ is a unit vector, we obtain $u_i=\pm\frac{1}{\sqrt{n-1}}$ and $c=\frac{n-2}{n}$, where the sign of $u_i$ can be chosen arbitrarily without changing the value of $f(A_0)$. In particular, if we take $u=\frac{1}{\sqrt{n-1}}e$, the global minimiser we obtain is the matrix $A_\ast$ we mentioned earlier in the answer and $f(A_\ast)=-c^n=-\left(\frac{n-2}{n}\right)^n$.