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.