Three lines proof of the lower bound for the matrix rigidity
| dc.creator | Midrijanis, Gatis | |
| dc.date | 2005-06-20 | |
| dc.date | 2005-06-20 | |
| dc.date.accessioned | 2026-07-07T03:23:09Z | |
| dc.date.available | 2026-07-07T03:23:09Z | |
| dc.description | The rigidity of a matrix describes the minimal number of entries one has to change to reduce matrix's rank to r. We give very simple combinatorial proof of the lower bound for the rigidity of Sylvester (special case of Hadamard) matrix that matches the best known result by de Wolf(2005) for Hadamard matrices proved by quantum information theoretical arguments. | |
| dc.description | 4 pages | |
| dc.identifier | https://arxiv.org/abs/cs/0506081 | |
| dc.identifier | http://arxiv.org/abs/cs/0506081 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/32835 | |
| dc.subject | Computational Complexity | |
| dc.title | Three lines proof of the lower bound for the matrix rigidity | |
| dc.type | text |