Putnam 2014, Problem A-6

Let $n$ be a positive integer. What is the largest $k$ for which there exist $n \times n$ matrices $M_1, \ldots, M_k$ and $N_1, \ldots, N_k$ with real entries such that for all $i$ and $j$, the matrix product $M_i N_j$ has a zero entry somewhere on its diagonal if and only if $i \neq j$?

Solution:
The largest such \(k\) is \(n^n\). Let \(e_1, \dots, e_n\) be the standard basis of \(\mathbb{R}^n\). For \(i_1, \dots, i_n \in \{1, \dots, n\}\), let \(M_{i_1, \dots, i_n}\) be the matrix with row vectors \(e_{i_1}, \dots, e_{i_n}\), and \(N_{i_1, \dots, i_n}\) be its transpose. Then \(M_{i_1, \dots, i_n} N_{j_1, \dots, j_n}\) has \(k\)-th diagonal entry \(e_{i_k} \cdot e_{j_k}\), so \(k \leq n^n\). For any families \(M_i, N_j\), let \(V\) be the \(n\)-fold tensor product \(\mathbb{R}^n \otimes \dots \otimes \mathbb{R}^n\) with orthonormal basis \(e_{i_1} \otimes \dots \otimes e_{i_n}\). Let \(m_i\) be the tensor product of the rows of \(M_i\), so \(m_i = \sum_{i_1, \dots, i_n=1}^n (M_i)_{1,i_1} \cdots (M_i)_{n,i_n} e_{i_1} \otimes \dots \otimes e_{i_n}\). Similarly, let \(n_j\) be the tensor product of the columns of \(N_j\). Then \(m_i \cdot n_j\) is the product of the diagonal entries of \(M_i N_j\), so it vanishes if \(i \neq j\). For \(c_i \in \mathbb{R}\) with \(\sum_i c_i m_i = 0\), we have \(0 = \left( \sum_i c_i m_i \right) \cdot n_j = \sum_i c_i (m_i \cdot n_j) = c_j\), so \(m_1, \dots, m_k\) are linearly independent, implying \(k \leq n^n\).