Mermin-Peres magic rectangles

Can a system of linear equations have no solution in numbers, but have a solution in matrices? The Mermin-Peres magic square gives a famous example modulo $2$. In our new paper Mermin-Peres magic rectangles modulo odd primes, with Josse van Dobben de Bruyn and Remy van Dobben de Bruyn, we construct examples for every modulus. In this post, I will give some background on how these systems relate to quantum theory and contextuality, then illustrate our result with an example.

---

Contents

1. What is an operator solution?
2. The original Mermin-Peres magic square
3. Measurements and contextuality
4. Our result
5. Magic rectangle modulo 3
6. The group generated by the magic square
7. From groups to linear systems
8. Related work

---

1. What is an operator solution?

Consider a linear system $Ax=b$ over $\mathbb Z/d\mathbb Z$. Writing $\omega=e^{2\pi i/d}$, we can encode a number $x_j$ by the scalar $\omega^{x_j}$. This turns each additive equation into a multiplicative one:

\[\sum_j A_{ij}x_j=b_i \quad\Longleftrightarrow\quad \prod_j (\omega^{x_j})^{A_{ij}}=\omega^{b_i}.\]

An operator solution replaces these scalars by unitary matrices $U_j$ of a common size, satisfying

\[U_j^d=I, \qquad \prod_j U_j^{A_{ij}}=\omega^{b_i}I.\]

There is one essential condition: matrices belonging to variables in the same equation must commute. Matrices appearing in different equations need not commute, and this is where new solutions become possible. Ordinary solutions correspond exactly to matrices of size $1$.

---

2. The original Mermin-Peres magic square

Start with nine variables $x_1,\ldots,x_9\in\mathbb Z/2\mathbb Z$, arranged in a $3\times3$ square. The numbers to the right and below specify the required row and column sums, all modulo $2$:

Thus each row sums to $0$, the first two columns sum to $0$, and the last column sums to $1$. Adding the row equations says that the sum of all nine bits is $0$; adding the column equations says it is $1$.

Equivalently, set $s_j=\omega^{x_j}$, where $\omega=e^{2\pi i/2}=-1$. We then seek a square of signs whose row products are all $+1$ and whose column products are $+1,+1,\omega$. No such square of numbers exists.

Here is its operator solution. Take the Pauli matrices

\[X=\begin{pmatrix}0&1\\1&0\end{pmatrix}, \qquad Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix}, \qquad Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}.\]

Replace each sign $s_j$ by the $4\times4$ matrix in the corresponding cell below. The entries to the right and below now give the row and column products:

Every entry squares to $I_4$, and the entries in each row or column commute pairwise. The factor $\omega$ in the last column comes from $XZ=-iY$:

\[(X\otimes X)(Z\otimes Z)(Y\otimes Y) =(XZY)\otimes(XZY) =(-iI_2)\otimes(-iI_2) =\omega I_4.\]

In the third row, the two signs instead cancel: $(X\otimes Z)(Z\otimes X)=(-iY)\otimes(iY)=Y\otimes Y$, so multiplying by the last entry gives $I_4$. Thus the square satisfies precisely the matrix equations corresponding to the impossible system of bits. This is the Mermin-Peres magic-square argument, expressed in the language of linear systems.

---

3. Measurements and contextuality

In quantum theory, an observable is represented by a Hermitian matrix $A$, whose spectral decomposition $A=\sum_a aP_a$ expresses it in terms of its distinct eigenvalues $a$ and the orthogonal projections $P_a$ onto their eigenspaces. These projections define a projective measurement: for a normalized state vector $\psi$, it returns the outcome $a$ with probability $\lVert P_a\psi\rVert^2$. The nine matrices in our square are observables of a pair of qubits: each is Hermitian, with eigenvalues $+1$ and $-1$, which are its possible measurement outcomes. For example, $X\otimes I$ measures the first qubit in the $X$ basis, while $I\otimes X$ measures the second. A commuting row or column has a common eigenbasis, so its three observables can be measured jointly. Such a compatible set of measurements is called a context. Some entries in different contexts do not commute, so the nine observables cannot all be measured by a single projective measurement.

The matrix identities give exact constraints on the outcomes of these joint measurements. If commuting observables $A,B,C$ satisfy $ABC=I_4$, their joint eigenvalues $a,b,c$ satisfy $abc=+1$; if $ABC=\omega I_4$, they satisfy $abc=\omega=-1$. Consequently, quantum theory predicts that the product of the three outcomes is always $+1$ for any row or either of the first two columns, and always $-1$ for the last column. These statements hold for every two-qubit state, even though the individual outcomes can be random.

In the usual classical picture, it is natural to think that ideal measurements reveal properties that the system already has. For example, a classical particle has a definite position $(x,y,z)$: reading its $x$ coordinate gives the same value whether we also read $y$ or $z$, provided the measurements do not disturb its position. Uncertainty about the particle’s state can make the answer unpredictable, but the value itself does not depend on which other coordinates we choose to read.

To apply this classical intuition to the square, imagine that each prepared pair of qubits comes with a hidden, prewritten answer sheet. The sheet is a $3\times3$ grid containing one sign, $+1$ or $-1$, for each of the nine observables. Different runs may use different sheets, even when we prepare exactly the same quantum state. The hidden state $\lambda$ tells us which sheet is used in a particular run.

After the sheet is fixed, we independently choose a row or column to measure and read off its three answers. The assumption of noncontextuality is that the answer depends on the observable and the hidden state $\lambda$, but not on the context. We write this answer as $v_\lambda(A)$: $\lambda$ specifies the sheet, and $A$ specifies the cell to read. Thus $v_\lambda(X\otimes X)$ is determined by the sheet, regardless of whether we choose the first row or the last column. Different runs can use different sheets and give different answers; noncontextuality says that choosing a context does not change the answer on a given sheet.

We only read one row or column in each run, but the sheet must be ready for any of the six choices. To reproduce these quantum predictions about row and column products, every sheet the model uses must satisfy all six constraints. If a sheet fails one of them, choosing that row or column reveals the failure. Yet no such sheet exists: multiplying the three row constraints gives $+1$, while multiplying the three column constraints gives $-1$. Both calculations multiply the same nine signs, so they must give the same answer. Drawing sheets at random cannot help, because every sheet fails at least one of the possible checks.

This is Kochen-Specker contextuality: the quantum predictions cannot be explained by a common collection of answer sheets with one answer per observable. The contradiction is state-independent because the product constraints hold in every quantum state. Quantum mechanics still gives the same probabilities for an individual observable whether we measure it in its row or its column. What fails is the idea that all the outcomes come from nine answers written down in advance. Contextual hidden-variable models allow an observable’s answer to depend on which other observables are measured alongside it, so they are outside this assumption. For further background, see the review of Kochen-Specker contextuality by Budroni, Cabello, Gühne, Kleinmann, and Larsson.

---

4. Our result

Every modulus $d\geq2$ admits a linear system with no numerical solution but with an operator solution. The difficult case is odd modulus: simply replacing the Pauli matrices in the usual magic square by their higher-dimensional analogues does not work. In fact, for odd modulus, any system solvable using generalized Pauli matrices also has a classical solution. Our construction goes beyond this family.

---

5. Magic rectangle modulo 3

Until recently, no example of a linear system with an operator solution but no numerical solution was known even modulo $3$. Our example modulo $3$ has $18$ variables $x_1,\ldots,x_{18}\in\mathbb Z/3\mathbb Z$ arranged in a $5\times6$ rectangle. The remaining cells contain zeros, and the numbers to the right and below specify the required row and column sums, all modulo $3$:

Thus the first four rows and all six columns sum to $0$, while the last row sums to $1$. There is no numerical solution: adding the row equations gives $\sum_{j=1}^{18}x_j=1$, while adding the column equations gives the same sum equal to $0$.

The explicit $9\times9$ operator solution can be found in Section 2 of our paper.

---

6. The group generated by the magic square

The nine operators in the original Mermin-Peres magic square generate the real two-qubit Pauli group, which has $32$ elements. Adjoining the scalar matrix $iI_4$ to this group gives the usual $64$-element two-qubit Pauli group. We now describe the $32$-element real two-qubit Pauli group, denoted by $G$, as a semidirect product.

Let $E=\mathbb F_2^2$, and let $\mathcal A_1=\operatorname{span}_{\mathbb F_2}\lbrace1,x,y\rbrace$ be the space of affine linear functions on $E$. Label the four standard basis vectors by $e_z$ for $z\in E$, and set $\omega=-1$. The group combines diagonal matrices with translations of these basis vectors:

\[D_f e_z=\omega^{f(z)}e_z,\qquad S_a e_z=e_{z-a}, \qquad f\in\mathcal A_1,\quad a\in E.\]

Every element is uniquely a product $D_fS_a$, giving

\[G\cong\mathcal A_1\rtimes E \cong(\mathbb Z/2\mathbb Z)^3\rtimes(\mathbb Z/2\mathbb Z)^2.\]

The action in this semidirect product is translation of functions: $(T_af)(z)=f(z+a)$. In matrix terms, $S_aD_fS_a^{-1}=D_{T_af}$.

This is exactly the group $G_{2,1}$ in our paper. For an odd prime $p$, our group has the same form $G_{p,p-1}=\mathcal A_{p-1}\rtimes\mathbb F_p^2$, where $\mathcal A_{p-1}$ consists of polynomials in two variables of total degree at most $p-1$ over $\mathbb F_p$. Thus we keep the translation action and enlarge the space of diagonal phase functions beyond the affine linear ones.

---

7. From groups to linear systems

There is a general way to turn the commuting relations of a group into a linear system. Start with a finite group $G$ and a central element $J$ of order $d$. Introduce a variable $x_u$ for every element $u\in G$ satisfying $u^d=e$, where $e$ is the identity. For every commuting pair of these elements, impose an equation, and add one final constraint:

\[\begin{aligned} x_u+x_v&=x_{uv} &&\text{whenever }uv=vu,\\ x_J&=1. \end{aligned}\]

All arithmetic is modulo $d$. The variable $x_{uv}$ exists because commuting elements with $u^d=v^d=e$ also satisfy $(uv)^d=e$. If $G$ is represented by unitary matrices $\rho(u)$ with $\rho(J)=\omega I$, where $\omega=e^{2\pi i/d}$, then assigning $U_u=\rho(u)$ gives an operator solution: the first equations express multiplication of commuting matrices, and the last one is exactly $U_J=\omega I$.

A numerical solution would assign a value $\ell(u)=x_u$ to each of these group elements, satisfying $\ell(uv)=\ell(u)+\ell(v)$ whenever $u$ and $v$ commute, together with $\ell(J)=1$. For the real two-qubit Pauli group, the magic-square argument already shows that such an assignment is impossible.

For our groups $G_{p,p-1}$ with $p$ odd, we set $d=p$ and prove that additivity on commuting pairs forces $\ell(J)=0$, where $J=(1,0)$ corresponds to the scalar matrix $\omega I$ and $\omega=e^{2\pi i/p}$. The proof compares the restrictions of $\ell$ to certain abelian subgroups whose elements satisfy $u^p=e$. On each such subgroup, $\ell$ must be linear; the relations between these subgroups then force $\ell(J)=0$. This contradicts the required equation $x_J=1$, so the system has an operator solution but no numerical solution. The general construction and the contradiction are given in Sections 3 and 5 of our paper.

---

8. Related work

There was also a little arXiv drama: Lorenzo Ciardo and Markus Frembs independently obtained the same existence result using different techniques, with all three preprints appearing within days of each other!

---