Let \sigma_1 and \sigma_3 be Pauli matrices (see https://en.wikipedia.org/wiki/Pauli_matrices) and let I be the identity matrix (all of these matrices are square matrices of size 2).

Now let

B_1 = \sigma_3 \otimes I \otimes \cdots \otimes I,

B_2= \sigma_1 \otimes \sigma_3 \otimes I \otimes \cdots \otimes I,

B_3= \sigma_1 \otimes \sigma_1 \otimes \sigma_3 \otimes I \otimes \cdots \otimes I,

…

B_n= \sigma_1 \otimes \cdots \otimes \sigma_1 \otimes \sigma_3;

(B_i contains exactly one factor \sigma_3 on i-th position, all factors before it are equal to \sigma_3 and all factors after it are equal to the identity matrix I).

Note that the matrices B_i described above appear naturally in the context of quantum mechanics for the following reason: since Pauli matrices anticommute: \sigma_1 \sigma_3=- \sigma_3 \sigma_1, it follows that the matrices B_i anticommute as well: B_i B_j = – B_j B_i whenever i\neq j. Also, (B_i)^2=I\otimes \cdots \otimes I is the identity matrix.

Luckily, we have that A=B_1+\cdots+B_n is a (signed) adjacency matrix for the graph we are interested in.

From the anticommutation of the matrices B_i it follows immediately that

A^2=(B_1+\cdots+B_n)^2= n.

(but I’m not sure if God will vote for it) ]]>

I’m a long-time reader of your blog, though I’ve only commented a couple of times since I usually don’t have much to add. But this time, I noticed something about the “magical” pattern of 1’s and -1’s that you might find interesting. Consider the following slightly modified pattern:

A_1 = 0,1;-1,0

A_n = A_{n-1}, I; -I, -A_{n-1}

First, this matrix has eigenvalues +-sqrt(-n) and is anti-symmetric, but I think a modified version of Lemma 2.3 would still go through.

Second, it is the adjacency matrix of a directed version of the cube graph. And not just any cube graph, but in fact the *Klee-Minty cube*! The KM cube is a notable example of a *unique sink orientation*, which are a purely combinatorial representations of various optimization problems such as linear programming. The KM cube can be used to show that the simplex algorithm may need exponentially long to solve a LP, since it contains a Hamilton path of length 2^n – 1.

So, I am not that surprised to see a construction similar to Klee-Minty cubes used here, as it basically maximizes “askewness” in some sense. Both Will Sawin #12 and Sankeerth Rao #22 make correct observations about the properties of this cube. In particular, the operation of “flipping all the bits at one vertex” mentioned by #22 turns the KM cube into an *odd USO*, which we observed in this paper: https://arxiv.org/pdf/1704.08481.pdf (see Lemma 21).

]]>