Improved lower bounds on the rigidity of Hadamard matrices

B. S. Kashin ; A. A. Razborov

Matematičeskie zametki, Tome 63 (1998) no. 4, pp. 535-540.

Résumé

We write$f=\Omega(g)$ if $f(x)\ge cg(x)$ with some positive constant $c$ for all $x$ from the domain of functions $f$ and $g$. We show that at least $\Omega(n^2/r)$ entries must be changed in an arbitrary (generalized) Hadamard matrix in order to reduce its rank below $r$. This improves the previously known bound $\Omega(n^2/r^2)$. If we additionally know that the changes are bounded above in absolute value by some number $\theta\ge n/r$, then the number of these entries is bounded below by $\Omega(n^3/(r\theta^2))$, which improves upon the previously known bound $\Omega(n^2/\theta^2)$.

Bibliographie

[1] Valiant L. G., Some Conjectures Relating to Superlinear Complexity Bounds, Tech. Report No 85, Univ. of Leeds, 1976

[2] Valiant L. G., Graph-Theoretic Arguments in Low-Level Complexity, Tech. Report No 13-77, Univ. of Edinburgh, Dept. of Comp. Sci., 1977

[3] Grigorev D. Yu., “Ispolzovanie ponyatii otdelennosti i nezavisimosti dlya polucheniya nizhnikh otsenok slozhnosti skhem”, Zapiski nauch. sem. LOMI, 60, Nauka, L., 1976, 38–48 | MR | Zbl

[4] Grigorev D. Yu., “Nizhnie otsenki v algebraicheskoi slozhnosti vychislenii”, Zapiski nauch. sem. LOMI, 118, Nauka, L., 1982, 25–82 | MR | Zbl

[5] Razborov A. A., Ob ustoichivykh matritsakh, Preprint, MIAN, M., 1989

[6] Lokam S. V., “Spectral methods for matrix rigidity with applications to size-depth tradeoffs and communication complexity”, Proc. of the 36th IEEE Symposium on Foundations of Computer Science, IEEE, Los Alamitos (C.A.), 1995, 6–15 | Zbl

[7] Friedman J., “A note on matrix rigidity”, Combinatorica, 13:2 (1993), 235–239 | DOI | MR | Zbl

[8] Pudlák P., Vavr̆ín Z., “Computation of rigidity of order $n^2/r$ for one simple matrix”, Comment. Math. Univ. Carolin., 32:2 (1991), 213–218 | MR | Zbl

[9] Kimmel P., Settle A., Reducing the Rank of Lower Triangular All-Ones Matrix, Tech. Report CS 92-21, Univ. of Chicago, 1992

[10] Pudlák P., “Large communication in constant depth circuits”, Combinatorica, 14:2 (1994), 203–216 | DOI | MR | Zbl

[11] Krause M., Waack S., “Variation ranks of communication matrices and lower bounds for depth two circuits having symmetric gates with unbounded fan-in”, Proc. of the 32nd IEEE Symposium on Foundations of Computer Science, IEEE, Los Alamitos (C.A.), 1991, 777–782 | MR

[12] Nisan N., Wigderson A., “On the complexity of bilinear forms”, Proceedings of the 27th ACM Symposium on the Theory of Computing, ACM, New York, 1995, 723–732 | Zbl

[13] Pudlák P., Razborov A., Savický P., Observations on Rigidity of Hadamard Matrices, Manuscript, 1988

[14] Alon N., On the Rigidity of Hadamard Matrices, Manuscript, Tel Aviv Univ., 1990

[15] Hoffman A. J., Wielandt H. W., “The variation of the spectrum of a normal matrix”, Duke Math. J., 20 (1953), 37–39 | DOI | MR | Zbl

[16] Golub G. H., van Loan C. F., Matrix Computations, John Hopkins Univ. Press, Baltimore, Maryland, 1983 | Zbl

[17] Kashin B. S., “O nekotorykh svoistvakh matrits ogranichennykh operatorov iz prostranstva $\ell_2^n$ v $\ell_2^m$”, Izv. AN ArmSSR. Matem., 15:5 (1980), 379–394 | MR | Zbl

[18] Lunin A. A., “Ob operatornykh normakh podmatrits”, Matem. zametki, 45:3 (1989), 94–100 | MR

[19] Kashin B., Tzaffiri L., Some Remarks on the Restriction of Operators to Coordinate Subspaces, Tech. Report No 12, The Edmund Landau Center for Research in Math. Anal., Hebrew Univ., Jerusalem, 1993/94

[20] Rudelson M., “Almost orthogonal submatrices of an orthogonal matrix”, Israel J. Math. (to appear)