#### Quantum Science Seminar

# The sign rank of a matrix

An interdisciplinary group of faculty & students studies problems in the theory of quantum information processing. A brief review of the most recent publications will be followed by a presentation on a specific paper or set of papers. All faculty and students are welcome.

Given a matrix A with entries in the set {1,-1}, the smallest possible rank of a real matrix B whose nonzero entries have the signs as prescribed by A, is called the sign-rank of A. It seems hard to find good lower bounds for the sign-rank of a matrix. I will explain a result of Forster that gives a lower bound for the sign-rank of A in terms of its spectral norm. In particular, the sign-rank of an n x n Hademard matrix is at last sqrt(n). I will also discuss the applicationof this result to communication complexity.