Quadratic matrix equation $X X' = A$

Question

Find $n\,\,0-1$ matrices $Y_i, i = 1,\dots,n$ with $n$ rows and $n^2$ columns such that:

$Y_iY_j' = \mathbf{1}_n, \forall i\ne j$

$Y_iY_i' = nI_n$

We can write this matrix equations as a single block matrix equation as following:

$XX' = A$,

where $A$ is a matrix with $n^2$ columns and $n^2$ rows and the elements in diagonal are n, other elements are $0$ or $1$ and $X$ is a $n^2\,\, 0-1$ matrix. In detail,

$ A = \begin{pmatrix} nI_n&\mathbf{1}_n& \dots &\mathbf{1}_n \\ \mathbf{1}_n & nI_n & \dots &\mathbf{1}_n \\ \vdots & \vdots & \ddots & \vdots\\ \mathbf{1}_n &\mathbf{1}_n & \dots & nI_n\end{pmatrix} $, $X = \begin{pmatrix} Y_1 \\Y_2\\ \dots \\ Y_n \end{pmatrix}$

Answer 1

This question is equal to find $n-1$ mutually orthogonal Latin squares for $n$, which is an open question.

Answer 2

A partial answer: when $n$ is a prime number, you may take $$ X=\pmatrix{ I&I&I&\cdots&I\\ I&C&C^2&\cdots&C^{n-1}\\ I&C^2&(C^2)^2&\cdots&(C^{n-1})^2\\ \vdots&\vdots&\vdots&&\vdots\\ I&C^{n-1}&(C^2)^{n-1}&\cdots&(C^{n-1})^{n-1}} $$ where $C$ is the companion matrix for the polynomial $x^n-1$. That is, we take $C$ as the permutation matrix for a cyclic shift and we let the $(k,j)$-th sub-block of $X$ be $C^{kj}$ for $k,j\in\{0,1,\ldots,n-1\}$. The $(i,j)$-th sub-block of $X^TX$ is then given by $$ \sum_{k=0}^{n-1}(C^{ki})^TC^{kj} =\sum_{k=0}^{n-1}(C^{j-i})^k =\begin{cases} nI&\text{when }i=j,\\ \mathbf 1_{n\times n}&\text{otherwise (here we need $n$ to be prime)}. \end{cases} $$

Answer 3

here is a recipe for an $n=4.$ Suppose I call this matrix $M.$ For each row $i$ of four numbers, place a $1$ for each of the four numbers $j,$ place a $1$ at $M_{i,j}$

Each block of four rows below should have the numbers from $1$ to $16$ For two rows in distinct blocks, there must be exactly one common element $j.$

I am a little encouraged in that the second block is the transpose of the first block; I did not build that in. Almost: not quite the transpose. On the other hand, the permutations of each column in block 2 come in a sort of 2 by 2; as rows, beginning with some abcd, we have alternatives used: dcba or cdab or badc. This suggests an approach to composite $n$

Let's see, the way I have printed this $M,$ the outcome $M M^T$ should be the desired Gram matrix.

More checking: I also know how to tell pari-gp the entries of this matrix $M,$ tell it to find $M M^T$ and print that out; I'll get to that later.

====================
    1    2    3    4
    5    6    7    8
    9   10   11   12
   13   14   15   16
---------------------
    1    5    9   13
    2    6   10   15
    3    7   11   14
    4    8   12   16
--------------------
    1    6   12   14
    2    5   11   16
    3    8   10   13
    4    7    9   15
---------------------
    1    8   11   15
    2    7   12   13
    3    6    9   16
    4    5   10   14
====================