# Improved upper bounds for the rigidity of Kronecker products111This paper is
to appear in the proceedings of the 46th International Symposium on
Mathematical Foundations of Computer Science (MFCS’21)

Bohdan Kivva
University of Chicago
<EMAIL_ADDRESS>
###### Abstract

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. 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},\dots,M_{k}$
(so $n=d^{k}$) $(d\geq 2)$ then changing only $n^{1+\varepsilon}$ entries of
$A$ one can reduce its rank to $\leq 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.

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.

##  1 Introduction

###  1.1 Recent upper bounds on rigidity

In his celebrated MFCS’77 paper [13], Leslie Valiant introduced the notion of
matrix rigidity as a tool to prove lower bounds for arithmetic circuits. Since
then, several other important problems in complexity theory have been reduced
to proving rigidity lower bounds for explicit families of matrices (see, e.g.,
[12, 7] and the survey [10]).

######  Definition 1.1.

Let $\mathbb{F}$ be a field. For a matrix $A\in\mathbb{F}^{n\times m}$ and a
target rank $0\leq r\leq\min(n,m)$ let $R_{\mathbb{F}}(A,r)$ denote the
minimum number of non-zero entries in a matrix $Z\in\mathbb{F}^{n\times m}$
such that $\operatorname{rank}(A-Z)\leq r$. The function
$R_{\mathbb{F}}(A,\cdot)$ is called the _rigidity_ of $A$ over $\mathbb{F}$.

Valiant [13] proved that if for some $\varepsilon>0$ the sequence of matrices
$A_{n}\in\mathbb{F}^{n\times n}$ satisfies

$R_{\mathbb{F}}(A_{n},n/\log\log n)\geq n^{1+\varepsilon},$ (1)

then the linear functions $x\mapsto A_{n}x$ cannot be computed by arithmetic
circuits of size $O(n)$ and depth $O(\log n)$. Following [5], we say that a
family of matrices $A_{n}$ is _Valiant-rigid_ if it satisfies Eq. (1) for some
$\varepsilon>0$ and all sufficiently large $n$. By saying that a family
$\mathcal{F}$ of matrices in not Valiant-rigid we mean that none of the
subsequences of matrices of $\mathcal{F}$ of increasing order is Valiant-
rigid.

The problem of constructing explicit Valiant-rigid matrices has been attacked
for more than four decades, but still remains open (see the survey [10]). Over
this time a few candidates of Valiant-rigid families were proposed that
included Hadamard matrices [11, 12], circulants [4], Discrete Fourier Transorm
(DFT) matrices [13], incidence matrices of projective planes over a finite
field [13].

In 2017, Alman and Williams [2] proved, that, contrary to expectations, the
Walsh–Hadamard matrices are not Valiant-rigid over $\mathbb{Q}$. Subsequently,
most of other long-studied candidates for rigidity were shown not to be
Valiant-rigid. Dvir and Edelman [5] proved that $G$-circulants222For a finite
abelian group $G$, a _$G$ -circulant_ is a $|G|\times|G|$ matrix of the form
$M(f)$ with entries $M(f)_{xy}=f(x-y)$ $(x,y\in G)$ where $f$ is any function
with domain $G$. are not Valiant-rigid over $\mathbb{F}_{p}$ for $G$ the
additive group of $\mathbb{F}_{p}^{n}$. Dvir and Liu [6] proved that DFT
matrices, circulant matrices, and more generally, $G$-circulant matrices for
any abelian group $G$, are not Valiant-rigid over $\mathbb{C}$. Moreover, as
observed in [3], the results of Dvir and Liu imply that the Paley-Hadamard
matrices and the Vandemonde matrices with a geometric progression as
generators are not Valiant-rigid over $\mathbb{C}$, and the incidence matrices
of projective planes over finite fields are not Valiant-rigid either over
$\mathbb{F}_{2}$ (contrary to Valiant’s suggestion [13]) or over $\mathbb{C}$.

Upper bounds on the rigidity of the Kronecker powers of a fixed matrix play an
important role in these results. Indeed, the Walsh–Hadamard matrices are just
the Kronecker powers of $H_{2}=\left(\begin{matrix}1&1\\\
1&-1\end{matrix}\right)$. Furthermore, in order to show that DFT and circulant
matrices are not Valiant-rigid, as the first step, Dvir and Liu [6] prove that
generalized Walsh–Hadamard matrices (Kronecker powers of a DFT matrix) are not
Valiant-rigid.

Hence, one may expect that strong upper bounds on the rigidity of Kronecker
products of small matrices may lead to upper bounds on the rigidity of
interesting new families of matrices, and so will further contribute to our
intuition of where not to look for Valiant-rigid matrices.

Recently, Josh Alman [1] proved that Kronecker products of square matrices of
any _fixed_ size are not Valiant-rigid. More precisely, he proved the
following result.

######  Theorem 1.2 (Alman).

Given $d\geq 2$ and $\varepsilon>0$, there exists
$\gamma=\Omega\left(\dfrac{d\log
d}{2^{d}}\cdot\dfrac{\varepsilon^{2}}{\log^{2}(1/\varepsilon)}\right)$ such
that the following holds for any sequence of matrices
$M_{1},M_{2},\ldots,M_{k}\in\mathbb{F}^{d\times d}$. Let
$M=\bigotimes\limits_{i=1}^{k}M_{i}$ and $n=d^{k}$. Then
$R_{\mathbb{F}}(M,n^{1-\gamma})\leq n^{1+\varepsilon}$.

###  1.2 Our results: improved bounds, non-uniform sizes

In this note we improve Alman’s 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$)
for matrices $M_{i}$ of sizes within a constant factor of each other.

This means that for matrices of equal size we get a meaningful reduction of
the rank already for $k=\widetilde{O}_{\varepsilon}(d)$, in contrast to
Alman’s result that kicks in when $k$ reaches about $2^{d}$.

######  Theorem 1.3.

Given $d\geq 2$ and $\varepsilon>0$, there exists
$\gamma=\Omega\left(\dfrac{1}{d^{3/2}\log^{3}(d)}\cdot\dfrac{\varepsilon^{2}}{\log^{2}(1/\varepsilon)}\right)$
such that the following holds for any sequence of matrices
$M_{1},M_{2},\ldots,M_{k}$ where $M_{i}\in\mathbb{F}^{d_{i}\times d_{i}}$ for
some $d_{i}\leq d$. Let $M=\bigotimes\limits_{i=1}^{k}M_{i}$ and
$n=\prod\limits_{i=1}^{k}d_{i}$. If $n\geq d^{1/\gamma}$, then
$R_{\mathbb{F}}(M,n^{1-\gamma})\leq n^{1+\varepsilon}$.

If the $d_{i}$ are within a constant factor of each other, we obtain the
following stronger result.

######  Theorem 1.4.

Given $d\geq 2$, $\varepsilon>0$, and a constant $c>0$, there exists
$\gamma=\Omega_{c}\left(\dfrac{1}{d\log
d}\cdot\dfrac{\varepsilon^{2}}{\log^{2}(1/\varepsilon)}\right)$ such that the
following holds for any sequence of matrices $M_{1},M_{2},\ldots,M_{k}$ where
$M_{i}\in\mathbb{F}^{d_{i}\times d_{i}}$ and $cd\leq d_{i}\leq d$. Let
$M=\bigotimes\limits_{i=1}^{k}M_{i}$ and $n=\prod\limits_{i=1}^{k}d_{i}$. If
$n\geq d^{1/\gamma}$, then $R_{\mathbb{F}}(M,n^{1-\gamma})\leq
n^{1+\varepsilon}$.

In the above theorem, the dependence of $\gamma$ on $c$ is nearly linear and
the explicit formula can be found in Corollary 5.2.

The key strength of our results is that we do not need to assume uniform size
of the matrices participating in the Kronecker product. Previous approaches
depended on uniform size because of their reliance either on a polynomial
method, or on an induction on the size of the matrix. As an applications of
the bound for matrices of non-uniform size we show that our results
significantly expand the class of Hadamard matrices that are known not to be
Valiant-rigid. We show that the Kronecker products of Paley-Hadamard matrices
and Hadamard matrices of bounded size are not Valiant-rigid (see Sec. 1.4).

Another strength of our improvement is that our bounds are sufficiently strong
to be fed into the machinery developed by Dvir and Liu [6] for matrices of
“well-factorable” size. Hence, we expect that this improvement might lead to
further applications.

We note, that our bound on $\gamma$ in Theorem 1.4 matches the Dvir–Liu bounds
for Kronecker powers of specific classes of matrices, such as the generalized
Walsh–Hadamard matrices and DFT matrices333The DFT (Discrete Fourier
Transform) matrix of a finite abelian group $G$ is the character table of $G$.
of direct products of small abelian groups.

We also note that our upper bounds, similarly to upper bounds in recent work
[2, 5, 6, 1], apply to a stronger notion of rigidity, called _row-column
rigidity_.

######  Definition 1.5 (Row-column rigidity).

For a matrix $A\in\mathbb{F}^{n\times n}$ and a target rank $0\leq r\leq n$,
let $R^{rc}_{\mathbb{F}}(A,r)$ be the minimal $t$ for which there exists
$Z\in\mathbb{F}^{n\times n}$ such that $\operatorname{rank}(A-Z)\leq r$ and
every row and column of $Z$ has at most $t$ non-zero entries.

In Theorems 1.2, 1.3, and 1.4 the conclusion can be replaced by
$R^{rc}_{\mathbb{F}}(M,n^{1-\gamma})\leq n^{\varepsilon}$. Clearly, the latter
statement is stronger, as for any $A\in\mathbb{F}^{n\times n}$ the inequality
$R_{\mathbb{F}}(A,r)\leq n\cdot R_{\mathbb{F}}^{rc}(A,r)$ holds. The row-
column versions of Theorems 1.3, and 1.4 are stated and proved as Theorem 5.4
and Corollary 5.3.

###  1.3 The field

We should point out that Theorems 1.2-1.4 make no assumption about the field
$\mathbb{F}$, and they use elements of $\mathbb{F}$ for the rank reduction.
This is in contrast to the results of Dvir and Liu who require a field
extension to achieve their rank reduction.

If the field $\mathbb{F}$ is the field of definition of the matrix $A$, in [3]
we call the corresponding rigidity function $R_{\mathbb{F}}(A,.)$ the _strict
rigidity_ of $A$. If $\overline{\mathbb{F}}$ denotes the algebraic closure of
$\mathbb{F}$ then we call $R_{\overline{\mathbb{F}}}(A,.)$ the _absolute
rigidity_ of $A$ because, as shown in [3], this gives the smallest possible
rigidity among all extension fields. A gap between these two quantities is
demonstrated in [3]. Note that an upper bound on strict rigidity is a stronger
statement than the same upper bound on absolute rigidity.

In this terminology, Dvir and Liu give upper bounds on absolute rigidity,
whereas Alman’s result and our results give upper bounds on strict rigidity.

###  1.4 Application of our results: rigidity upper bounds for Hadamard
matrices

We recall that an _Hadamard matrix_ is a square matrix whose entries are $+1$
and $-1$ and whose rows are mutually orthogonal. In addition to many other
interesting properties, it was long believed that one can find a family of
Valiant-rigid matrices among Hadamard matrices.

Contrary to expectations, two of the most well-studied families of Hadamard
matrices were recently shown to be not Valiant-rigid. In 2017, Alman and
Williams [2] proved that Walsh-Hadamard matrices are not strictly Valiant-
rigid. As a corollary to [6], in [3] it was shown that Paley-Hadamard matrices
are not absolutely Valiant-rigid. These results inspired the following
conjecture.

######  Conjecture 1.6 (Babai).

The family of known Hadamard matrices is not strictly Valiant-rigid.

We mention that in addition to infinite families, new classes of Hadamard
matrices arise as Kronecker products of a steadily growing starter set of
small Hadamard matrices with other known Hadamard matrices (see, e.g., surveys
[8, 9]). Indeed, note that if $H_{1}$ and $H_{2}$ are Hadamard matrices, then
$H_{1}\otimes H_{2}$ is an Hadamard matrix as well.

As an application of our results for Kronecker products of matrices of non-
uniform size we further expand the family of Hadamard matrices that are known
not to be Valiant-rigid.

######  Theorem 1.7.

Let $\mathcal{F}_{0}$ be the family of Paley-Hadamard matrices and Hadamard
matrices of bounded size. Let $\mathcal{F}$ be the family of all matrices that
can be obtained as Kronecker products of some matrices from $\mathcal{F}_{0}$.
Then $\mathcal{F}$ is not absolutely Valiant-rigid.

######  Remark 1.8.

We note that Hadamard matrices are naturally defined over $\mathbb{Q}$, while
the theorem above shows that matrices in $\mathcal{F}$ are not sufficiently
rigid when we make changes from $\mathbb{C}$. It is still open whether Paley-
Hadamard matrices are strictly Valiant-rigid. If one proves that Paley-
Hadamard matrices are not strictly Valiant-rigid, our proof will immediately
yield the stronger version of the theorem above, that $\mathcal{F}$ is not
strictly Valiant-rigid.

######  Remark 1.9.

We note that Theorem 1.7 does not follow from Alman’s original upper bound for
rigidity of Kronecker products (Theorem 1.2).

A more general version of Theorem 1.7 can be stated for Kronecker products of
matrices of bounded size and matrices that are sufficiently not rigid.

######  Theorem 1.10.

Let $0<\varepsilon<1/2$ and $b\geq 2$. Let $\mathcal{F}$ be a family of
matrices over $\mathbb{F}$, such that for every $d\times d$ matrix
$A\in\mathcal{F}$ either $d\leq b$, or

$R_{\mathbb{F}}^{rc}\left(A,d^{1-\gamma}\right)\leq
d^{\varepsilon}\quad\text{for}\quad\gamma=\dfrac{12(\log\log
d)^{2}}{\varepsilon^{3}\log d}.$ (2)

Then, for every sequence of matrices $M_{1},M_{2},\ldots M_{k}\in\mathcal{F}$,
the $n\times n$ matrix $M=\bigotimes\limits_{i\in[k]}M_{i}$ either satisfies
$R_{\mathbb{F}}^{rc}\left(M,{n}/{\log n}\right)\leq n^{6\varepsilon},$ or $n$
is bounded above by a function of $b$ and $\varepsilon$.

######  Corollary 1.11.

Let $\mathcal{F}$ be a family of square matrices over $\mathbb{F}$. If for
every $0<\varepsilon<1/2$ there exists $b\geq 2$ such that $\mathcal{F}$
satisfies the assumptions of Theorem 1.10, then the family of Kronecker
products of matrices from $\mathcal{F}$ is not Valiant-rigid over
$\mathbb{F}$.

We prove Theorems 1.7 and 1.10 in Section 6.

###  1.5 Our approach

In order to prove Theorem 1.2, Alman [1] first uses a beautiful trick to
deduce the claim for Kronecker products of $2\times 2$ matrices. He observes
that it is sufficient to prove the claim for $R=\left(\begin{matrix}1&1\\\
1&0\end{matrix}\right)$. The Kronecker powers of $R$ have low rigidity since
they are very sparse. After that, he applies induction on the size $d$ of the
matrices involved in the Kronecker product. The technically involved induction
argument leads to the factor $2^{-d}$ in $\gamma$.

Our proof is simpler and omits induction. Instead, we observe that an idea,
somewhat similar to Alman’s proof of the base case $d=2$, can be applied for
any $d$.

Our key observation is that any $d\times d$ matrix can be written as a product
of at most $2d$ very sparse matrices and $2d$ permutation matrices.

Specifically, for a vector $x\in\mathbb{F}^{d}$ define a $d\times d$ matrix

$G_{d}(x)=\left(\begin{matrix}I_{d-1}\\\ 0\end{matrix}\
x\right)=\left(\begin{matrix}1&0&0\ldots&0&x_{1}\\\ 0&1&0\ldots&0&x_{2}\\\
\ldots\\\ 0&0&0\ldots&1&x_{d-1}\\\ 0&0&0\ldots&0&x_{d}\end{matrix}\right).$
(3)

We are going to call the matrices of this form the V-matrices for the pattern
of their non-zero entries. Next, it is not hard to verify that any $d\times d$
matrix can be written as

$A=P_{1}\cdot G_{d}(y)^{T}\cdot\left(\begin{matrix}B&0\\\
0&\lambda\end{matrix}\right)\cdot G_{d}(x)\cdot P_{2},$

where $\lambda\in\\{0,1\\}\subseteq\mathbb{F}$,
$B\in\mathbb{F}^{(d-1)\times(d-1)}$ and $P_{1},P_{2}$ are permutation
matrices. By repeating this procedure for $B$ at most $d-2$ times one ends up
with a product of $2d-2$ V-matrices, a diagonal matrix, and permutation
matrices (see Section 3.1).

As was observed in [6], the row-column rigidity of the product can be
controlled by the row-column rigidity of each component.

######  Lemma 1.12.

For arbitrary $d\times d$ matrices $A$ and $B$ over a field $\mathbb{F}$

$R^{rc}_{\mathbb{F}}(A\cdot B,r+s)\leq R^{rc}_{\mathbb{F}}(A,r)\cdot
R^{rc}_{\mathbb{F}}(B,s)\,.$ (4)

Recall that a _monomial matrix_ is a matrix where each row and each column has
at most one non-zero element. A matrix is monomial exactly if it is the
product of a diagonal matrix and a permutation matrix. A Kronecker product of
monomial matrices is itself a monomial matrix. Moreover, if $P$ is a monomial
matrix then $R^{rc}_{\mathbb{F}}(P,0)=1$. Thus, in order to prove Theorem 1.4
one only needs to show strong upper bounds on row-column rigidity for
Kronecker products of V-matrices.

To bound the row-column rigidity of a matrix $M$ that is a Kronecker product
of V-matrices one needs to observe that most of the non-zero entries are
concentrated in just a few columns and rows, and so these entries form a low-
rank matrix.

We discuss our strategy for upper bounds on rigidity of Kronecker products in
Section 3. We prove Theorem 1.4 for the case of matrices of equal size in
Section 4. We discuss rigidity bounds for matrices of unequal sizes in Section
5. Some standard tail bounds for binomial distributions are reviewed in
Section 2. We expand the family of Hadamard matrices known not to be Valiant
rigid in Section 6. The proof of Obs. 3.2 omitted in Section 3 is provided in
Appendix A.

###  1.6 Notation

We use $[n]$ to denote the set $\\{1,2,\ldots,n\\}$. $\mathbb{F}$ denotes a
field. Throughout the paper we use $\vec{d}$ to denote the vector
$(d_{1},d_{2},\ldots d_{k})$, where each $d_{i}\geq 2$. We define
$[\vec{d}]=[d_{1}]\times[d_{2}]\times\ldots\times[d_{k}]$. We say that
$X\in\mathbb{F}^{\vec{d}}$ if $X=(X_{1},X_{2},\ldots,X_{k})$, where
$X_{i}\in\mathbb{F}^{d_{i}}$.

We use standard asymptotic notation. Let $f(n),g(n)$ be non-negative
functions. We say that $f(n)=O(g(n))$ if there exists a constant $C$ such that
$f(n)\leq Cg(n)$ for all sufficiently large $n$. We say that
$f(n)=\Omega(g(n))$ if $g(n)=O(f(n))$. Finally, $f(n)=\Theta(g(n))$ if
$f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$.

## Acknowledgments

The author is grateful to his advisor László Babai for helpful discussions,
his help in improving the organization of the paper, and for pointing out
improvements to the results and simplifications of the proofs. The author is
partially supported by Prof. László Babai’s NSF Grant CCF 1718902. All
statements made in this paper reflect the author’s views and have not been
evaluated or endorsed by the NSF.

##  2 Tail bounds

In this section we review a classical concentration inequality which we apply
to the binomial distribution.

######  Theorem 2.1 (Bernstein inequality).

Let $L\geq 0$ and $\delta>0$. Let $X_{1},\dots,X_{n}$ be independent random
variables satisfying $|X_{i}-\mathbb{E}(X_{i})|\leq L$ for $i\in[n]$. Let
$X=\sum\limits_{i=1}^{n}X_{i}$. Then we have

$\mathbb{P}(X\geq\mathbb{E}(X)+\delta)\leq\exp\left(-\dfrac{\delta^{2}/2}{\sum\limits_{i=1}^{n}\operatorname{Var}(X_{i})+L\delta/3}\right).$

######  Corollary 2.2.

Let $d>1$. Let $X_{i}$ be i. i. d. $\\{0,1\\}$-valued random variables such
that $\mathbb{P}(X_{i}=1)=1-\mathbb{P}(X_{i}=0)=1/d$ for $i\in[n]$. Let
$X=\sum\limits_{i=1}^{n}X_{i}$. Let $\delta<1/d$. Then

$\mathbb{P}\left[X\geq\left(\dfrac{1}{d}+\delta\right)n\right]\leq\exp\left(-\dfrac{\delta^{2}n}{3d}\right)\quad\text{and}\quad\mathbb{P}\left[X\leq\left(\dfrac{1}{d}-\delta\right)n\right]\leq\exp\left(-\dfrac{\delta^{2}n}{3d}\right).$

###### Proof.

Note that $\mathbb{E}(X_{i})=1/d$ and $\operatorname{Var}(X_{i})=(d-1)/d^{2}$.
The first bound follows from Theorem 2.1 with $L=(d-1)/d$. The second bound
follows from Theorem 2.1 with $L=(d-1)/d$ by applying it to
$Y_{i}=\mathbb{E}(X_{i})-X_{i}$. ∎

We also use the following elementary bound.

######  Lemma 2.3.

Let $0\leq k\leq n$. Then
$\sum\limits_{i=0}^{k}\binom{n}{i}\leq\left(\dfrac{\mathrm{e}n}{k}\right)^{k}.$

##  3 A strategy for upper bounds on the rigidity of Kronecker products

###  3.1 Expressing a matrix as a product of V-matrices

Recall that for a vector $x\in\mathbb{F}^{d}$ we define a $d\times d$ V-matrix

$G_{d}(x)=\left(\begin{matrix}I_{d-1}\\\ 0\end{matrix}\
x\right)=\left(\begin{matrix}1&0&0\ldots&0&x_{1}\\\ 0&1&0\ldots&0&x_{2}\\\
\ldots\\\ 0&0&0\ldots&1&x_{d-1}\\\ 0&0&0\ldots&0&x_{d}\end{matrix}\right).$
(5)

Let $\vec{d}=(d_{1},d_{2},\ldots,d_{k})$. For $X=(X_{1},X_{2},\ldots X_{k})$
with $X_{i}\in\mathbb{F}^{d_{i}}$ for $i\in[k]$, define

$G_{\vec{d}\,}(X)=\bigotimes_{i=1}^{k}G_{d_{i}}(X_{i}).$ (6)

In the case when $\vec{d}$ consists of $k$ equal coordinates $d_{i}=d$, we use
notation $G_{d,k}(X):=G_{\vec{d}\,}(X)$.

######  Definition 3.1.

A square matrix $P$ is called a permutation matrix, if every row and every
column of $P$ has precisely one non-zero entry, which is equal to 1.

Recall, that arbitrary permutation of columns (rows) of a matrix can be
represented by right (left, respectively) multiplication by a permutation
matrix.

The multiplication of an $m\times d$ matrix $A$ by $G_{d}(x)$ from the right
corresponds to keeping the first $d-1$ columns of $A$ unchanged and replacing
the last column of $A$ with a linear combination of the columns of $A$ with
the coefficients given by $x$. We make the following observation.

######  Observation 3.2.

For any matrix $A\in\mathbb{F}^{d\times d}$ there exist
$B\in\mathbb{F}^{(d-1)\times(d-1)}$, vectors $x,y\in\mathbb{F}^{d}$,
$\lambda\in\\{0,1\\}\subseteq\mathbb{F}$ and permutation matrices
$P_{1},P_{2}\in\mathbb{F}^{d\times d}$ such that

$A=P_{1}\cdot G_{d}(y)^{T}\cdot\left(\begin{matrix}B&0\\\
0&\lambda\end{matrix}\right)\cdot G_{d}(x)\cdot P_{2}.$ (7)

###### Proof.

See Appendix A. ∎

######  Corollary 3.3.

For any matrix $A\in\mathbb{F}^{d\times d}$ there exist a diagonal matrix $W$,
$2(d-1)$ vectors $X_{i},Y_{i}$ for $i\in[d-1]$, and $2(d-1)$ permutation
matrices $P_{i},Q_{i}$ for $i\in[d-1]$ such that

$A=Q_{1}\cdot G_{d}(Y_{1})^{T}\cdot Q_{2}\cdot\ldots\cdot
G_{d}(Y_{d-1})^{T}\cdot W\cdot G_{d}(X_{d-1})\cdot P_{d-1}\cdot\ldots\cdot
G_{d}(X_{1})\cdot P_{1}.$ (8)

###### Proof.

Let $t\in[d-1]$. Observe that for $x\in\mathbb{F}^{t}$ and the vector
$y\in\mathbb{F}^{d}$, whose first $d-t$ coordinates are 0, and last $t$
coordinates are equal to the corresponding coordinates of $x$,

$\left(\begin{matrix}G_{d-t}(x)&0\\\
0&I_{t}\end{matrix}\right)=P_{1}G_{d}(y)P_{2},$ (9)

where $I_{t}$ is the $t\times t$ identity matrix and $P_{1},P_{2}$ are the
permutation matrices that exchange the first $d-t$ and the last $t$ rows and
columns, respectively.

Then, the claim of the corollary follows from Observation 3.2 by applying it
recursively $d-1$ times to the remaining top-left block $B$, until we are left
with a diagonal matrix. ∎

By combining the above corollary with Lemma 1.12 we obtain the following
inequality.

######  Lemma 3.4.

Let $d\geq 2$, $r\leq d^{k}$ and
$M_{1},M_{2},\ldots,M_{k}\in\mathbb{F}^{d\times d}$. Then

$R_{\mathbb{F}}^{rc}\left(\bigotimes\limits_{i=1}^{k}M_{i},(2d-2)r\right)\leq\left(\max\limits_{X\in\mathbb{F}^{d\times
k}}R_{\mathbb{F}}^{rc}\left(G_{d,k}(X),r\right)\right)^{2d-2}.$ (10)

###### Proof.

By Corollary 3.3, for each $i\in[k]$ there exist $2(d-1)$ vectors
$X_{i}^{(j)},Y_{i}^{(j)}\in\mathbb{F}^{d}$, $2(d-1)$ permutation matrices
$P_{i}^{(j)},Q_{i}^{(j)}$ and a diagonal matrix $W_{i}$ such that

$M_{i}=\prod\limits_{j=1}^{d-1}\left(Q_{i}^{(j)}\cdot
G_{d}(Y^{(j)}_{i})^{T}\right)\cdot
W_{i}\cdot\prod\limits_{j=1}^{d-1}\left(G_{d}(X^{(d-j)}_{i})\cdot
P^{(d-j)}_{i}\right).$

Then, using that $(A_{1}\otimes B_{1})\cdot(A_{2}\otimes
B_{2})=(A_{1}A_{2})\otimes(B_{1}B_{2})$ holds for any matrices, we get

$\bigotimes\limits_{i=1}^{k}M_{i}=\prod\limits_{j=1}^{d-1}\left(\bigotimes\limits_{i=1}^{k}Q_{i}^{(j)}\bigotimes\limits_{i=1}^{k}G_{d}(Y^{(j)}_{i})^{T}\right)\cdot\left(\bigotimes\limits_{i=1}^{k}W_{i}\right)\cdot\prod\limits_{j=1}^{d-1}\left(\bigotimes\limits_{i=1}^{k}G_{d}(X^{(d-j)}_{i})\bigotimes\limits_{i=1}^{k}P_{i}^{(d-j)}\right).$

Let $X^{(j)}\in\mathbb{F}^{d\times k}$ be a matrix whose $i$-th column is
$X_{i}^{(j)}$. Define $Y^{(j)}\in\mathbb{F}^{d\times k}$ similarly. Let

$Q^{(j)}=\bigotimes\limits_{i=1}^{k}Q_{i}^{(j)},\qquad
P^{(j)}=\bigotimes\limits_{i=1}^{k}P_{i}^{(j)},\qquad
W=\bigotimes\limits_{i=1}^{k}W_{i}.$ (11)

Then, $Q^{(j)}$ and $P^{(j)}$ are permutation matrices, and $W$ is a diagonal
matrix, and

$M=\bigotimes\limits_{i=1}^{k}M_{i}=\prod\limits_{j=1}^{d-1}\left(Q^{(j)}\cdot
G_{d,k}(Y^{(j)})^{T}\right)\cdot
W\cdot\prod\limits_{j=1}^{d-1}\left(G_{d,k}(X^{(d-j)})\cdot P^{(d-j)}\right).$
(12)

Thus, by Lemma 1.12,

$\begin{split}R_{\mathbb{F}}^{rc}\left(M,(2d-2)r\right)&\leq\prod\limits_{j=1}^{d-1}R_{\mathbb{F}}^{rc}\left(G_{d,k}(Y^{(j)}),r\right)\cdot\prod\limits_{j=1}^{d-1}R_{\mathbb{F}}^{rc}\left(G_{d,k}(X^{(j)}),r\right)\leq\\\
&\leq\left(\max\limits_{X\in\mathbb{F}^{d\times
k}}R_{\mathbb{F}}^{rc}\left(G_{d,k}(X),r\right)\right)^{2d-2}.\qed\end{split}$
(13)

Furthermore, we note that a similar statement holds for Kronecker products of
matrices of not necessarily equal size.

######  Lemma 3.5.

Let $d_{i}\geq 2$ and $M_{i}\in\mathbb{F}^{d_{i}\times d_{i}}$ for $i\in[k]$.
Assume $d_{k}\geq d_{i}$ for $i\in[k]$. Then

$R_{\mathbb{F}}^{rc}\left(\bigotimes\limits_{i=1}^{k}M_{i},(2d_{k}-2)r\right)\leq\left(\max\limits_{X\in\mathbb{F}^{\vec{d}}}R_{\mathbb{F}}^{rc}\left(G_{\vec{d}\,}(X),r\right)\right)^{2d_{k}-2}.$
(14)

###### Proof.

For $M_{i}$ with $d_{i}<d_{k}$ we multiply the decomposition given by
Corollary 3.3, by $2(d_{k}-d_{i})$ identity matrices from the left and from
the right, so that every $M_{i}$ is decomposed into the product of precisely
$4d_{k}-3$ matrices. After this, the proof is identical to the proof of the
previous lemma. ∎

###  3.2 General approach to upper bounds for the rigidity of
$G_{\vec{d}\,}(X)$

As we see from Lemmas 3.4 and 3.5, in order to prove Theorems 1.3 and 1.4 it
is sufficient to bound the row-column rigidity of Kronecker products of
V-matrices. We describe a general approach to such bounds.

The key observation is that most of the non-zero entries of $G_{\vec{d}\,}(X)$
are concentrated in just a few columns and a few rows. Hence, after deleting
these columns and rows we expect to get a matrix with very sparse rows and
columns.

Recall, that for $\vec{d}=(d_{1},d_{2},\ldots,d_{k})$ we define
$[\vec{d}]=[d_{1}]\times[d_{2}]\times\ldots\times[d_{k}]$. The rows and the
columns of $G_{\vec{d}\,}(X)$ are indexed by tuples in $[\vec{d}]$.

For a $d_{i}\times d_{i}$ V-matrix all rows, except the $d_{i}$-th row, have
up to two non-zero entries, while the $d_{i}$-th row has only one non-zero
entry. For V-matrices, all columns, except the last one, have one non-zero
entry and the last column may have up to $d_{i}$ non-zero entries. Therefore,
the densest rows are indexed by tuples with a small number of $i$-th
coordinates being equal $d_{i}$ and the densest columns are indexed by tuples
with a large number of $i$-th coordinates being equal $d_{i}$, for $i\in[k]$.

Let $w:\mathbb{R}\rightarrow\mathbb{R}$ be a function. Define a score of a
string $x\in[\vec{d}]$ as

$s(x)=\sum\limits_{i=1}^{k}w(d_{i})\mathbf{1}[x_{i}=d_{i}].$ (15)

Consider the uniform distribution on $[\vec{d}]$. Then
$\chi(i)=w(d_{i})\mathbf{1}[x_{i}=d_{i}]$ are independent random variables,
and $s(x)=\sum\limits_{i=1}^{k}\chi(i)$ with

$\mathbb{E}_{x}[s(x)]=\sum\limits_{i=1}^{k}\frac{w(d_{i})}{d_{i}}\quad\text{and}\quad\operatorname{Var}[s(x)]=\sum\limits_{i=1}^{k}w(d_{i})^{2}\left(\dfrac{d_{i}-1}{d_{i}^{2}}\right).$
(16)

For $\delta>0$ we define a pair of sets of strings of high and low scores,
respectively

$\mathcal{C}(\delta)=\\{x\in[\vec{d}]\mid
s(x)\geq\mathbb{E}_{y}[s(y)]+\delta\\}\quad\text{and}\quad\mathcal{R}(\delta)=\\{x\in[\vec{d}]\mid
s(x)\leq\mathbb{E}_{y}[s(y)]-\delta\\}.$ (17)

These sets correspond to indices of the most dense columns and rows,
respectively. Note, that one may use concentration inequalities to bound the
sizes of these sets (see Sec. 2).
The matrix $E$ defined by the union of the rows of $G_{\vec{d}}(X)$ in
$\mathcal{R}(\delta)$ and the columns of $G_{\vec{d}}(X)$ in
$\mathcal{C}(\delta)$ has low rank. Now we want to count the number of non-
zero entries in rows and columns of $G_{\vec{d}}(X)-E$. Define

$T_{c}(\delta,y)=\\{x\in[\vec{d}]\setminus\mathcal{R}(\delta)\mid\forall i:\
y_{i}\in\\{x_{i},d_{i}\\}\\}\quad\text{and}\quad
M_{c}(\delta)=\max\limits_{y\in[\vec{d}]\setminus\mathcal{C}(\delta)}|T_{c}(\delta,y)|;$
(18) $T_{r}(\delta,x)=\\{y\in[\vec{d}]\setminus\mathcal{C}(\delta)\mid\forall
i:\ y_{i}\in\\{x_{i},d_{i}\\}\\}\quad\text{and}\quad
M_{r}(\delta)=\max\limits_{x\in[\vec{d}]\setminus\mathcal{R}(\delta)}|T_{r}(\delta,x)|.$
(19)

With this notation, we have the following inequality.

######  Lemma 3.6.

Let $\delta>0$. Then, for any $X\in\mathbb{F}^{\vec{d}}$,

$R_{\mathbb{F}}^{rc}(G_{\vec{d}\,}(X),|\mathcal{C}(\delta)|+|\mathcal{R}(\delta)|)\leq\max(M_{c}(\delta),M_{r}(\delta)).$

###### Proof.

Let $E$ be the matrix obtained from $G_{\vec{d\,}}(X)$ by changing to 0 every
entry that is not in a column with index in $\mathcal{C}(\delta)$ and is not
in a row with index in $\mathcal{R}(\delta)$. Then

$\operatorname{rank}(E)\leq|\mathcal{C}(\delta)|+|\mathcal{R}(\delta)|.$ (20)

Let $Z=G_{\vec{d}\,}(X)-E$ and $x,y\in[\vec{d}]$. Observe that the entry of
$G_{\vec{d}\,}(X)$ with coordinates $(x,y)$ is non-zero only if for every
$i\in[k]$ either $x_{i}=y_{i}$ or $y_{i}=d_{i}$. Therefore, every row of $Z$
has at most $M_{r}(\delta)$ non-zero entries, and every column of $Z$ has at
most $M_{c}(\delta)$ non-zero entries. ∎

Hence, in order to prove an upper bound on the rigidity of $G_{\vec{d}\,}(X)$,
one just may come up with a good choice of weights $w$ and a threshold
$\delta>0$ which make all the quantities $|\mathcal{C}(\delta)|$,
$|\mathcal{R}(\delta)|$, $M_{c}(\delta)$ and $M_{r}(\delta)$ small.

##  4 Rigidity of Kronecker products of matrices of uniform size

Now, we show how the approach, described above, provides a strong upper bound
on the rigidity of Kronecker products of matrices of uniform size. We follow
the notation introduced earlier.

######  Theorem 4.1.

Given $d\geq 2$ and $0<\varepsilon<1$, there exists
$\gamma=\Theta\left(\dfrac{1}{d\log
d}\cdot\dfrac{\varepsilon^{2}}{\log^{2}(1/\varepsilon)}\right)$ such that for
all $k\geq 1$ and $X\in\mathbb{F}^{d\times k}$ we have
$R_{\mathbb{F}}^{rc}(G_{d,k}(X),n^{1-\gamma})\leq n^{\varepsilon/d}$, where
$n=d^{k}$.

###### Proof.

We use the approach described in the previous section. We take $w(x)=1$, then
$s(x)$ given by Eq. (15) counts the number of coordinates equal to $d$. A
simple computation gives

$\mathbb{E}[s(x)]=k/d\qquad\text{and}\qquad\operatorname{Var}[s(x)]=k(d-1)/d^{2}.$
(21)

Then, by the Bernstein inequality (see Corollary 2.2), for $\delta<1/d$,

$|\mathcal{C}(\delta k)|=d^{k}\cdot\mathbb{P}\left[s(x)\geq k/d+\delta
k\right]\leq\exp\left(\left(\ln d-\frac{\delta^{2}d}{3}\right)k\right).$ (22)

$|\mathcal{R}(\delta k)|=d^{k}\cdot\mathbb{P}\left[s(x)\leq k/d-\delta
k\right]\leq\exp\left(\left(\ln d-\frac{\delta^{2}d}{3}\right)k\right).$ (23)

Therefore, for
$\delta=\Theta\left(\dfrac{\varepsilon}{\log(1/\varepsilon)d}\right)$,

$|\mathcal{R}(\delta k)|+|\mathcal{C}(\delta k)|\leq
d^{(1-\gamma)k}=n^{1-\gamma},\quad\text{for
some}\quad\gamma=\Theta\left(\dfrac{\varepsilon^{2}}{d\log
d\log^{2}(1/\varepsilon)}\right).$ (24)

For a string $x\in[d]^{k}$ define the set $S_{x}=\\{i\mid x_{i}=d\\}$. Recall,
that for every $y\in[d]^{k}\setminus\mathcal{C}(\delta k)$ we have
$|S_{y}|\leq k(1/d+\delta)$ and for every
$x\in[d]^{k}\setminus\mathcal{R}(\delta k)$ we have $|S_{x}|\geq
k(1/d-\delta)$.

For each $y\in[d]^{k}\setminus\mathcal{C}(\delta k)$, a vector $x\in
T_{c}(\delta k,y)$ can be described by picking a subset $U$ of $S_{y}$ of the
size at most $2\delta k$ such that $U=S_{y}\setminus S_{x}$ and by picking
$x_{j}\in[d-1]$ for every $j\in U$. So, by Lemma 2.3,

$|T_{c}(\delta k,y)|\leq\sum\limits_{i\leq 2\delta
k}\binom{|S_{y}|}{i}(d-1)^{i}\leq\left(\dfrac{\mathrm{e}|S_{y}|(d-1)}{2\delta
k}\right)^{2\delta k}\leq\exp(2\delta\ln(3/\delta)k).$ (25)

Similarly, for every row index $x\in[d]^{k}\setminus\mathcal{R}(\delta k)$, a
column $y\in T_{r}(\delta k,x)$ can be described by picking a subset
$U\subseteq[k]\setminus S_{x}$ of size at most $2\delta k$ and by setting
$y_{j}=d$ for $j\in U$ and $y_{j}=x_{j}$ for $j\notin U$. Hence, by Lemma 2.3,

$|T_{r}(\delta k,x)|\leq\sum\limits_{i\leq 2\delta
k}\binom{k-|S_{x}|}{i}\leq\left(\dfrac{\mathrm{e}k}{2\delta k}\right)^{2\delta
k}\leq\exp(2\delta\ln(2/\delta)k).$ (26)

Therefore,

$\max(M_{c}(\delta k),M_{r}(\delta
k))\leq\exp\left(2\delta\ln(3/\delta)k\right)\leq d^{\displaystyle\varepsilon
k/d},\quad\text{for some
}\delta=\Theta\left(\dfrac{\varepsilon}{\log(1/\varepsilon)d}\right).$ (27)

Hence, the conclusion of the theorem follows from Lemma 3.6. ∎

Finally, we can deduce our improved bound for the rigidity of Kronecker
products of matrices of uniform size.

######  Theorem 4.2.

Given $d\geq 2$ and $0<\varepsilon<1$, there exists
$\gamma=\Omega\left(\dfrac{1}{d\log
d}\cdot\dfrac{\varepsilon^{2}}{\log^{2}(1/\varepsilon)}\right)$ such that the
following holds for any $M_{1},M_{2},\ldots,M_{k}\in\mathbb{F}^{d\times d}$
with $k>1/\gamma$. Let $M=\bigotimes\limits_{i=1}^{k}M_{i}$ and $n=d^{k}$.
Then

$R_{\mathbb{F}}^{rc}\left(M,n^{1-\gamma}\right)\leq
n^{\varepsilon},\quad\text{ and so }\quad
R_{\mathbb{F}}\left(M,n^{1-\gamma}\right)\leq n^{1+\varepsilon}.$

###### Proof.

By Theorem 4.1 and Lemma 3.4, for $\varepsilon^{\prime}=\varepsilon/2$ we have

$R_{\mathbb{F}}^{rc}\left(M,2d\cdot d^{(1-\gamma^{\prime})k}\right)\leq
d^{2\varepsilon^{\prime}k}\quad\text{for
some}\quad\gamma^{\prime}=\Theta\left(\dfrac{\varepsilon^{2}}{\log^{2}(1/\varepsilon)d\log
d}\right).$

Pick $\gamma=\gamma^{\prime}/3$ and note that for $k>1/\gamma$ we have
$2d\cdot d^{-2\gamma k}\leq 2d\cdot d^{-2}\leq 1$. ∎

##  5 Rigidity bounds for matrices of unequal sizes

In this section we show how a similar approach may be used to show upper
bounds on the rigidity of Kronecker products of matrices of not necessarily
equal sizes.

######  Theorem 5.1.

Let $0<\varepsilon<1$ and let $w(x)\geq 1$ be a non-decreasing function. There
exists an absolute constant $c>0$ such that the following is true. Let $2\leq
d_{1}\leq d_{2}\leq\ldots\leq d_{k}$ be integers. Let $L>0$ and $K>0$ be such
that

  1. (i)

$\sum\limits_{i=1}^{k}w(d_{i})/d_{i}\leq K\left(\sum\limits_{i=1}^{k}\log
d_{i}/\log d_{k}\right)\cdot(w(d_{1})/d_{k})$, and

  2. (ii)

$\sum\limits_{i=1}^{k}w(d_{i})/d_{i}\geq L\left(\sum\limits_{i=1}^{k}\log
d_{i}/\log d_{k}\right)\cdot(w(d_{k})/d_{k})$.

Let $n=\prod\limits_{i=1}^{k}d_{i}$. Consider arbitrary matrices
$M_{i}\in\mathbb{F}^{d_{i}\times d_{i}}$ and let
$M=\bigotimes\limits_{i=1}^{k}M_{i}$. Then

$R^{rc}_{\mathbb{F}}(M,2d_{k}\cdot n^{1-\gamma})\leq
n^{\varepsilon}\quad\text{where}\quad\gamma=\dfrac{cL\varepsilon^{2}}{d_{k}\log
d_{k}\cdot K^{2}\log^{2}(K/\varepsilon)}.$

###### Proof.

We follow the notation of Section 3.2. Recall that

$m:=\mathbb{E}[s(x)]=\sum\limits_{i=1}^{k}w(d_{i})/d_{i}\quad\text{and}\quad\operatorname{Var}[s(x)]=\sum\limits_{i=1}^{k}w(d_{i})^{2}\left(\dfrac{d_{i}-1}{d_{i}^{2}}\right)\leq
w(d_{k})m.$ (28)

Then, by the Bernstein inequality, for $0<\delta<1$,

$\begin{split}|\mathcal{C}(\delta m)|=n\cdot\mathbb{P}\left[s(x)\geq m+\delta
m\right]\leq
n\cdot\exp\left(-\frac{\delta^{2}m^{2}/2}{\operatorname{Var}[s(x)]+\delta
w(d_{k})m/3}\right)\leq\\\ \leq
n\cdot\exp\left(-\frac{\delta^{2}m}{3w(d_{k})}\right).\end{split}$ (29)

and similarly,

$\begin{split}|\mathcal{R}(\delta m)|=n\cdot\mathbb{P}\left[s(x)\leq m-\delta
m\right]\leq
n\cdot\exp\left(-\frac{\delta^{2}m}{3w(d_{k})}\right).\end{split}$ (30)

Now we want to bound the number of entries in $T_{c}(\delta m,y)$ and
$T_{r}(\delta m,x)$. For $x\in[\vec{d}]$ define $S_{x}=\\{i\in[n]\mid
x_{i}=d_{i}\\}$.

Let $x\in[\vec{d}]\setminus\mathcal{R}(\delta m)$ and $y\in T_{r}(\delta
m,x)$, by definition, $S_{x}\subseteq S_{y}$ and

$\sum\limits_{i\in S_{y}\setminus S_{x}}w(d_{i})\leq 2\delta m.$ (31)

Thus, $t:=|S_{y}\setminus S_{x}|\leq 2\delta m/w(d_{1})=:t_{\max}$. Assumption
(i) implies that

$t_{\max}\leq 2\delta K\ln(n)/(d_{k}\ln d_{k}).$

At the same time, $t_{\max}\geq 2\delta\cdot(kw(d_{1})/d_{k})/w(d_{1})=2\delta
k/d_{k}$. Note that $y\in T_{r}(\delta m,x)$ is uniquely defined by
$S_{y}\setminus S_{x}$. Thus, by Lemma 2.3,

$\begin{gathered}T_{r}(\delta
m,x)\leq\sum\limits_{i=0}^{t_{\max}}\binom{k}{i}\leq\exp\left(t_{\max}\ln\left(\dfrac{\mathrm{e}k}{t_{\max}}\right)\right)\leq\\\
\leq\exp(\ln n\cdot 2\delta K\ln(2d_{k}/\delta)/(d_{k}\ln
d_{k})).\end{gathered}$ (32)

Similarly, for $y\in[\vec{d}]\setminus\mathcal{C}(\delta m)$ we have $x\in
T_{c}(\delta m,y)$ only if $S_{x}\subseteq S_{y}$ and Eq. (31) is satisfied.
Clearly, $|S_{y}|\leq m(1+\delta)/w(d_{1})\leq 2m/w(d_{1})$, and
$t=|S_{y}\setminus S_{x}|$ satisfies $t\leq t_{\max}$. Hence, by Lemma 2.3,

$\begin{split}T_{c}(\delta
m,y)&\leq\sum\limits_{i=0}^{t_{\max}}\binom{|S_{y}|}{t_{\max}}d_{k}^{i}\leq
d_{k}^{t_{\max}}\sum\limits_{i=0}^{t_{\max}}\binom{2m/w(d_{1})}{t_{\max}}\leq\\\
&\leq\exp(t_{\max}\ln(3\delta^{-1})+t_{\max}\ln{d_{k}})\leq\exp(\ln n\cdot
2\delta K\ln(3\delta^{-1})/d_{k}).\end{split}$ (33)

Therefore, there exists
$\delta=\Theta\left((\varepsilon/K)/\log(K/\varepsilon)\right)$ such that

$\max(M_{r}(\delta m),M_{c}(\delta m))\leq n^{\varepsilon/(2d_{k})}\,.$

Moreover, for such choice of $\delta$, by assumption (ii) and Eq. (29)-(30),
we obtain

$|\mathcal{C}(\delta m)|+|\mathcal{R}(\delta m)|\leq
n\exp(-\delta^{2}L\ln(n)/(3d_{k}\ln d_{k}))\leq n^{1-\gamma}.$ (34)

Thus, the claim follows from Lemma 3.6 and Lemma 3.5. ∎

Observe that Theorem 4.2 is a special case of Theorem 5.1 with $K=L=1$. More
generally, we can get the same bound on $\gamma$ for the case when all the
$d_{i}$ are within a constant factor of each other.

######  Corollary 5.2.

Given $0<\varepsilon,c\leq 1$, and $d\geq 2$, there exists
$\gamma=\Omega\left(\dfrac{c\varepsilon^{2}}{d\log(d)\log(1/c)\log^{2}(1/(c\varepsilon))}\right)$
such that the following holds for any sequence of matrices
$M_{1},M_{2},\ldots,M_{k}$ where $M_{i}\in\mathbb{F}^{d_{i}\times d_{i}}$ and
$cd\leq d_{i}\leq d$. Let $M=\bigotimes\limits_{i=1}^{k}M_{i}$ and
$n=\prod\limits_{i=1}^{k}d_{i}$. If $n\geq d^{1/\gamma}$, then
$R^{rc}_{\mathbb{F}}(M,n^{1-\gamma})\leq n^{\varepsilon}$.

###### Proof.

Observe that the assumptions of Theorem 5.1 are satisfied for $w(x)=1$ with
$K=L\leq(1/c)\log(1/c)$. Let $\gamma^{\prime}$ be the constant provided by
Theorem 5.1. We take $\gamma=\gamma^{\prime}/3$ and note that $n^{2\gamma}\geq
2d$. Hence, $R^{rc}_{\mathbb{F}}(M,n^{1-\gamma})\leq n^{\varepsilon}.$ ∎

Next, we eliminate the lower bound constraint on the $d_{i}$, at the cost of a
slightly worse dependence of $\gamma$ on $d$. (Theorem 5.4 below). In
preparation for proving Theorem 5.4, we state its special case where all but
at most one of the $d_{i}$ are restricted to the interval $[\sqrt{d},d]$.

######  Corollary 5.3.

Given $d\geq 2$ and $0<\varepsilon<1$, there exists
$\gamma=\Omega\left(\dfrac{\varepsilon^{2}}{d^{3/2}\log(d)\log^{2}(d/\varepsilon)}\right)$
such that the following holds. Consider any $d_{i}\leq d$ and
$M_{i}\in\mathbb{F}^{d_{i}\times d_{i}}$ for $i\in[k]$. Let
$M=\bigotimes\limits_{i=1}^{k}M_{i}$ and $n=\prod\limits_{i=1}^{k}d_{i}$.
Assume that $d_{i}\geq\sqrt{d}$ for all $i\geq 2$. If $n\geq d^{1/\gamma}$.
Then $R^{rc}_{\mathbb{F}}(M,n^{1-\gamma})\leq n^{\varepsilon}$.

###### Proof.

Define $w(d_{i})=1$. Then, the assumptions of Theorem 5.1 are satisfied for
$K=L\leq 4\sqrt{d}$. Indeed, for $d_{k}\leq d$ and $d_{2}\geq\sqrt{d}$ and
$k>d$, we have the following trivial bounds

$\sum\limits_{i=1}^{k}\log(d_{i})/\log(d_{k})\geq(k-1)/2\quad\text{and}\quad\sum\limits_{i=1}^{k}1/d_{i}\leq(k-1)/\sqrt{d}+1\leq
2(k-1)/\sqrt{d}.$ (35)

Hence, by Theorem 5.1, there exists
$\gamma^{\prime}=\Omega\left(\dfrac{\varepsilon^{2}}{d^{3/2}\log(d)\log^{2}(d/\varepsilon)}\right)$
such that

$R^{rc}_{\mathbb{F}}(M,2dn^{1-\gamma^{\prime}})\leq n^{\varepsilon}.$

Take $\gamma=\gamma^{\prime}/3$. Finally, note that the assumption $n\geq
d^{1/\gamma}$ implies that $n^{2\gamma}\geq 2d$ and $k\geq d$. Hence,
$R^{rc}_{\mathbb{F}}(M,n^{1-\gamma})\leq n^{\varepsilon}$. ∎

Finally, we prove our main result by eliminating $d_{i}\geq\sqrt{d}$
constraint using a bin packing argument.

######  Theorem 5.4.

Given $d\geq 2$ and $0<\varepsilon<1$, there exists
$\gamma=\Omega\left(\dfrac{\varepsilon^{2}}{d^{3/2}\log(d)\log^{2}(d/\varepsilon)}\right)$
such that the following holds for any sequence of matrices
$M_{1},M_{2},\ldots,M_{k}$ where $M_{i}\in\mathbb{F}^{d_{i}\times d_{i}}$ and
$2\leq d_{i}\leq d$. Let $M=\bigotimes\limits_{i=1}^{k}M_{i}$ and
$n=\prod\limits_{i=1}^{k}d_{i}$. If $n\geq d^{1/\gamma}$, then
$R^{rc}_{\mathbb{F}}(M,n^{1-\gamma})\leq n^{\varepsilon}$.

###### Proof.

Let us split the $d_{i}$ into the smallest possible number $k^{\prime}$ of
bins, such that the product of numbers in each bin is at most $d$. Let $a_{j}$
be the product of the numbers in bin $j\in[k^{\prime}]$ and let $A_{j}$ be the
Kronecker product of the corresponding matrices. Then at most one $a_{i}$ is
$\leq\sqrt{d}$. Hence, the theorem follows from Corollary 5.3. ∎

##  6 Application to rigidity upper bounds for Hadamard matrices

As an application of our improved bounds, we show that the family of Kronecker
products of sufficiently not rigid matrices and matrices of bounded size is
not Valiant-rigid.

######  Theorem 6.1.

Let $0<\varepsilon<1/2$ and $b\geq 2$. Let $\mathcal{F}$ be a family of
matrices over $\mathbb{F}$, such that for every $d\times d$ matrix
$A\in\mathcal{F}$ either $d\leq b$, or

$R_{\mathbb{F}}^{rc}\left(A,d^{1-\gamma}\right)\leq
d^{\varepsilon}\quad\text{for}\quad\gamma=\dfrac{12(\log\log
d)^{2}}{\varepsilon^{3}\log d}.$ (36)

Then, for every sequence of matrices $M_{1},M_{2},\ldots M_{k}\in\mathcal{F}$,
the $n\times n$ matrix $M=\bigotimes\limits_{i\in[k]}M_{i}$ either satisfies
$R_{\mathbb{F}}^{rc}\left(M,{n}/{\log n}\right)\leq n^{6\varepsilon},$ or $n$
is bounded above by a function of $b$ and $\varepsilon$.

As an immediate application of Theorem 6.1, we significantly expand the family
of Hadamard matrices known to be not Valiant rigid (Theorem 1.7). We rely on
the rigidity upper bound for Paley-Hadamard matrices established in [6, 3].

######  Theorem 6.2 ([6, 3]).

There exist constants $c_{1}>0$ and $c_{2}>0$ such that for all
$\varepsilon>0$ and an arbitrary $d\times d$ Paley-Hadamard matrix $A$ we have
$R_{\mathbb{C}}^{rc}\left(A,\dfrac{d}{\exp(\varepsilon^{c_{1}}(\log
d)^{c_{2}})}\right)\leq d^{\varepsilon}$.

We restate Theorem 1.7 for convenience.

######  Theorem 6.3.

Let $\mathcal{F}_{0}$ be the family of Paley-Hadamard matrices and Hadamard
matrices of bounded size. Let $\mathcal{F}$ be the family of all matrices that
can be obtained as Kronecker products of some matrices from $\mathcal{F}_{0}$.
Then $\mathcal{F}$ is not absolutely Valiant-rigid.

###### Proof.

Fix $\varepsilon>0$. By Theorem 6.2, the inequality

$\gamma=\dfrac{\varepsilon^{c_{1}}}{(\log d)^{1-c_{2}}}\geq\dfrac{12(\log\log
d)^{2}}{\varepsilon^{3}\log d}\quad\Leftrightarrow\quad\dfrac{(\log
d)^{c_{2}}}{(\log\log d)^{2}}\geq 12\varepsilon^{-3-c_{1}}$

holds for all sufficiently large $d$. Thus, the claim of the theorem follows
from Theorem 6.1. ∎

In order to prove Theorem 6.1, we use the following inequality that relates
the row-column rigidity of the Kronecker product of a pair of matrices to the
row-column rigidities of each of the matrices participating in the product.

######  Lemma 6.4 (Dvir, Liu [6, Lemma 4.9]).

Let $A$ be an $n\times n$ matrix and $B$ be an $m\times m$ matrix. Then

$R_{\mathbb{F}}^{rc}(A\otimes B,r_{a}m+r_{b}n)\leq
R_{\mathbb{F}}^{rc}(A,r_{a})\cdot R_{\mathbb{F}}^{rc}(B,r_{b})$

In the pair of lemmas below we show that the Kronecker product of arbitrary
many sufficiently large and sufficiently not rigid matrices is sufficiently
not rigid itself. These lemmas are essentially the proof content of Lemma 4.10
in [6], which was stated and proved for more specific needs.

######  Lemma 6.5.

Let $2\leq b\leq d_{1}\leq\ldots\leq d_{k}\leq b^{2}$ be integers. Let
$0<\varepsilon<1$ and $\gamma>0$ such that $\gamma\log(b)\geq
2\log(3/\varepsilon)$ and $b\geq 3/\varepsilon$. Assume that for every
$i\in[k]$, $M_{i}$ is a $d_{i}\times d_{i}$ matrix over $\mathbb{F}$ that
satisfies

$R_{\mathbb{F}}^{rc}(M_{i},d_{i}^{1-\gamma})\leq d_{i}^{\varepsilon}.$

Define $M=\bigotimes\limits_{i\in[k]}M_{i}$ and
$n=\prod\limits_{i\in[k]}d_{i}$. Then,

$R_{\mathbb{F}}^{rc}\left(M,n^{1-\varepsilon\gamma/4}\right)\leq
n^{4\varepsilon}.$

###### Proof.

By the assumptions of the lemma, we can write $M_{i}=A_{i}+E_{i}$, where
$A_{i},E_{i}\in\mathbb{F}^{d_{i}\times d_{i}}$,
$\operatorname{rank}(A_{i})\leq d_{i}^{1-\gamma}$, and $E_{i}$ has at most
$d_{i}^{\varepsilon}$ non-zero entries in every row and column. Then

$\begin{split}\bigotimes\limits_{i\in[k]}M_{i}=&\bigotimes\limits_{i\in[k]}(A_{i}+E_{i})=\sum\limits_{S\subseteq[k]}\bigotimes\limits_{i\in
S}A_{i}\bigotimes\limits_{j\in[k]\setminus S}E_{j}\end{split}$ (37)

Now all the summands can be split into two groups: when $|S|\geq\varepsilon k$
and when $|S|<\varepsilon k$. We are going to bound the rank of the sum of the
first group and the number of non-zero entries of the sum of the second group.

$\begin{split}\operatorname{rank}\left(\sum\limits_{S\subseteq[k],|S|\geq\varepsilon
k}\bigotimes\limits_{i\in S}A_{i}\bigotimes\limits_{j\in[k]\setminus
S}E_{j}\right)\leq\sum\limits_{S\subseteq[k],|S|=\varepsilon
k}\operatorname{rank}\left(\bigotimes\limits_{i\in
S}A_{i}\right)\prod\limits_{j\in[k]\setminus S}d_{j}\leq\\\
\leq\binom{k}{\varepsilon k}\max\limits_{S\subseteq[k],|S|=\varepsilon
k}\prod\limits_{i\in S}d_{i}^{1-\gamma}\prod\limits_{j\in[k]\setminus
S}d_{j}\leq\left(\dfrac{3}{\varepsilon}\right)^{\varepsilon k}\cdot n\cdot
b^{-\varepsilon k\gamma}\end{split}$ (38)

Since $b^{\gamma}\geq(3/\varepsilon)^{2}$ and $n\leq b^{2k}$, we have

$\operatorname{rank}\left(\sum\limits_{S\subseteq[k],|S|\geq\varepsilon
k}\bigotimes\limits_{i\in S}A_{i}\bigotimes\limits_{j\in[k]\setminus
S}E_{j}\right)\leq n\cdot b^{-\varepsilon k\gamma/2}\leq
n^{1-\varepsilon\gamma/4}$ (39)

Next, consider the remaining terms

$E=\sum\limits_{S\subseteq[k],|S|<\varepsilon k}\bigotimes\limits_{i\in
S}A_{i}\bigotimes\limits_{j\in[k]\setminus S}E_{j}.$ (40)

Using Lemma 2.3, every column and every row of $E$ has at most

$\left(\sum\limits_{i=0}^{\varepsilon
k}\binom{k}{i}\right)(b^{2})^{\varepsilon
k}\prod_{i\in[k]}d_{i}^{\varepsilon}\leq\left(\dfrac{3}{\varepsilon}\right)^{\varepsilon
k}n^{2\varepsilon}n^{\varepsilon}\leq b^{\varepsilon k}n^{3\varepsilon}\leq
n^{4\varepsilon}$ (41)

non-zero entries. ∎

######  Lemma 6.6.

Let $2\leq b\leq d_{1}\leq\ldots\leq d_{k}$ be integers. Let $0<\varepsilon<1$
and $\gamma_{1},\gamma_{2},\ldots,\gamma_{k}>0$ be such that $b\geq
3/\varepsilon$ and for all $i\in[k]$ we have $\gamma_{i}\cdot\log d_{i}\geq
4\log(3/\varepsilon)$. Assume that for every $i\in[k]$, $M_{i}$ is a
$d_{i}\times d_{i}$ matrix over $\mathbb{F}$, that satisfies
$R_{\mathbb{F}}^{rc}(M_{i},d_{i}^{1-\gamma_{i}})\leq d_{i}^{\varepsilon}$.

Define $M=\bigotimes\limits_{i\in[k]}M_{i}$ and
$n=\prod\limits_{i\in[k]}d_{i}$. Then,

$R_{\mathbb{F}}^{rc}\left(M,n^{1-\psi}\right)\leq
n^{5\varepsilon}\quad\text{for}\quad\psi=\dfrac{\varepsilon^{2}\min_{i}\gamma_{i}}{4\log\log
d_{k}}-\dfrac{\log\log\log d_{k}}{\log n}$

###### Proof.

Let $I_{t}=\\{i\mid d_{i}\in(b^{2^{t}},b^{2^{t+1}}]\\}$ for
$t=1,\ldots,L=\log\log d_{k}$. Let $A_{t}=\bigotimes\limits_{i\in I_{t}}M_{i}$
and $n_{t}=\prod\limits_{i\in I_{t}}d_{i}$. Let $\gamma=\min_{i}\gamma_{i}$.
By Lemma 6.5,

$R_{\mathbb{F}}^{rc}(A_{t},n_{t}^{1-\varepsilon\gamma/4})\leq
n_{t}^{4\varepsilon}$ (42)

Let $S=\\{t\mid n_{t}\geq n^{\varepsilon/L}\\}$ and $N_{S}=\prod\limits_{t\in
S}n_{t}$. Then, by Lemma 6.4,

$R_{\mathbb{F}}^{rc}\left(\bigotimes\limits_{t\in S}A_{t},\
N_{S}\left(\sum\limits_{t\in S}n_{t}^{-\varepsilon\gamma/4}\right)\right)\leq
N_{S}^{4\varepsilon}.$ (43)

Hence,

$R_{\mathbb{F}}^{rc}\left(\bigotimes\limits_{t\in S}A_{t},\ L\cdot
N_{S}n^{-\varepsilon^{2}\gamma/(4L)}\right)\leq N_{S}^{4\varepsilon}$ (44)

Observe that, $n/N_{S}\leq\left(n^{\varepsilon/L}\right)^{L}\leq
n^{\varepsilon}$. Thus,
$R_{\mathbb{F}}^{rc}\left(\bigotimes\limits_{t\in[L]\setminus S}A_{t},\
0\right)\leq n^{\varepsilon}$. Hence, by Lemma 6.4,

$R_{\mathbb{F}}^{rc}\left(M,n^{1-\psi}\right)\leq n^{5\varepsilon},$ (45)

as $n^{-\psi}=\log\log d_{k}\cdot n^{-\varepsilon^{2}\gamma/(4\log\log
d_{k})}=Ln^{-\varepsilon^{2}\gamma/(4L)}$.

∎

Finally, we are ready to prove Theorem 6.1.

###### Proof of Theorem 6.1.

Define $b_{\varepsilon}=3/\varepsilon$ and $b_{*}=\max(b,b_{\varepsilon})$.
Let
$\gamma_{b}=c_{0}\dfrac{1}{b_{*}^{3/2}\log^{3}(b_{*})}\cdot\dfrac{\varepsilon^{2}}{\log^{2}(1/\varepsilon)}$,
where $c_{0}>0$ is the constant given by Theorem 5.4. We may assume $c_{0}<1$.
Define $N_{b}=b_{*}^{24/(\varepsilon\gamma_{b})}$.

Denote the size of $M_{i}$ by $d_{i}$ for $i\in[k]$ and let $S=\\{i\in[k]\mid
d_{i}\leq b_{*}\\}$. Let

$F=\bigotimes\limits_{i\in S}M_{i}\quad\text{and}\quad
H=\bigotimes\limits_{j\in[k]\setminus S}M_{j}.$ (46)

Denote by $N_{F}$ and $N_{H}$ be the orders of $F$ and $H$, respectively. Then
$N_{F}\cdot N_{H}=n$. Let $d_{\max}=\max_{i}d_{i}$. By Lemma 6.6,

$R_{\mathbb{F}}^{rc}\left(M,N_{H}^{1-\psi_{H}}\right)\leq
N_{H}^{5\varepsilon},$ (47)

where

$\psi_{H}\geq\dfrac{\varepsilon^{2}}{4\log\log
d_{\max}}\cdot\dfrac{12(\log\log d_{\max})^{2}}{\varepsilon^{3}\log
d_{\max}}-\dfrac{\log\log\log d_{\max}}{\log N_{H}}\geq\dfrac{2\log\log
n}{\varepsilon\log n}.$ (48)

At the same time, by Theorem 5.4, if $N_{F}\geq N_{b}$, then

$R_{\mathbb{F}}^{rc}\left(F,N_{F}^{1-\gamma_{b}}\right)\leq
N_{F}^{\varepsilon}.$ (49)

Note, since $b_{*}\geq 3/\varepsilon$, we have

$\log\log N_{b}\leq\log(1/\gamma_{b})+2\log(b_{*})\leq
12\log(b_{*})\leq\gamma_{b}\varepsilon\log N_{b}/2.$ (50)

So, in the case $n\geq N_{F}\geq N_{b}$ we have
$\gamma_{b}\geq\dfrac{2\log\log n}{\varepsilon\log n}$.

If $\min(N_{H},N_{F})\geq n^{\varepsilon}$ and $N_{F}\geq N_{b}$, then, by
Lemma 6.4,

$\begin{split}&R^{rc}_{\mathbb{F}}\left(M,n/\log n\right)\leq
R^{rc}_{\mathbb{F}}\left(M,n(n^{-\varepsilon\psi_{H}}+n^{-\varepsilon\gamma_{b}})\right)\leq\\\
&\quad\leq R^{rc}_{\mathbb{F}}\left(H\cdot
F,n(N_{H}^{-\psi_{H}}+N_{F}^{-\gamma_{b}})\right)\leq
R_{\mathbb{F}}^{rc}\left(H,N_{H}^{1-\psi_{H}}\right)\cdot
R_{\mathbb{F}}^{rc}\left(F,N_{F}^{1-\gamma_{b}}\right)\leq
n^{5\varepsilon}.\end{split}$ (51)

If $N_{F}\leq n^{\varepsilon}$, then $N_{H}\geq n^{\varepsilon}$, and by Lemma
6.4,

$R^{rc}_{\mathbb{F}}\left(M,n/\log n\right)\leq
R_{\mathbb{F}}^{rc}\left(M,N_{F}N_{H}^{1-\psi_{H}}\right)\leq
N_{H}^{5\varepsilon}\cdot R_{\mathbb{F}}^{rc}\left(F,0\right)\leq
N_{H}^{5\varepsilon}\cdot N_{F}\leq n^{6\varepsilon}.$ (52)

Similarly, if $N_{H}\leq n^{\varepsilon}$ and $N_{F}\geq N_{b}$, then
$R^{rc}_{\mathbb{F}}\left(M,n/\log n\right)\leq n^{6\varepsilon}$.

Finally, if $N_{b}>N_{F}\geq n^{\varepsilon}$, then the size of $M$ is bounded
by a function of $b$ and $\varepsilon$. ∎

##  Appendix A Proof of Observation 3.2

In this appendix we prove Observation 3.2.

######  Observation A.1.

For any matrix $A\in\mathbb{F}^{d\times d}$ there exists
$B\in\mathbb{F}^{(d-1)\times(d-1)}$, vectors $x,y\in\mathbb{F}^{d}$,
$\lambda\in\\{0,1\\}\subseteq\mathbb{F}$ and permutation matrices
$P_{1},P_{2}\in\mathbb{F}^{d\times d}$ such that

$A=P_{1}\cdot G_{d}(y)^{T}\cdot\left(\begin{matrix}B&0\\\
0&\lambda\end{matrix}\right)\cdot G_{d}(x)\cdot P_{2}.$ (53)

###### Proof.

We consider two cases. First, assume that $A$ has rank $d$. In this case, the
basis vector $e_{d}$ can be written as a linear combination of the columns
$A_{i}$ of $A$. Moreover, by changing the order of columns (by some
permutation matrix, say $Q_{1}$) we may assume that the coefficient in front
of the last column is non-zero. In other words, there exist coefficients
$\mu_{1},\ldots,\mu_{d}$, with $\mu_{d}\neq 0$ such that

$e_{d}=\mu_{1}(AQ_{1})_{1}+\mu_{2}(AQ_{1})_{2}+\ldots+\mu_{d}(AQ_{1})_{d}.$

Define $x_{i}=-\mu_{i}/\mu_{d}$ for $i\in[d-1]$ and
$x_{d}=\dfrac{1}{\mu_{d}}$. Denote by $A^{\prime}$ the matrix consisting of
the first $d-1$ columns of $AQ_{1}$. Then

$AQ_{1}=\left(A^{\prime}\ \begin{matrix}0_{d-1}\\\
1\end{matrix}\right)G_{d}(x).$ (54)

Since $A$ has full rank, the first $d-1$ rows of $A^{\prime}$ span
$\mathbb{F}^{d-1}$. So the last row of $A^{\prime}$ can be written as a linear
combination of the first $d-1$ rows. Hence, for some vector
$y\in\mathbb{F}^{d}$ with $y_{d}=1$,

$(A^{\prime})^{T}=\left(B\ 0_{d-1}\right)G_{d}(y)\quad\Rightarrow\quad
AQ_{1}=G_{d}(y)^{T}\cdot\left(\begin{matrix}B&0\\\ 0&1\end{matrix}\right)\cdot
G_{d}(x).$ (55)

If $A$ has rank less than $d$, there exists a column and a row of $A$ that can
be expressed as a linear combination of all other columns and rows of $A$,
respectively. By changing the order of rows and columns we may assume that
these are $d$-th column and $d$-th row. Then, similarly as above, we see that
$A$ can be written in the form (53) with $\lambda=0$. ∎

## References

  * [1] Josh Alman.  Kronecker products, low-depth circuits, and matrix rigidity.  In Proc. 53rd STOC, pages 772–785. ACM Press, 2021.  (arXiv:2102.11992).
  * [2] Josh Alman and Ryan Williams.  Probabilistic rank and matrix rigidity.  In Proc. 49th STOC, pages 17:1–17:23. ACM Press, 2017.
  * [3] László Babai and Bohdan Kivva.  Matrix rigidity depends on the target field.  In 36th Computational Complexity Conf. (CCC’21), volume 200, pages 41:1–41:26. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2021.
  * [4] Bruno Codenotti, Pavel Pudlák, and Giovanni Resta.  Some structural properties of low-rank matrices related to computational complexity.  Theoretical Computer Science, 235(1):89–107, 2000.
  * [5] Zeev Dvir and Benjamin L. Edelman.  Matrix rigidity and the Croot-Lev-Pach lemma.  Theory of Computing, 15(8):1–7, 2019.
  * [6] Zeev Dvir and Allen Liu.  Fourier and circulant matrices are not rigid.  Theory of Computing, 16(20):1–48, 2020.
  * [7] Oded Goldreich and Avi Wigderson.  On the size of depth-three boolean circuits for computing multilinear functions.  Computational Complexity and Property Testing, pages 41–86, 2020\.
  * [8] A. Hedayat and Walter Dennis Wallis.  Hadamard matrices and their applications.  Annals of Statistics, 6(6):1184–1238, 1978.
  * [9] Kathy J. Horadam.  Hadamard matrices and their applications.  Princeton university press, 2012.
  * [10] Satyanarayana V. Lokam.  Complexity lower bounds using linear algebra.  Foundations and Trends in Theoretical Computer Science, 4(1–2):1–155, 2009.
  * [11] Pavel Pudlák and Petr Savický.  Private communication, cited in [Raz89], 1988.
  * [12] Alexander Razborov.  On Rigid Matrices.  Technical report, Steklov Math. Inst., 1989.  (In Russian, http://people.cs.uchicago.edu/ razborov/files/rigid.pdf).
  * [13] Leslie G. Valiant.  Graph-theoretic arguments in low-level complexity.  In Math. Found. Comp. Sci. (MFCS’77), pages 162–176. Springer, 1977\.