home | literature reviews

"Geometric search for Hadamard matrices", Jeffery Kline, 2019

Reviewed September 12, 2023

Citation: Kline, Jeffery. "Geometric search for Hadamard matrices." Theoretical Computer Science 778 (2019): 33-46.

Web: https://www.sciencedirect.com/science/article/pii/S0304397519300507

Tags: Computer-scientific, Hadamard-matrices

This paper gives a very nice perspective on the redundancy inherent to Hadamard matrices. Given an n by n Hadamard matrix, removing n entries means that it cannot be reconstructed: a whole column could have been removed, and there are two choices of ways to reconstruct this column depending on choice of global phase. If you want want to see how many entries you can remove and still recover your matrix and still have a high probability of recovering the original, the answer is shockingly high: on the order of n^2/log(n), a large fraction of all the entries!

Not only does this help establish the redundancy of Hadamard matrices, it also helps establish the nice error correction potential: the algorithm for reconstructing the original matrix from the one with its entries deleted is very efficient, running in time no longer than matrix multiplication. Efficient!

This paper also focuses on the application of this reconstruction result to the construction of Hadamard matrices.