  For a matrix $M$ and a positive integer $r$, the rank $r$ rigidity of $M$ is
the smallest number of entries of $M$ which one must change to make its rank at
most $r$. There are many known applications of rigidity lower bounds to a
variety of areas in complexity theory, but fewer known applications of rigidity
upper bounds. In this paper, we use rigidity upper bounds to prove new upper
bounds in a few different models of computation. Our results include:
  $\bullet$ For any $d> 1$, and over any field $\mathbb{F}$, the $N \times N$
Walsh-Hadamard transform has a depth-$d$ linear circuit of size $O(d \cdot N^{1
+ 0.96/d})$. This circumvents a known lower bound of $\Omega(d \cdot N^{1 +
1/d})$ for circuits with bounded coefficients over $\mathbb{C}$ by Pudl\'ak
(2000), by using coefficients of magnitude polynomial in $N$. Our construction
also generalizes to linear transformations given by a Kronecker power of any
fixed $2 \times 2$ matrix.
  $\bullet$ The $N \times N$ Walsh-Hadamard transform has a linear circuit of
size $\leq (1.81 + o(1)) N \log_2 N$, improving on the bound of $\approx 1.88 N
\log_2 N$ which one obtains from the standard fast Walsh-Hadamard transform.
  $\bullet$ A new rigidity upper bound, showing that the following classes of
matrices are not rigid enough to prove circuit lower bounds using Valiant's
approach:
  $-$ for any field $\mathbb{F}$ and any function $f : \{0,1\}^n \to
\mathbb{F}$, the matrix $V_f \in \mathbb{F}^{2^n \times 2^n}$ given by, for any
$x,y \in \{0,1\}^n$, $V_f[x,y] = f(x \wedge y)$, and
  $-$ for any field $\mathbb{F}$ and any fixed-size matrices $M_1, \ldots, M_n
\in \mathbb{F}^{q \times q}$, the Kronecker product $M_1 \otimes M_2 \otimes
\cdots \otimes M_n$.
  This generalizes recent results on non-rigidity, using a simpler approach
which avoids needing the polynomial method.
