EECS | Electrical Engineering and Computer Science

Quantum Info Processing Seminar

The sign rank of a matrix

Harm Derksen

Mathematics Department, University of Michigan, Ann Arbor
Friday, October 04, 2013
1:30pm - 3:00pm
2733 Beyster Bldg.

Add to Google Calendar
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.

About the Event

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 application of this result to communication complexity.

Additional Information

Contact: Carl Miller


Sponsor(s): EECS

Open to: Public

Web Page: