I'm interested in the orthogonal similarity transformation of diagonal matrices, see also my previous questions properties of orthogonal similarity transformation and
orthogonal similarity transformation of a diagonal matrix by a permutation matrix: reverse direction. Assume that $\mathbf{D}$ is a diagonal matrix with positive and pairwise different elements $d_1 > \ldots > d_n > 0$ and $\mathbf{Q}$ an orthogonal matrix. If the orthogonal similarity transformation $\mathbf{Q}^T \mathbf{D} \mathbf{Q}$ is a diagonal matrix, we have expressions $$\mathbf{q}_i^T \mathbf{D} \mathbf{q}_j = 0$$ for the off-diagonal elements ($i \neq j$). At the same time, we have $$\mathbf{q}_i^T \mathbf{q}_j = \mathbf{q}_i^T \mathbf{I} \mathbf{q}_j = 0$$ for these elements, and $\|\mathbf{q}_i\| = 1$.
My guess is that unit vectors $\mathbf{q}_i$ and $\mathbf{q}_j$ can only be orthogonal in both bilinear forms (i.e. both expressions above are zero) if they have an element $\pm 1$.
Does anyone have a counter-example or an idea for a proof? Can the proof address individual elements $(i,j)$ or would we have to consider all $(i,j)$? Would the conjectured property be lost with different assumptions on $\mathbf{D}$, i.e. if some elements of $\mathbf{D}$ are identical or if some are negative?
I'm grateful for any ideas.
I made a bit of progress, but got stuck at a later point.
$
\newcommand{\matQ}{\mathbf{Q}}
\newcommand{\matD}{\mathbf{D}}
\newcommand{\matC}{\mathbf{C}}
\newcommand{\vecz}{\mathbf{z}}
\newcommand{\vecq}{\mathbf{q}}
\newcommand{\vecp}{\mathbf{p}}
\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}}
\newcommand{\vecnull}{\mathbf{0}}
$
In the following I give up the sorting assumption of the diagonal elements.
We first look at the system of equations for two columns $\vecq$ and
$\vecp$ of $\matQ$:
\begin{eqnarray}
\vecq^T \matD \vecp &=& 0\\
\vecq^T \vecp &=& 0.
\end{eqnarray}
We can transform this system into a homogeneous linear system
\begin{equation}
\pmat{
d_1 & d_2 & d_3 & \ldots & d_n\\
1 & 1 & 1 & \ldots & 1}
\pmat{
z_1\\
\vdots\\
z_n}
=
\pmat{0\\0}
\end{equation}
where $z_i = q_i p_i$. We transform the coefficient matrix
\begin{equation}
\matC =
\pmat{
d_1 & d_2 & d_3 & \ldots & d_n\\
1 & 1 & 1 & \ldots & 1}
\end{equation}
into reduced row echelon form: We normalize $d'_i = d_i / d_1$,
\begin{equation}
\pmat{
1 & d'_2 & d'_3 & \ldots & d'_n\\
1 & 1 & 1 & \ldots & 1},
\end{equation}
subtract the first row from the second,
\begin{equation}
\pmat{
1 & d'_2 & d'_3 & \ldots & d'_n\\
0 & 1-d'_2 & 1-d'_3 & \ldots & 1-d'_n},
\end{equation}
normalize the second row,
\begin{equation}
\pmat{
1 & d'_2 & d'_3 & \ldots & d'_n\\
0 & 1 & \frac{1-d'_3}{1-d'_2} & \ldots & \frac{1-d'_n}{1-d'_2}},
\end{equation}
and subtract a scaled version of the second row from the first
\begin{equation}
\pmat{
1 & 0 & d'_3 – \frac{1-d'_3}{1-d'_2} d'_2 & \ldots & d'_n – \frac{1-d'_n}{1-d'_2} d'_2\\
0 & 1 & \frac{1-d'_3}{1-d'_2} & \ldots & \frac{1-d'_n}{1-d'_2}}.
\end{equation}
We introduce for $i \geq 3$
\begin{eqnarray}
a_i
&:=&
d'_i – \frac{1-d'_i}{1-d'_2} d'_2
=
\frac{d'_i (1-d'_2) – (1-d'_i) d'_2}{1-d'_2}
=
\frac{d'_i – d'_2}{1-d'_2}\\
%
b_i
&:=&
\frac{1-d'_i}{1-d'_2}
\end{eqnarray}
and obtain the reduced row echelon form
\begin{equation}
\matC'
=
\pmat{
1 & 0 & a_3 & \ldots & a_n\\
0 & 1 & b_3 & \ldots & b_n}.
\end{equation}
For $d_i \neq d_j\, \forall i \neq j$ we see that $1-d'_i \neq 0\,
\forall i \geq 2$, thus the denominators are defined and $b_i \neq
0\, \forall i \geq 3$ and $a_i \neq 0\, \forall i \geq 3$.
(This paragraph considers violations of the assumption of pairwise different elements in $\matD$. It may be useful later. If $\exists i,j\,(i\neq j): d_i = d_j$, we have to distinguish two
cases. If all $d_i$ are equal, then the $z_i$ can be chosen
arbitrarily under the constraint $\sum_{i=1}^n z_i = 0$. If there is
at least one pair of diagonal elements which differ from each other,
we can select them w.l.o.g. to be $d_1$ and $d_2$, thus $d_1 \neq
d_2$ and $1-d'_2 \neq 0$. In addition, we select the diagonal
elements such that $\exists i\,(i\geq 3): d_2 = d_i$. In this case
we have $a_i = 0$. If also $\exists j\,(j\geq 3): d_1 = d_j$, we
also have $b_j = 0$. The case $a_i = b_i = 0$ is not possible.)
We now determine the null space of $\matC$. From $\matC' \vecz =
\vecnull$ we obtain
\begin{equation}
\begin{matrix}
z_1 & & + z_3 a_3 & \ldots & + z_n a_n & = 0\\
& z_2 & + z_3 b_3 & \ldots & + z_n b_n & = 0
\end{matrix}
\end{equation}
where $z_3,\ldots,z_n$ are free parameters. This leads to
\begin{equation}
\vecz = \pmat{
-z_3 a_3 & -z_4 a_4 & \ldots & -z_n a_n\\
-z_3 b_3 & -z_4 b_4 & \ldots & -z_n b_n\\
z_3 & & & \\
& z_4 & & \\
& & \ddots & \\
& & & z_n
}
\end{equation}
(note that this is not a matrix, but a vector written such that each
$z_i$ appears in a separate column) thus the null space is spanned
by the columns of the $n \times (n-2)$ matrix
\begin{equation}
\pmat{
-a_3 & -a_4 & \ldots & -a_n\\
-b_3 & -b_4 & \ldots & -b_n\\
1 & & & \\
& 1 & & \\
& & \ddots & \\
& & & 1
}.
\end{equation}
Clearly, we can find a $\vecz \neq \vecnull$ such that both bilinear forms become zero. Therefore,
individual vectors $\vecq, \vecp$ fulfilling both equations are not
necessarily vectors with a single non-zero element in different
positions: Assume that $z_i \neq 0$, then $q_i \neq 0$ and
$p_i \neq 0$.
Thus we obviously have to consider the entire matrix $\matQ$:
\begin{eqnarray}
\vecq_i^T \matD \vecq_j &=& 0\quad \forall i \neq j\\
\vecq_i^T \vecq_j &=& 0 \quad \forall i \neq j.
\end{eqnarray}
If we could show that only $\vecz = \vecnull$ allows to fulfill all
these equations, we
could demonstrate that all vectors $\vecq_i$ can only have exactly
one non-zero element (which has to be $\pm 1$ since the vectors are
unit vectors) which appears in different positions. The argument
proceeds as follows: If $z_k = q_{i,k} q_{j,k} = 0$ for all $k$,
then $\vecq_i$ has zero elements where $\vecq_j$ has non-zero
elements and vice versa. Assume that one vector $\vecq_i$ has more
than one non-zero element. Since the remaining $n-1$ vectors
$\vecq_j$ ($j \neq i$) have at least one non-zero element (as they
are unit vectors), it would not be possible to find $n-1$ other
vectors $\vecq_j$ which have their non-zero element at the $n-2$
remaining zero positions of $\vecq_i$.
Any ideas how to show this? Thanks!
Best Answer
Let $A$ be an $n \times n$ matrix. Then $A$ is diagonal if and only if each of the standard basis vectors $e_1, \ldots, e_n$ is an eigenvector of $A$. If $Q$ is an invertible matrix then $Q^{-1} A Q$ is diagonal if and only if the columns of $Q$ are eigenvectors of $A$.
In your case, you have a diagonal matrix $D$ with distinct entries, meaning that each standard basis vector $e_i$ is an eigenvector. Because the eigenvalues are distinct, every eigenvector is a multiple of some $e_i$. This means that when you suppose that $Q^{-1} D Q$ is diagonal for some invertible matrix $Q$, you already know that the columns of $Q$ must contain multiples of the eigenvectors $e_i$. For example, a potential $Q$ could look like $$ Q = \begin{pmatrix} 0 & 6 & 0 \\ -\sqrt{2} & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}. $$
Now apply the fact that your $Q$ is orthogonal, and so every entry must be $\pm 1$.