The rigidity of a matrix A for target rank r is the minimum number of entries of A that need to be changed in order to obtain a matrix of rank at most r. Matrix rigidity was introduced by Valiant in 1977 as a tool to prove circuit lower bounds for linear functions and since then this notion has also found applications in other areas of complexity theory. Recently (arXiv 2021) , Alman proved that for any field \mathbb{F, d\geq 2 and arbitrary }  matrices M_1, \ldots, M_n \in \mathbb{F^{d\times d}, one can get a d^n\times d^n matrix of rank }%DIFDELCMD < \le %%% d^{(1-\gamma)n \dots\ge  ^{ ( 1+\varepsilon ) n } entries of the Kronecker product M = M_1\otimes M_2\otimes \ldots\otimes M_n\le  , where 1/\gamma is roughly 2^d/\varepsilon^2. In this note we improve this result in two directions. First, we do not require the matrices M_i to have equal size. Second, we reduce 1/\gamma from exponential in d to roughly d^{3/2}/\varepsilon^2 (where d is the maximum size of the matrices  ), and to nearly linear (roughly d/\varepsilon^2) for matrices M_i of sizes within a constant factor of each other. For the case of matrices of equal size, our bound matches the bound given by Dvir and Liu (\textit{Theory of Computing, 2020 ) for the rigidity of generalized Walsh--Hadamard matrices (Kronecker powers of DFT matrices ), and improves their bounds for DFT matrices of abelian groups that are direct products of small groups .
The rigidity of a matrix A for target rank r is the minimum number of entries of A that need to be changed in order to obtain a matrix of rank at most r. At MFCS'77, Valiant introduced matrix rigidity as a tool to prove circuit lower bounds for linear functions and since then this notion received much attention and found applications in other areas of complexity theory. , d\geq 2 and arbitrary } The problem of constructing an explicit family of matrices that are sufficiently rigid for Valiant's reduction (Valiant-rigid) still remains open. Moreover, since 2017 most of the long-studied candidates have been shown not to be Valiant-rigid. Some of those former candidates for rigidity are Kronecker products of small matrices. In a recent paper (STOC'21), Alman gave a general non-rigidity result for such matrices: he showed that if an n\times n matrix A (over any field) is a Kronecker product of d\times d matrices M_1, ^{d\times d}, one can get a d^n\times d^n matrix of rank }%DIFDELCMD < \le %%% \dots, M_k (so n=d^k) (d\ge 2) then changing only n ^{ 1+\varepsilon } entries of A one can reduce its rank to\le n^{1-\gamma , where 1/\gamma is roughly 2^d/\varepsilon^2. In this note we improve this result in two directions. First, we do not require the matrices M_i to have equal size. Second, we reduce 1/\gamma from exponential in d to roughly d^{3/2}/\varepsilon^2 (where d is the maximum size of the matrices M_i ), and to nearly linear (roughly d/\varepsilon^2) for matrices M_i of sizes within a constant factor of each other. \textit{ As an application of our results we significantly expand the class of Hadamard matrices that are known not to be Valiant-rigid; these now include the Kronecker products of Paley-Hadamard matrices and Hadamard matrices of bounded size .
R
Matrix rigidity was introduced by Valiant in 1977
At MFCS'77, Valiant introduced matrix rigidity
R
has also
received much attention and
D
Recently (arXiv 2021) , Alman proved that for any field \mathbb{F
A
The problem of constructing an explicit family of matrices that are sufficiently rigid for Valiant's reduction (Valiant-rigid) still remains open. Moreover, since 2017 most of the long-studied candidates have been shown not to be Valiant-rigid. Some of those former candidates for rigidity are Kronecker products of small matrices. In a recent paper (STOC'21), Alman gave a general non-rigidity result for such matrices: he showed that if an n\times n matrix A (over any field) is a Kronecker product of d\times d
D
\ldots, M_n \in \mathbb{F
D
d^{(1-\gamma)n
A
, M_k (so n=d^k) (d
A
2) then changing only n
D
(
D
) n
R
the Kronecker product M = M_1\otimes M_2\otimes \ldots\otimes M_n
A one can reduce its rank to
A
n^{1-\gamma
A
M_i
D
For the case of matrices of equal size, our bound matches the bound given by Dvir and Liu (
D
Theory of Computing, 2020
R
) for the rigidity of generalized Walsh--Hadamard matrices (Kronecker powers of DFT matrices ), and improves their bounds for DFT matrices of abelian groups that are direct products of small groups
As an application of our results we significantly expand the class of Hadamard matrices that are known not to be Valiant-rigid; these now include the Kronecker products of Paley-Hadamard matrices and Hadamard matrices of bounded size