New proofs of the Kochen–Specker theorem via Hadamard matrices

We demonstrate that Hadamard matrices and their generalizations can be used to prove the Kochen–Specker (KS) theorem. In particular, we prove that large classes of classical and generalized Hadamard matrices can be used to construct so-called KS pairs, which provide such proofs. We construct an infinite family of KS pairs by showing that for any odd prime p, there exists a KS pair in C^2p using p^4 vectors and p^3 orthogonal bases. Each of these pairs is shown to correspond to a 1-factorization of the complete graph K_2p. We explore various computational approaches to the search for new KS pairs. We develop an integer linear programming approach for testing whether an arbitrary set of vectors and bases forms a KS pair, which we use to simplify some existing KS pairs.