Orthogonal basis of ${\bf Sym}_n(\mathbb R)$, made of orthogonal matrices

Question

My question is motivated by this one, but within real matrices instead of complex ones.

${\bf Sym}_n(\mathbb R)$ is a vector space of dimension $N=\frac{n(n+1)}2$. Equipped with the scalar product $\langle A,B\rangle={\rm Tr}(AB)$, this is a Euclidean space. Does there exist a basis $(R_1,\ldots,R_N)$, made of orthogonal matrices only ?

In this situation, each element $U_j$ satisfies $(U_j)^2=I_n$ and therefore is of the form $2\pi_j-I_n$, where $\pi_j$ is an orthogonal projector, over some subspace $E_j$ of $\mathbb R^n$.

Two observations. On the one hand, the answer is No when $n=3$. The basis may not contain $\pm I_3$, because $\langle I_3,R_j\rangle=\pm1\ne0$ for $R_j\ne\pm I_3$. Therefore one may choose each $R_j$ of the form $2x_jx_j^T-I_3$ where $x_j$ is a unit vector. The condition that $\langle R_j,R_k\rangle=0$ for $j\ne k$ writes $|\langle x_j,x_k\rangle|=\frac12$. Therefore $\|x_j-x_k\|=1$ or $\sqrt3$. The twelve unit vectors $\pm x_j$ are such that the pairwise distances are either $1$, $\sqrt3$ or $2$ (for opposite vectors). In short, they should form a regular icosahedron (each vertex has five neighbours) inscribed in the unit sphere, whose edges have unit length ! This is false, since the edge of this icosahedron equals $$\sqrt{\frac{10-2\sqrt5}5}.$$

On the other hand, if we denote $d_j=\dim E_j={\rm Tr}\pi_j$, the orthogonality condition is $$4{\rm Tr}(\pi_j\pi_k)=2d_j+2d_k-n,\qquad j\ne k.$$ We deduce that $$\langle\pi_i-\pi_j,\pi_k-\pi_\ell\rangle=0$$ whenever $i,j,k,\ell$ are pairwise distinct. Therefore ${\bf Sym}_n(\mathbb R)$ contains a subset made of $\frac{N(N-1)}2$ elements (the $S_{ij}=\pi_i-\pi_j$), in which each element is orthogonal to $\frac{(N-2)(N-3)}2$ other ones. Can such a rich configuration exist ?

Edit. Here is an interesting remark. The case $n=3$, studied above, suggested that $I_n$ is unlikely to belong to the basis (though it does for $n=2$). Thus let us raise the side question:

does there exist such a base $\cal B$, containing $R_1=I_n$ ?

If so the other elements $R_i=2\pi_i-I_n$, being orthogonal to $I_n$, satisfy $\dim E_i=\frac n2$. In particular $n$ is even. Now, the orthogonality of $R_i$ and $R_j$ gives $$4{\rm Tr}(\pi_i\pi_j)=2\frac n2+2\frac n2-n=n.$$ Let now $k\in[1,N-1]$ be an integer, and $J\subset[2,N]$ have cardinal $k$. Let us form $$H_J=\sum_{j\in J}\pi_j,$$ which is positive semi-definite. Then $${\rm Tr}H_J=k\frac n2,\qquad{\rm Tr}(H_J)^2=k\frac n2+k(k-1)\frac n4=k\frac n4 (k+1).$$ Let $r_J$ be the rank of $H_J$. By Cauchy-Schwarz (written for the eigenvalues of $H_J$), we have $$({\rm Tr}H_J)^2\le r_J{\rm Tr}(H_J)^2,$$ which gives $$r_J\ge n\frac k{k+1}.$$ If $k=n$, then this implies $r_J\ge\frac{n^2}{n+1}>n-1$ and thus $r_J\ge n$. In other words:

Suppose $R_1=I_n$. For every $J\subset[2,N]$ of cardinal $n$, the symmetric matrix $H_J=\sum_{j\in J}\pi_j$ is positive definite.

Of course this sum of $n$ terms is relatively small, compared to the $N-1=\frac{(n-1)(n+2)}2$ involved projectors $\pi_j$.

Redit. The argument above actually extends to the general case (when $\cal B$ does not necessarily contain $I_n$). Let $J\subset[1,N]$ be of cardinal $m$, and denote $$H_J=\sum_J\pi_j.$$ If $D_J={\rm Tr}H_J=\sum_Jd_j$, then ${\rm Tr}(H_J)^2=m(D_J-\frac{n(m-1)}4)$. Cauchy-Schwarz yields $$D_J^2\le r_Jm\left(D_J-\frac{n(m-1)}4\right).$$ The polynomial $X^2-r_Jm\left(X-\frac{n(m-1)}4\right)$ thus has real roots. Writing that its discriminant is non-negative, we obtain $$r\ge n\frac{m-1}m.$$ For $m=n+1$, this gives $r>n-1$, that is $r=n$. Therefore

The sum of $n+1$ distinct $\pi_j$'s is positive semi-definite.

Answer 1

Here is an example with $n=4$. (ADDED BELOW: An example for any power of $2$)

I identify $\mathbb R^4$ with the quaternions, and describe $10$ subspaces such that any two of the resulting orthogonal projections satisfy the required condition $4Tr(\pi\pi')=2d+2d'-4$. One of the ten is the zero-dimensional subspace, and the other nine are $2$-dimensional. I need $Tr(\pi\pi')=1$ for any two of these nine.

Recall that in the group of unit quaternions there is a subgroup of order $24$. It contains (and normalizes) the order $8$ group $\lbrace \pm 1,\pm i,\pm j, \pm k\rbrace$. The other sixteen elements are the quaternions of the form $$ \frac{\pm 1\pm i \pm j\pm k}{2}.$$ Dividing by the subgroup $\lbrace \pm 1\rbrace$, we get a group $G$ of order $12$ with a normal subgroup $V$ of order $4$. The elements of $G$ correspond to $12$ one-dimensional vector subspaces. The four lines belonging to $V$ are perpendicular to each other, and within each of other two cosets of $V$ in $G$ the four lines are again perpendicular to each other. This gives us eighteen two-dimensional subspaces, each spanned by two perpendicular lines. These come in nine orthogonal pairs. Choose one from each pair.

When $V$ and $V'$ are two of the nine and $\pi$ and $\pi'$ are the corresponding projections, then:

Case 1. $V$ and $V'$ might both come from the same coset of $V$ in $G$. A typical example is: $V$ spanned by $\lbrace 1,i\rbrace$ and $V'$ spanned by $\lbrace 1,j\rbrace$. The trace here is $1$ (eigenvalues $1,0,0,0$).

Case 2. $V$ and $V'$ come from different cosets. Here a typical example is $V$ spanned by $\lbrace 1,i\rbrace$ and $V'$ spanned by $\lbrace 1+i,j+k\rbrace$. The trace is again $1$ (eigenvalues $\frac{1}{2},\frac{1}{2},0,0$).

ADDED

Now that I think it over, a more direct way to describe these nine symmetric-and-orthogonal matrices is to say that they are the maps $x\mapsto axb$, where $\lbrace a,b\rbrace\subset \lbrace i,j,k\rbrace$.

GENERALIZATION

The answer is yes when $n=2^k$ for any $k\ge 0$. In the basis that I will specify, each matrix is a monomial matrix, that is, the product of a permutation matrix (for a very particular kind of permutation) and a diagonal matrix whose eigenvalues are $\pm 1$.

Let $V$ be a $k$-dimensional vector space over $\mathbb F_2$. I will make a set of "$V$ by $V$ matrices", i.e. functions $A:V\times V\to \lbrace 1,-1,0\rbrace\subset \mathbb R$. Each of these will be an orthogonal matrix, the inner product of two of them will always be zero, and he number of elements of the set will be $\frac{n(n+1)}{2}$.

If $H\subset V$ is either $V$ or a codimension one vector subspace, and if $c\in H$, then define the matrix $A_{H,c}$ by $A_{H,c}(v,v+c)=1$ if $v\in H$ and $A_{H,c}(v,v+c)=-1$ if $v\notin H$, and $A_{H,c}(v_1,v_2)=0$ if $v_2\neq v_1+c$. Note that this is symmetric because $c\in H$.

The inner product of $A_{H,c}$ and $A_{H',c'}$ is $0$ if $c\neq c'$, because in that case there is no $(v_1,v_2)$ such that both $A_{H,c}(v_1,v_2)$ and $A_{H',c'}(v_1,v_2)$ are non-zero.

The inner product of $A_{H,c}$ and $A_{H',c}$ is $0$ if $H\neq H'$ because exactly one half of the vectors of $V$ are in the symmetric difference of $H$ and $H'$, insuring that one half of the non-zero terms $A_{H,c}(v,v+c)A_{H',c}(v,v+c)$ in the inner product are $-1$ while the other half are $+1$.

The total number of pairs $(H,c)$ with $H=V$ is $n$, and the total number of pairs $(H,c)$ with $H\neq V$ is $\frac{(n-1)n}{2}$. This adds to $\frac{n^2+n}{2}$.

Answer 2

If there is a Hadamard matrix of size $n/2$, then there is a set of orthogonal matrices as desired. Recall that Hadamard's conjecture predicts that there is a Hadamard matrix of size $m$ whenever $m \equiv 0 \bmod 4$.

Proof: As in Tom Goodwillie's solution, each matrix will be a signed permutation matrix.

First recall that, if there is a Hadamard matrix of size $n/2$, then there is also one of size $n$. Take the $n$ diagonal matrices whose diagonal entries are the rows of an $n \times n$ Hadamard matrix. These will form an orthogonal basis for the space of diagonal matrices.

Let $X=\{ 1,2,\ldots, n-1, \infty \}$. For each $j$ from $1 \to n-1$, let $\sigma_j$ be the permutation of $X$ given by $\sigma_j(j) = \infty$, $\sigma_j(\infty) = j$ and $\sigma_j(i) = 2j-i \bmod n-1$ for $i \neq j$, $\infty$. Note that $\sigma_j$ is a fixed point free involution, so the permutation matrix of $\sigma_j$ is symmetric with no diagonal entries.

For each $\sigma_j$, we will take $n/2$ signed permutation matrices, whose underlying permutation is $\sigma_j$, and whose signs are symmetric and copy the rows of a $(n/2) \times (n/2)$ Hadamard matrix. This will give an orthogonal basis for the set of symmetric matrices supported on the permutation $\sigma_j$.

Since all the $\sigma_j$'s are supported in distinct positions of the matrix, and the supports of all of them are disjoint from the diagonal, combining all of our matrices gives $$n + (n-1) (n/2) = \frac{(n+1)n}{2}$$ mutually orthogonal symmetric signed permutation matrices.