Geodesic
Improved lower bounds on the rigidity of Hadamard matrices
Matematičeskie zametki, Tome 63 (1998) no. 4, pp. 535-540

Voir la notice de l'article provenant de la source Math-Net.Ru

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)$. 
@article{MZM_1998_63_4_a6,
     author = {B. S. Kashin and A. A. Razborov},
     title = {Improved lower bounds on the rigidity of {Hadamard} matrices},
     journal = {Matemati\v{c}eskie zametki},
     pages = {535--540},
     publisher = {mathdoc},
     volume = {63},
     number = {4},
     year = {1998},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_1998_63_4_a6/}
}
TY  - JOUR
AU  - B. S. Kashin
AU  - A. A. Razborov
TI  - Improved lower bounds on the rigidity of Hadamard matrices
JO  - Matematičeskie zametki
PY  - 1998
SP  - 535
EP  - 540
VL  - 63
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_1998_63_4_a6/
LA  - ru
ID  - MZM_1998_63_4_a6
ER  - 
%0 Journal Article
%A B. S. Kashin
%A A. A. Razborov
%T Improved lower bounds on the rigidity of Hadamard matrices
%J Matematičeskie zametki
%D 1998
%P 535-540
%V 63
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_1998_63_4_a6/
%G ru
%F MZM_1998_63_4_a6
B. S. Kashin; A. A. Razborov. Improved lower bounds on the rigidity of Hadamard matrices. Matematičeskie zametki, Tome 63 (1998) no. 4, pp. 535-540. http://geodesic.mathdoc.fr/item/MZM_1998_63_4_a6/