# Restricted invertibility of continuous matrix functions

Adrian Fan  A. Fan, Department of Mathematics, Evans Hall, 3840, University of
California, Berkeley, CA 94720-3840<EMAIL_ADDRESS>,  Jack Montemurro
J. Montemurro, Department of Mathematics, University of Toronto, Toronto, M5S
2E4, Canada<EMAIL_ADDRESS>,  Pavlos Motakis  P. Motakis,
Department of Mathematics and Statistics, York University, 4700 Keele Street,
Toronto, Ontario, M3J 1P3, Canada<EMAIL_ADDRESS>,  Naina Praveen  N.
Praveen, Department of Mathematics, Ashoka University, Rajiv Gandhi Education
City, P.O.Rai, Sonepat, Haryana 131 029, India.
<EMAIL_ADDRESS>,  Alyssa Rusonik  A. Rusonik, Department
of Mathematics, University of Toronto, Toronto, M5S 2E4, Canada.
<EMAIL_ADDRESS>,  Paul Skoufranis  P. Skoufranis, Department
of Mathematics and Statistics, York University, 4700 Keele Street, Toronto,
Ontario, M3J 1P3, Canada<EMAIL_ADDRESS>and  Noam Tobin  N. Tobin,
Department of Mathematics and Statistics, York University, 4700 Keele Street,
Toronto, Ontario, M3J 1P3, Canada<EMAIL_ADDRESS>
###### Abstract.

Motivated by an influential result of Bourgain and Tzafriri, we consider
continuous matrix functions $A:\mathbb{R}\to M_{n\times n}$ and lower
$\ell_{2}$-norm bounds associated with their restriction to certain subspaces.
We prove that for any such $A$ with unit-length columns, there exists a
continuous choice of subspaces $t\mapsto U(t)\subset\mathbb{R}^{n}$ such that
for $v\in U(t)$, $\|A(t)v\|\geq c\|v\|$ where $c$ is some universal constant.
Furthermore, the $U(t)$ are chosen so that their dimension satisfies a lower
bound with optimal asymptotic dependence on $n$ and
$\sup_{t\in\mathbb{R}}\|A(t)\|.$ We provide two methods. The first relies on
an orthogonality argument, while the second is probabilistic and combinatorial
in nature. The latter does not yield the optimal bound for $\dim(U(t))$ but
the $U(t)$ obtained in this way are guaranteed to have a canonical
representation as joined-together spaces spanned by subsets of the unit vector
basis.

This research was conducted during a Fields Undergraduate Summer Research
Program in 2021 and the first, second, fourth, and fifth authors were
supported by this program. The third author was supported by NSERC Grant
RGPIN-2021-03639. The sixth author was supported by NSERC Grant
RGPIN-2017-05711. The seventh author was supported by an Undergraduate Student
Research Award (NSERC)

##  1\. Introduction

This paper concerns itself with continuous matrix functions $A:\mathbb{R}\to
M_{n\times n}$ restricted to linear subspaces and certain lower
$\ell_{2}$-norm bounds satisfied on these subspaces. It is motivated by
specific results in the non-continuous (static) setting. Inspired by problems
in harmonic analysis and the geometry of Banach spaces, a seminal 1987 article
by Bourgain and Tzafriri ([4]) proved the following.

######  Theorem 1.1 ([4]).

There exist universal constants $c_{0},d_{0}>0$ such that for any $A\in
M_{n\times n}(\mathbb{R})$ with $\|Ae_{i}\|=1$ for $1\leq i\leq n$ there
exists $\sigma\subset\\{1,\dotsc,n\\}$ with $|\sigma|\geq d_{0}{n\|A\|^{-2}}$
such that for any set of scalars $\\{a_{j}\\}_{j\in\sigma}$,

$\norm{\sum_{j\in\sigma}a_{j}Ae_{j}}_{2}\geq
c_{0}\left(\sum_{j\in\sigma}|a_{j}|^{2}\right)^{1/2}.$ (1)

Equivalently, for $U_{\sigma}=\langle e_{j}:j\in\sigma\rangle$ and for any
$v\in U_{\sigma}$, $\|Av\|\geq c_{0}\|v\|.$

For the remainder of the paper, let $c_{0}$ and $d_{0}$ be a pair of constants
satisfying the conclusion of Theorem 1.1. We point out that a dimensional
estimate of order ${n\|A\|^{-2}}$ is optimal up to a constant (see Remark
3.7). Intuitively, the Bourgain-Tzafriri result guarantees the existence of a
“large” subspace of $\mathbb{R}^{n}$ on which $A$ does not shrink vectors
“excessively.” The above result implies that $A$ is invertible when restricted
to $U$ which was the original motivation for [4], and hence the term
restricted invertibility. The $U$ from the above theorem is a particularly
simple type of subspace namely one spanned by a subset of standard basis
vectors.

Theorem 1.1 from [4] and subsequent work of Bourgain and Tzafriri ([5], [6])
are strongly related to the famous Kadison-Singer conjecture [9]. This was a
central problem in $C^{*}$-algebras that was restated by Anderson in [1] as a
problem about matrices and it was proved by Casazza and Tremain in [7] that a
certain statement that is related to Theorem 1.1 is equivalent to this
conjecture. Within this context (and others), Theorem 1.1 has been studied,
reproved, and generalized many times including results by Vershynin in [19],
by Spielman and Srivastava in [18] (who showed that for $0<\varepsilon<1$ one
can choose $c_{0}=\varepsilon^{2}$ and $d_{0}=(1-\varepsilon)^{2}$), and by
Naor and Youssef in [16]. Using some of the techniques developed in [18],
Marcus, Spielman, and Srivastava eventually solved the Kadison-Singer
conjecture in [15].

The preservation of lower $\ell_{2}$-norm bounds on subspaces is also related
to a problem from infinite-dimensional Banach space theory, namely the
factorization property of bounded linear operators with large diagonal. This
problem has its origins in Andrew’s paper [2] and it has been further
developed by Laustsen, Lechner, and Müller in [10], by Lechner in [11], by
Lechner, Müller, Schlumprecht, and the third author in [12] and [13], and
others. In the finite-dimensional Euclidean setting, the problem can be stated
as follows: Given $n\in\mathbb{N}$ and $\theta>0$, determine $C>0$ and
$m\in\mathbb{N}$ such that every norm-one $n\times n$ matrix $A=(a_{i,j})$
with $\min|a_{i,i}|\geq\theta$ is a $C/\theta$-factor of the $m\times m$
identity matrix $I_{m}$. This means that there exist matrices $L$ and $R$ of
appropriate dimension such that $\|L\|\|R\|\leq C/\theta$ and $LAR=I_{m}$.
Theorem 1.1 guarantees that one may take $C=c_{0}$ and $m\geq
d_{0}n\theta^{2}$. The continuous version of this problem was investigated by
Dai, Hore, Jiao, Lan, and the third author in [8] where non-optimal estimates
were given.

We turn out attention towards formulating a version of Theorem 1.1 in the
setting of a continuous matrix function $A:\mathbb{R}\to M_{n\times n}$. A
point-wise application of Theorem 1.1 gives that there exists a choice of
subspaces of constant dimension $U(t)\subset\mathbb{R}^{n}$, for all
$t\in\mathbb{R}$ such that $v\in U(t)$, $\|A(t)v\|\geq c\|v\|$. However, the
collection $\\{U(t)\\}_{t\in\mathbb{R}}$ is not a priori known to satisfy any
useful properties. The property of focus in this paper is continuity. We say
that a collection $\\{U(t)\\}_{t\in\mathbb{R}}$ of subspaces varies
continuously or is a continuous collection of subspaces if the matrix function
$P:\mathbb{R}\to M_{n\times n}$, assigning to each $t\in\mathbb{R}$ the
orthogonal projection $P(t)$ onto $U(t)$, is continuous (see Definition 2.3
and Theorem 2.5). We focus on generalizing Theorem 1.1 by addressing the
following main problem:

######  Problem 1.

Given a continuous matrix function $A:\mathbb{R}\to M_{n\times n}(\mathbb{R})$
satisfying pointwise the same hypotheses as those in Theorem 1.1, is it
possible to find subspaces $\\{U(t)\\}_{t\in\mathbb{R}}$ that vary
continuously satisfying a similar lower $\ell_{2}$-norm bound? If so, are
there obtainable bounds on $\dim(U(t))$?

We use techniques from linear algebra, analysis, and combinatorics, and employ
a probabilistic construction to obtain the desired collection
$\\{U(t)\\}_{t\in\mathbb{R}}$ with a lower bound of the dimension which is
indeed optimal up to a constant. Closely related to Problem 1, is the
following problem considered in [8].

######  Problem 2.

Given $n\in\mathbb{N}$ and $\theta>0$, determine $C>0$ and $m\in\mathbb{N}$
such that for every continuous matrix function $A=(a_{i,j}):\mathbb{R}\to
M_{n\times n}$ with $\|A(t)\|\leq 1$ and $\min_{i}|a_{i,i}(t)|\geq\theta$ for
every $t\in\mathbb{R}$ there exists continuous matrix functions
$L:\mathbb{R}\to M_{m\times n}$, $R:\mathbb{R}\to M_{n\times m}$ so that
$LAR=I_{m}$ and $\sup_{t}\|L(t)\|\|R(t)\|\leq C/\theta$.

In Theorem 3.9 we will show that a solution to the first problem also offers
one for the second. We will provide two approaches to solving these problems.
The first one, presented in Section 3, allows us to recover the (up to
universal constants) optimal bound:

######  Theorem 1.2.

Let $A:\mathbb{R}\rightarrow M_{n\times n}$ be a continuous matrix function,
satisfying the property that for all $t\in\mathbb{R}$, $\|A(t)e_{i}\|=1$ for
every $1\leq i\leq n$. Let $\Lambda=\sup_{t}\|A(t)\|$ and $\gamma\in(0,1)$.
Then, there exists a continuous family of $m$-dimensional subspaces
$\\{U(t)\\}_{t\in\mathbb{R}}$ where $m\geq(d_{0}n/7\Lambda^{2})$ such that for
every $t\in\mathbb{R},$ and every $v\in U(t)$, $\|Av\|\geq\gamma c_{0}\|v\|$.

Note that the Hilbert-Schmidt norm of each $A(t)$ is $\sqrt{n}$ and therefore
$\Lambda\leq\sqrt{n}$.

The second approach yields a more rigid collection of subspaces
$\\{U(t)\\}_{t\in\mathbb{R}}$. As a trade-off, their dimensional estimate is
weakened.

######  Definition 1.3.

An $m$-dimensional subspace $U$ of $\mathbb{R}^{n}$ is called a quadratic
convex combination of disjoint basis vectors if there exist disjoint subsets
$\sigma_{1}=\\{i_{1}<\cdots<i_{m}\\}$, $\sigma_{2}=\\{j_{1}<\cdots<j_{m}\\}$
of $\\{1,\ldots,n\\}$ and $\lambda\in[0,1]$ such that $U$ is spanned by the
orthonormal sequence
$u_{k}=\lambda^{1/2}e_{i_{k}}+(1-\lambda)^{1/2}e_{j_{k}}$, $k=1,\ldots,m$. If
we wish to be more specific, we will say that $U$ is a $\lambda$-quadratic
convex combination of $U_{\sigma_{1}}$ and $U_{\sigma_{2}}$.

######  Theorem 1.4.

There exists universal constants $c,d>0$ such that for all continuous matrix
functions $A:\mathbb{R}\rightarrow M_{n\times n}$ with the property that
$\|A(t)e_{i}\|=1$ for all $t\in\mathbb{R}$ and $1\leq i\leq n$, there exists a
continuous family of $m$-dimensional subspaces $\\{U(t)\\}_{t\in\mathbb{R}}$
of $\mathbb{R}^{n}$ with $m\geq dn/\Lambda^{4}$ where
$\Lambda=\sup_{t}\|A(t)\|$ such that $\|Av\|\geq c\|v\|$ for every
$t\in\mathbb{R}$ and every $v\in U(t)$. Furthermore, each subspace $U(t)$ is a
quadratic convex combination of disjoint basis vectors.

The impact of this improved choice of subspaces on the dimensional estimate is
on the exponent of $\Lambda$. To motivate the second method, which is
presented in Section 4, we begin with a consideration of the issues that arise
with a pointwise application of the Bourgain-Tzafriri result. Were we to try
to merely apply Theorem 1.1 pointwise given $A:\mathbb{R}\to M_{n\times n}$,
we would be able to generate a suitable collection
$\\{\sigma_{t}\\}_{t\in\mathbb{R}}$ of subsets of $\\{1,\dotsc,n\\}$. Of
course, this is not enough: $U_{\sigma_{t}}$ cannot be chosen uniformly with
respect to $t$, so there is no reason to suppose that for two arbitrarily
close points $t_{1},t_{2}$ the corresponding
$U_{\sigma_{t_{1}}},U_{\sigma_{t_{2}}}$ would serendipitously satisfy the
required continuous transition property. To see this, it is enough to notice
that satisfactory sets $\sigma_{t}$ at a point need not be unique.

Instead we find a suitable countable sequence of points
$(t_{i})_{i\in\mathbb{Z}}$, apply a static result à la Bourgain-Tzafriri at
each such $t_{i}$ to first find a subset $\sigma_{i}$ of $\\{1,\ldots,n\\}$
and then conclude by means of a “stitching” argument. By this, we mean that we
continuously pass between $U_{\sigma_{i}}$ and $U_{\sigma_{{i+1}}}$ on
$[t_{i},t_{i+1}]$ via quadratic convex combinations $U(t)$ of $U_{\sigma_{i}}$
and $U_{\sigma_{i+1}}$ while simultaneously preserving the desired lower
$\ell_{2}$-norm bound of $A(t)$ on $U(t)$. Importantly, it is necessary that
on the whole interval $[t_{i},t_{i+1}]$, $A(t)$ already satisfies this bound
on both $U_{\sigma_{i}}$ and $U_{\sigma_{{i+1}}}$. But this alone is not
sufficient. Without further stipulations, $U(t)$ could fail to preserve the
desired properties at some point (e.g., $U(t)$ and $\mathrm{ker}A(t)$ may
momentarily intersect for some $t\in[t_{i},t_{i+1}]$, which would immediately
violate the lower $\ell_{2}$-norm bound). From this, it becomes clear that
there must be some relationship between $\sigma_{i}$ and $\sigma_{{i+1}}$ that
would preserve the minimal stretch property during the “stitching” procedure.
It is sufficient to require that for all $t\in[t_{i},t_{i+1}]$, $A(t)$
satisfies the desired bound on the whole subspace
$U_{\sigma_{i}\cup\sigma_{i+1}}$.

To achieve this, we rely on an iterative application of a modified Bourgain-
Tzafriri argument. The modification introduces a dependence of each subsequent
column set on the one that precedes it; the iteration consists of passing to
subsets of the generated column sets, and allows for the modification to be
bilateral. Then, each column set depends on both the one that precedes it and
on the one that will follow. This is where the loss of optimality occurs.

Because the iterative application of the modified Bourgain-Tzafriri result
incurs the loss of optimal dimension, in the proof of Theorem 1.2, we base the
argument on a different way of refining the column sets. We introduce a
dependence that allows for a different “stitching” argument to be made which
takes place at the level of the spaces $A(t)(U_{\sigma_{i}})$ and
$A(t)(U_{\sigma_{i+1}})$. This is based on nice properties of orthogonal
subspaces, to which one may conveniently pass with a judicious construction.
As the Bourgain-Tzafriri result is applied once and subsequent modifications
come only at the cost of worse universal constants, this optimally solves
Problem 1 (and, by extension, Problem 2).

##  2\. Preliminaries

In this section we recall various norms, recall the concept of continuous
matrix functions, and discuss continuously varying subspaces of
$\mathbb{R}^{n}$. We denote the standard basis for $\mathbb{R}^{n}$ by
$\\{e_{1},\dotsc,e_{n}\\}$ and assume the norm on $\mathbb{R}^{n}$ to be the
2-norm: $\norm{x}=(\sum_{i=1}^{n}x_{i}^{2})^{\frac{1}{2}}$ for all
$x\in\mathbb{R}^{n}$. We begin by defining useful quantities on $M_{m\times
n}$, the space of all real valued $m\times n$ matrices.

######  Definition 2.1.

Let $A=(a_{i,j})\in M_{m\times n}$.

  1. (i)

The operator norm of $A$ is defined as

$\|A\|=\sup\Big{\\{}\|Ax\|:x\in\mathbb{R}^{n},\|x\|=1\Big{\\}}.$

If $U$ is a subspace of $\mathbb{R}^{n}$, let $\|A|_{U}\|=\sup\\{\|Ax\|:x\in
U,\|x\|=1\\}$.

  2. (ii)

The minimal stretch of $A$ is defined as

$m_{A}=\inf\Big{\\{}\|Ax\|:x\in\mathbb{R}^{n},\|x\|=1\Big{\\}}.$

If $U$ is a subspace of $\mathbb{R}^{n}$, let $m_{A|_{U}}=\inf\\{\|Ax\|:x\in
U,\|x\|=1\\}$.

  3. (iii)

The Hilbert-Schmidt norm of $A$ is defined as

$\|A\|_{\text{HS}}=\Big{(}\sum_{i=1}^{n}\|Ae_{i}\|^{2}\Big{)}^{1/2}=\Big{(}\sum_{i=1}^{m}\sum_{j=1}^{n}a_{ij}^{2}\Big{)}^{1/2}.$

We point out that these quantities can be equivalently defined as follows. Let
$(\sigma_{i})_{i=1}^{m\wedge n}$ denote sequence of the singular values of
$A$. Then $\|A\|=\max\sigma_{i}$ whereas $m_{A}=\min\sigma_{i}$ and
$\|A\|_{\text{HS}}=(\mathrm{tr}(A^{T}A))^{1/2}=(\sum_{i=1}^{m\wedge
n}\sigma_{i}^{2})^{1/2}$ (see, e.g., [14, Theorem 7.4.3]). These yield the
following estimates.

$\|A\|\leq\|A\|_{\mathrm{HS}}\leq\big{(}\mathrm{rank}(A)\big{)}^{1/2}\|A\|.$

######  Definition 2.2.

Let $I$ be an interval of $\mathbb{R}$. A matrix function $A=(a_{i,j}):I\to
M_{m\times n}$ is said to be continuous if its entries $a_{i,j}:I\to
M_{m\times n}$ are continuous.

It is well known that $A$ is continuous if and only if it is continuous as a
function from the metric space $(I,|\cdot|)$ to the normed linear space
$(M_{m\times n},\|\cdot\|)$ (see, e.g., [8, Lemma 3.1]).

######  Definition 2.3.

Let $I$ be an interval of $\mathbb{R}$ and let $\\{U(t)\\}_{t\in I}$ be a
family of subspaces of $\mathbb{R}^{n}$.

  1. (i)

The family $\\{U(t)\\}_{t\in I}$ is said to be a continuous choice of
subspaces of $\mathbb{R}^{n}$ if the function $P:I\to M_{n\times n}$ where
$P(t)$ is the orthogonal projection onto $U(t)$ for all $t\in I$ is
continuous.

  2. (ii)

The family $\\{U(t)\\}_{t\in I}$ is said to admit a continuous choice of basis
if, for some $m\in\mathbb{N}$, there exist continuous
$\gamma_{1},\ldots,\gamma_{m}:I\to\mathbb{R}^{n}$ so that for each $t\in I$,
$\gamma_{1}(t),\ldots,\gamma_{m}(t)$ form a basis of $U(t)$.

######  Lemma 2.4.

If $I$ is an interval of $\mathbb{R}$ and a family $\\{U(t)\\}_{t\in I}$ of
subspaces of $\mathbb{R}^{n}$ admits a continuous choice of basis
$\gamma_{1},\ldots,\gamma_{m}:I\to\mathbb{R}^{n}$ then it also admits a
continuous choice of orthonormal basis
$u_{1},\ldots,u_{m}:I\to\mathbb{R}^{n}$. Therefore $\\{U(t)\\}_{t\in I}$ is a
continuous choice of subspaces of $\mathbb{R}^{n}$.

###### Proof.

Define $u_{1}(t)=\|\gamma_{1}(t)\|^{-1}\gamma_{1}(t)$. By induction on
$k=2,\ldots,m$ let
$\tilde{u}_{k}(t)=\gamma_{k}(t)-\sum_{i=1}^{k-1}\langle\gamma_{k}(t),u_{i}(t)\rangle
u_{i}(t)$ and $u_{k}(t)=\|\tilde{u}_{k}(t)\|^{-1}\tilde{u}_{k}(t)$. This
yields a continuous choice of orthonormal basis
$u_{1},\ldots,u_{m}:I\to\mathbb{R}^{n}$. Finally, note that for each $t\in I$,
putting $W(t)=[u_{1}(t)\cdots u_{m}(t)]$ we have that $P(t)=W(t)W^{T}(t)$ the
orthogonal projection onto $U(t)$ and $P:I\to M_{n\times n}$ is continuous. ∎

Our next goal is to show that (i) and (ii) of Definition 2.3 are in fact
equivalent. Note it is essential that the domain $I$ is a subset of
$\mathbb{R}$. Indeed if we replace $I$ with the unit circle $S^{1}$ then this
would no longer be true since we are working with subspaces of
$\mathbb{R}^{n}$. For example, for all $x=(\cos(\theta),\sin(\theta))$ in
$S^{1}$ let

$U(\cos(\theta),\sin(\theta))=\langle(\cos(\theta/2),\sin(\theta/2))\rangle\subset\mathbb{R}^{2}.$

Then $\\{U(x)\\}_{x\in S^{1}}$ is a continuous choice of subspaces of
$\mathbb{R}^{2}$ for which a continuous choice of basis is impossible.

######  Theorem 2.5.

Let $I$ be an interval of $\mathbb{R}$. A family of subspaces
$\\{U(t)\\}_{t\in I}$ of $\mathbb{R}^{n}$ is continuous if and only if it
admits a continuous choice of orthonormal basis.

The proof of the above requires some preparatory steps. For each of the
following lemmata, let $I$ be an interval of $\mathbb{R}$ and $P:I\to
M_{n\times n}$ be a continuous matrix function such that $P(t)$ is an
orthogonal projection for all $t\in\mathbb{R}$.

######  Lemma 2.6.

The rank of $P(t)$ is constant for all $t\in I$.

###### Proof.

Since the rank of an orthogonal projection is equal to the trace of the
orthogonal projection, and since $\tr(P(t)):I\to\mathbb{R}$ is continuous when
$P$ is continuous, the result follows. ∎

######  Lemma 2.7.

For all $t_{0}\in I$ there is an $\varepsilon>0$ and continuous functions
$\gamma_{1},\dotsc,\gamma_{k}:(t_{0}-\varepsilon,t_{0}+\varepsilon)\cap
I\to\mathbb{R}^{n}$ such that for all
$t\in(t_{0}-\varepsilon,t_{0}+\varepsilon)\cap
I,\,\imaginary(P(t))=\langle\gamma_{1}(t),\dotsc,\gamma_{k}(t)\rangle$.

###### Proof.

Let $t_{0}\in I$. By assumption, $\rank(P(t_{0}))=k$, so there exist $k$
linearly independent columns of $P(t_{0})$,
$\\{Pe_{i_{j}}(t_{0})\\}_{j=1}^{k}$, which span $\imaginary(P(t_{0}))$. That
is,

$\imaginary(P(t_{0}))=\langle Pe_{i_{1}}(t_{0})\dotsc
Pe_{i_{k}}(t_{0})\rangle.$

Since $\rank(Pe_{i_{1}}(t_{0})\dotsc Pe_{i_{k}}(t_{0}))=k$, we can find $k$
suitable rows of the matrix $[Pe_{i_{1}}(t)\dotsc Pe_{i_{k}}(t)]$ to obtain
$B:\mathbb{R}\to M_{k\times k}$ such that $B(t_{0})$ is invertible (by virtue
of satisfying $\det B(t_{0})\neq 0$). The continuity of the determinant
function guarantees the existence of an $\varepsilon>0$ such that for any
$t\in(t_{0}-\varepsilon,t_{0}+\varepsilon)\cap I,\,\det B(t)\neq 0$. Thus, for
any $t\in(t_{0}-\varepsilon,t_{0}+\varepsilon)\cap I,\rank(Pe_{i_{1}}(t)\dotsc
Pe_{i_{k}}(t))=k$ and so

$\imaginary(P(t))=\langle Pe_{i_{1}}(t)\dotsc Pe_{i_{k}}(t)\rangle\text{ as
}\rank(P(t))=k$

(where $B(t)$ is the minor of $P(t)$ defined using the same components as
$B(t_{0})$). ∎

######  Lemma 2.8.

Let $a<c<b<d$ and $P:(a,d)\to M_{n\times n}$ be continuous and let
$k=\rank(P(t))$ for all $t\in\mathbb{R}$. Assume that $\imaginary(P(t))$
admits a continuous choice of basis
$\gamma_{1},\dotsc,\gamma_{k}:(a,b)\to\mathbb{R}^{n}$ on $(a,b)$ and another
continuous choice of basis on $(c,d)$. Then, $\gamma_{1},\dotsc,\gamma_{k}$
may be extended to a continuous choice of basis on $(a,d)$.

###### Proof.

By Lemma 2.7, it is sufficient to show that we can “stitch together”
continuous bases with intersecting domains. Let

$\displaystyle\alpha_{1},\dotsc,\alpha_{k}$
$\displaystyle:(a,b)\to\mathbb{R}^{n}\text{ s.t. }\forall t\in(a,b),\text{
Im}(P(t))=\langle\alpha_{1}(t),\dotsc,\alpha_{k}(t)\rangle$
$\displaystyle\beta_{1},\dotsc,\beta_{k}$
$\displaystyle:(c,d)\to\mathbb{R}^{n}\text{ s.t. }\forall t\in(c,d),\text{
Im}(P(t))=\langle\beta_{1}(t),\dotsc,\beta_{k}(t)\rangle$

for some $a<c<b<d$. Let $t_{0}\in(c,b)$. Then we can write the
$\alpha_{i}(t_{0})$ as linear combinations of
$\beta_{1}(t_{0}),\dotsc,\beta_{k}(t_{0})$ since
$\langle\alpha_{1}(t_{0}),\dotsc,\alpha_{k}(t_{0})\rangle=\langle\beta_{1}(t_{0}),\dotsc,\beta_{k}(t_{0})\rangle$.
In other words, for each $i\in\\{1,\dotsc,k\\}$, there are
$(\lambda_{ij})_{j=1}^{k}\text{ s.t.
}\alpha_{i}(t_{0})=\displaystyle\sum_{j=1}^{k}\lambda_{ij}\beta_{j}(t_{0})$.

Since the $\left(\alpha_{i}(t_{0})\right)_{i=1}^{k}$ and
$\left(\beta_{i}(t_{0})\right)_{i=1}^{k}$ are bases of Im$(P(t_{0}))$, the
$\lambda_{ij}$ uniquely determine an invertible matrix $F=(\lambda_{ij})\in
M_{k\times k}(\mathbb{R})$, for which

$\begin{bmatrix}\alpha_{1}(t_{0})^{T}\\\ \vdots\\\
\alpha_{k}(t_{0})^{T}\end{bmatrix}=F\begin{bmatrix}\beta(t_{0})^{T}\\\
\vdots\\\ \beta_{k}(t_{0})^{T}\end{bmatrix}.$

Define $(\gamma_{1},\dotsc,\gamma_{k}):(a,d)\to M_{n\times k}(\mathbb{R})$ by:

$\left(\gamma_{1}(t),\dotsc,\gamma_{k}(t)\right)=\begin{cases}\left(\alpha_{1}(t),\dotsc,\alpha_{k}(t)\right)&t\leq
t_{0}\\\ \left(\beta_{1}(t),\dotsc,\beta_{k}(t)\right)F^{T}&t>t_{0}.\\\
\end{cases}$

Then for every $t\in(a,d),$
Im$(P(t))=\langle\gamma_{1}(t),\dotsc,\gamma_{k}(t)\rangle$ (since $\det F\neq
0$), and the $\gamma_{i}$ are continuous. ∎

###### Proof of Theorem 2.5.

Let $P:I\to M_{n\times n}$ be continuous such that for all $t\in I$, $P(t)$ is
an orthogonal projection. We want to construct $u_{i}:I\to\mathbb{R}^{n}$
continuous such that $u_{1}(t),\dotsc,u_{k}(t)$ form a basis of Im$(P(t))$ for
every $t\in I$. For simplicity, let us assume that $I=\mathbb{R}$ as the other
cases are similar.

We work first with $[-1,1]$. As it is compact, by Lemma 2.7, $[-1,1]$ admits a
finite cover by open intervals $(a_{j},b_{j})$ so that there exist continuous
$\gamma_{ji}:(a_{j},b_{j})\to\mathbb{R}^{n}$ such that for
$t\in(a_{j},b_{j}),(\gamma_{j1}(t),\dotsc,\gamma_{jk}(t))$ is a basis of
Im$(P(t))$.

Without loss of generality, we assume $a_{j+1}<b_{j}$ to obtain a cover by
“interlocking” intervals (with non-empty sequential intersections). A finite,
step-by-step application of Lemma 2.8 allows for the construction of
continuous $\gamma_{i}:[-1,1]\to\mathbb{R}^{n}$ such that
$(\gamma_{1}(t),\dotsc,\gamma_{k}(t))$ is a basis of Im$(P(t))$ for each
$t\in[-1,1]$.

Suppose $\gamma_{i}(t)$ is defined for all $t\in[-m,m]$. We will extend
$\gamma_{i}$ to $[-(m+1),m+1]$. We similarly use Lemma 2.7 and the compactness
of $[-(m+1),m+1]$ to obtain a suitable finite open cover, whereupon we apply
Lemma 2.8 as above to define $\gamma_{i}(t)$ for $t\in[-(m+1),m+1]$ without
modifying $\gamma_{i}$ on $[-m,m]$. Notice that $\gamma_{i}$ is well-defined
as it is independent of the choice of $m$ (subsequent extensions of
$\gamma_{i}$ do not alter the behaviour of the function on a domain on which
it was previously defined). ∎

##  3\. Method I: Optimal Dimensional Bound

In this section we prove Theorem 1.2 and then show how it can be used to
provide a solution to Problem 2.

###  3.1. The proof of Theorem 1.2

We start by proving some statements that will allow us to find appropriate
subspaces of $\mathbb{R}^{n}$ and then stitch them together.

######  Proposition 3.1.

If $X$ and $Y$ are linear subspaces of $\mathbb{R}^{n}$ and
$\dim{X}=\dim{Y}=m$, then there exist linear subspaces
$\stackon[.5pt]{X}{\scriptscriptstyle\sim}\subset X,\tilde{Y}\subset Y$ such
that
$\dim{\tilde{X}},\dim{\stackon[.5pt]{Y}{\scriptscriptstyle\sim}}\geq\lfloor\frac{m}{2}\rfloor$
and $\tilde{X}\perp\tilde{Y}$.

In order to show this theorem, we first prove a lemma that allows us to
construct a convenient basis for our subspaces.

######  Lemma 3.2.

Given two subspaces $X$ and $Y$ of $\mathbb{R}^{n}$ of dimension $m$, there
exist orthonormal bases $\\{x_{1},x_{2},\ldots,x_{m}\\}$ and
$\\{y_{1},y_{2},\ldots,y_{m}\\}$ of $X$ and $Y$ respectively, such that
$\langle x_{i},y_{j}\rangle=0$ for any $i\neq j$.

###### Proof.

Define $P:\mathbb{R}^{n}\rightarrow Y$ to be the projection map onto $Y$. Let
$\stackon[.5pt]{P}{\scriptscriptstyle\sim}=P|_{X}$, and so,
$\stackon[.5pt]{P}{\scriptscriptstyle\sim}:X\rightarrow Y$. Define
$A=\stackon[.5pt]{P}{\scriptscriptstyle\sim}^{*}\stackon[.5pt]{P}{\scriptscriptstyle\sim}:X\rightarrow
X$. Then $A$ is self-adjoint, so the Spectral Theorem implies there is an
orthonormal basis $\\{x_{1},\ldots,x_{m}\\}$ of $X$ such that each $x_{i}$ is
an eigenvector of $A$. Now, let
$\stackon[.5pt]{y}{\scriptscriptstyle\sim}_{i}=\stackon[.5pt]{P}{\scriptscriptstyle\sim}x_{i}$
and $\sigma=\\{1\leq i\leq m:\tilde{y}_{i}\neq 0\\}$. For $i\in\sigma$ let
$y_{i}=\|\stackon[.5pt]{y}{\scriptscriptstyle\sim}_{i}\|^{-1}\stackon[.5pt]{y}{\scriptscriptstyle\sim}_{i}$.
Note for $i,j\in\sigma$ with $i\neq j$ that

$\langle\tilde{y}_{i},\tilde{y}_{j}\rangle=\langle\stackon[.5pt]{P}{\scriptscriptstyle\sim}x_{i},\stackon[.5pt]{P}{\scriptscriptstyle\sim}x_{j}\rangle=\langle
x_{i},\stackon[.5pt]{P}{\scriptscriptstyle\sim}^{*}\stackon[.5pt]{P}{\scriptscriptstyle\sim}x_{j}\rangle=\langle
x_{i},Ax_{j}\rangle=\lambda_{j}\langle x_{i},x_{j}\rangle=0$

so the sequence $(y_{i})_{i\in\sigma}$ is orthonormal. Extend
$(y_{i})_{i\in\sigma}$ to an orthonormal basis $(y_{i})_{i=1}^{m}$ of $Y$. It
now remains to check that $\langle x_{i},y_{j}\rangle=0$ for $i\neq j$. If
$\stackon[.5pt]{P}{\scriptscriptstyle\sim}x_{i}=0$, then $x_{i}$ is orthogonal
to every vector in $Y$. Otherwise, notice that $u_{i}\in\mathbb{R}^{n}=Y\oplus
Y^{\perp}$, and so we can express it as $x_{i}=\tilde{y}_{i}+y^{\prime}_{i}$
where $y^{\prime}_{i}=x_{i}-\tilde{y}_{i}\in Y^{\perp}$. Then, it follows:

$\langle
x_{i},y_{j}\rangle=\langle\tilde{y}_{i}+y^{\prime}_{i},y_{j}\rangle=\langle\tilde{y}_{i},y_{j}\rangle+\langle
y^{\prime}_{i},y_{j}\rangle=0.\qed$

We can now proceed with the proof of Proposition 3.1

###### Proof.

Lemma 3.2 yields orthonormal bases $\\{x_{1},\ldots,x_{m}\\}$ and
$\\{y_{1},\ldots,y_{m}\\}$ of $X$ and $Y$ respectively, such that $\langle
x_{i},y_{j}\rangle=0$ when $i\neq j$. When $m$ is odd, define
$\stackon[.5pt]{X}{\scriptscriptstyle\sim}=\langle\\{x_{1},\ldots,x_{\lfloor\frac{m}{2}\rfloor}\\}\rangle$
and
$\stackon[.5pt]{Y}{\scriptscriptstyle\sim}=\langle\\{y_{\lceil\frac{m}{2}\rceil},\ldots,y_{m-1},y_{m}\\}\rangle$.
Then $\langle x_{i},y_{j}\rangle=0$ for all $1\leq
i\leq\lfloor\frac{m}{2}\rfloor,\lceil\frac{m}{2}\rceil\leq j\leq m$.

If $m$ is even, define
$\stackon[.5pt]{X}{\scriptscriptstyle\sim}=\langle\\{x_{1},\ldots,x_{\frac{m}{2}}\\}\rangle$
and
$\stackon[.5pt]{Y}{\scriptscriptstyle\sim}=\langle\\{y_{\frac{m}{2}+1},\ldots,y_{m-1},y_{m}\\}\rangle$.
Then $\langle x_{i},y_{j}\rangle=0$ for all $1\leq
i\leq\frac{m}{2},\frac{m}{2}+1\leq j\leq m$. Thus,
$\stackon[.5pt]{X}{\scriptscriptstyle\sim}\perp\stackon[.5pt]{Y}{\scriptscriptstyle\sim}$.
∎

By Proposition 3.1, given any two subspaces, we can always find orthogonal
subspaces at the cost of reducing the dimension by half. The following result
again appeals to Lemma 3.2 in order to show that given two subspaces of a
fixed dimension, it is possible to traverse from one subspace to another
through a continuously varying choice of subspaces of the same dimension.

######  Proposition 3.3.

Let $X,Y\subset\mathbb{R}^{n}$, with $\dim(X)=\dim(Y)=m$. Then, for any
$a<b\in\mathbb{R}$, there exists a continuous choice of subspaces
$\\{U(t)\\}_{t\in[a,b]}$ of $\mathbb{R}^{n}$, such that $X=U(a)$ and $Y=U(b)$,
and $U(t)$ lies in $X+Y$ for all $t\in[a,b]$.

###### Proof.

Using Lemma 3.2, we can find an orthonormal bases $\\{x_{1},\ldots x_{m}\\}$
and $\\{y_{1},\ldots y_{m}\\}$ of $X$ and $Y$ respectively such that $\langle
x_{i},y_{j}\rangle=0$ whenever $i\neq j$. Now define for $1\leq i\leq m$,

$u_{i}(t)=\left\\{\begin{array}[]{ll}\left(1-\dfrac{t-a}{b-a}\right)x_{i}+\left(\dfrac{t-a}{b-a}\right)y_{i}&\text{if
$x_{i}$, $y_{i}$ are linearly independent}\\\ y_{i}&\text{if $x_{i}$, $y_{i}$
are linearly dependent.}\end{array}\right.$

Let $U(t)=\langle u_{1}(t),u_{2}(t),\ldots,u_{m}(t)\rangle$. Observe that
$U(a)=X$ and $U(b)=Y$. Notice that for any $t\in[a,b]$, at no point do we have
linear dependence between the $u_{i}$’s as, in fact, they are always
orthogonal. Thus, $\\{U(t)\\}_{t\in[a,b]}$ as defined above is our required
family of subspaces. ∎

The following lemma guarantees the existence of a discrete collection of
points in $\mathbb{R}^{n}$ such that the application of Theorem 1.1 on all
points of this collection preserves the desired minimal stretch property on
overlapping intervals covering $\mathbb{R}$.

######  Lemma 3.4.

Let $\varepsilon>0$ and $A:\mathbb{R}\to M_{n\times n}(\mathbb{R})$ be a
continuous matrix function. Then there exists a sequence
$(t_{i})_{i\in\mathbb{Z}}$ in $\mathbb{R}$ such that the following are
satisfied.

  1. (i)

For all $i\in\mathbb{Z}$, $t_{i}<t_{i+1}$, $\sup_{i}t_{i}=\infty$, and
$\inf_{i}t_{i}=-\infty$.

  2. (ii)

For all $i\in\mathbb{Z}$ and $t$ in $[t_{i-1},t_{i+1}]$,
$\|A(t_{i})-A(t)\|\leq\varepsilon$.

In particular, if $i\in\mathbb{Z}$, $c>0$, and $U$ is a subspace of
$\mathbb{R}^{n}$ such that $m_{A(t_{i})|_{U}}\geq c$ then for all
$t\in[t_{i-1},t_{i+1}]$, $m_{A(t)|_{U}}\geq c-\varepsilon$.

###### Proof.

By the uniform continuity of $A$ on each compact interval $[i,i+1]$, there
exists $k_{i}\in\mathbb{N}$ such that for all $s,t$ in $[i,i+1]$ with
$|s-t|\leq 1/k_{i}$, $\|A(s)-A(t)\|\leq\varepsilon/2$. Denote
$F_{i}=\\{i+j/k_{i}:j=0,1,\ldots,k_{i}-1\\}$ and define
$F=\cup_{i\in\mathbb{Z}}F_{i}$. Clearly, this is a discrete subset of
$\mathbb{R}$ that is unbounded above and unbounded below. Enumerating it in
increasing order yields the desired sequence $(t_{i})_{i\in\mathbb{Z}}$ that
satisfies (i) and (ii).

For the final part let $i\in\mathbb{Z}$, $c>0$, and $U$ be a subspace of
$\mathbb{R}^{n}$ such that $m_{A(t_{i})|_{U}}\geq c$. Then, for all $x\in U$
with $\|x\|=1$ and $t\in[t_{i-1},t_{i+1}]$,

$\|A(t)x\|\geq\|A(t_{i})x\|-\|A(t_{i})-A(t)\|\|x\|\geq c-\varepsilon.$

In other words, $m_{A(t)|_{U}}\geq c-\varepsilon$. ∎

We can now prove Theorem 1.2, which we restate for convenience.

######  Theorem 3.5.

Let $A:\mathbb{R}\rightarrow M_{n\times n}$ be a continuous matrix function,
satisfying the property that for all $t\in\mathbb{R}$, $\|A(t)e_{i}\|=1$ for
every $1\leq i\leq n$. Let $\Lambda=\sup_{t}\|A(t)\|$ and $\gamma\in(0,1)$.
Then, there exists a continuous family of $m$-dimensional subspaces
$\\{U(t)\\}_{t\in\mathbb{R}}$ where $m\geq(d_{0}n)/(7\Lambda^{2})$ such that
for every $t\in\mathbb{R},$ and every $v\in U(t)$, $\|Av\|\geq\gamma
c_{0}\|v\|$.

###### Proof.

To begin, note it is always possible to find a continuous choice of one-
dimensional subspaces by taking $U(t)=\langle e_{1}\rangle$, for all
$t\in\mathbb{R}$. Let $m_{0}=\lceil d_{0}n/\Lambda^{2}\rceil$. We will show
that there is continuous choice of $\lfloor m_{0}/4\rfloor$-dimensional
subspaces that satisfies the conclusion. Therefore, we can achieve
$1\vee\lfloor m_{0}/4\rfloor$ which dominates $m_{0}/7$ for all possible
values of $m_{0}$.

Apply Lemma 3.4 to $A$ for $0<\varepsilon<(1-c)c_{0}$ to find an increasing
sequence of points $(t_{i})_{i\in\mathbb{Z}}$ satisfying the conclusion of
that lemma. We will later specify that $\varepsilon$ needs in fact to be taken
even smaller. For each $i\in\mathbb{Z}$ apply Theorem 1.1 to $A(t_{i})$ to
obtain a set $\sigma_{i}$ of a common cardinality $m_{0}\geq
d_{0}n/\Lambda^{2}$. For each $i\in\mathbb{Z}$, by letting $U_{i}=\langle
e_{j}:j\in\sigma_{i}\rangle$, we have for all $t\in[t_{i-1},t_{i+1}]$ that
$m_{A(t)|_{U_{i}}}\geq\gamma c_{0}$.

Let $i\in\mathbb{Z}$ be given. We will outline the mechanism by which one
produces the required subspaces on $[t_{i},t_{i+1}]$, and then conclude by
extending the construction to all of $\mathbb{R}$ by working on each interval
and “stitching” together at the boundaries. Given $i$ and
$t\in[t_{i-1},t_{i+1}]$ let $V_{i,t}:=\langle
A(t)e_{j}:j\in\sigma_{i}\rangle=A(t)(U_{i})$.

A diagram illustrating the choice of subspaces on the interval
$[t_{i},t_{i+2}]$ is included below for the reader’s convenience.

$\sigma_{i}$$\sigma_{i}{}_{+}{}_{1}$$\sigma_{i}{}_{+}{}_{2}$$t_{i}$$t_{i}{}_{+}{}_{1}$$t_{i}{}_{+}{}_{2}$$s_{i}$$s_{i}{}_{+}{}_{1}$$U_{i}^{L}$$U_{i+1}^{R}$$U_{i+1}^{L}$$U{{}_{i+2}^{R}}$$\widetilde{\
\ }$$\widetilde{\ \ }$$\widetilde{\ \ }$$\widetilde{\ \
}$$U_{i}$$U_{i}{}_{+}{}_{1}$$U_{i}{}_{+}{}_{2}$$V_{i}^{L}\perp\
V_{i+1}^{R}$$U_{i+1}^{L}\perp\ U_{i+2}^{R}$$U_{i}^{L}\perp\
U_{i+1}^{R}$$V_{i+1}^{L}\perp\ V_{i+2}^{R}$$\tilde{\
}$$\tilde{}$$\tilde{}$$\tilde{}$$\tilde{}$$\tilde{}$$\tilde{}$$\tilde{}$

Fix an $s_{i}\in(t_{i},t_{i+1})$. At $s_{i}$, we apply Proposition 3.1 to the
subspaces $V_{i,s_{i}}$ and $V_{i+1,s_{i}}$ to obtain subspaces
$\stackon[.5pt]{V}{\scriptscriptstyle\sim}^{L}_{i,s_{i}}\subset V_{i,s_{i}}$
and $\stackon[.5pt]{V}{\scriptscriptstyle\sim}^{R}_{i+1,s_{i}}\subset
V_{i+1,s_{i}}$ such that
$\stackon[.5pt]{V}{\scriptscriptstyle\sim}^{L}_{i,s_{i}}\perp\stackon[.5pt]{V}{\scriptscriptstyle\sim}^{R}_{i+1,s_{i}}$
and
$\dim\stackon[.5pt]{V}{\scriptscriptstyle\sim}^{L}_{i,s_{i}}=\dim\stackon[.5pt]{V}{\scriptscriptstyle\sim}_{i+1,s_{i}}^{R}=\lfloor\frac{m_{0}}{2}\rfloor$.

We once more invoke Proposition 3.1 at the pre-images of
$\stackon[.5pt]{V}{\scriptscriptstyle\sim}_{i+1,s_{i}}^{R}$ and
$\stackon[.5pt]{V}{\scriptscriptstyle\sim}_{i,s_{i}}^{L}$ under $A$ to obtain
subspaces
$\tilde{U}^{L}_{i}\subset(A(s_{i})|_{U_{i}})^{-1}\left(\stackon[.5pt]{V}{\scriptscriptstyle\sim}_{i+1,s_{i}}^{R}\right)\subset
U_{i}$ and
$\stackon[.5pt]{U}{\scriptscriptstyle\sim}^{R}_{i+1}\subset(A(s_{i})|_{U_{i+1}})^{-1}\left(\stackon[.5pt]{V}{\scriptscriptstyle\sim}_{i,s_{i}}^{L}\right)\subset
U_{i+1}$ such that
$\stackon[.5pt]{U}{\scriptscriptstyle\sim}^{L}_{i}\perp\stackon[.5pt]{U}{\scriptscriptstyle\sim}^{R}_{i+1}$.
The iterative application of Proposition 3.1 incurs a further loss of
dimension: for all $t\in[t_{i},t_{i+1}],$

$\dim\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i,t}^{L}=\dim\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i+1,t}^{R}=\left\lfloor\frac{1}{2}\left\lfloor\frac{m_{0}}{2}\right\rfloor\right\rfloor=\left\lfloor\frac{m_{0}}{4}\right\rfloor.$

Now, we must find a way to continuously “stitch”
$\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i}^{L}$ and
$\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i+1}^{R}$ around $s_{i}$, and
similarly between $\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i+1}^{R}$ and
$\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i+1}^{L}$ to pass to the next
interval. This second “stitch” will be necessary as there is no reason to
suppose that
$\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i+1}^{R}=\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i+1}^{L}$.

To this end, we pick some
$\eta_{i}\in(0,\min\\{\frac{s_{i}-t_{i}}{2},\frac{t_{i+1}-s_{i}}{2}\\})$. This
will be the margin through at which the “stitching” occurs (that is, there
will be two instances of “stitching together”: on
$(s_{i}-\eta_{i},s_{i}+\eta_{i})$ and on $(t_{i+1}-\eta_{i},t_{i+1}]$).

Observe that an application of Proposition 3.3 allows us to switch from
$\stackon[.5pt]{U}{\scriptscriptstyle\sim}^{L}_{i}$ at $s_{i}-\eta_{i}$ to
$\stackon[.5pt]{U}{\scriptscriptstyle\sim}^{R}_{i+1}$ at $s_{i}+\eta_{i}$,
through subspaces of dimension $m_{0}$ without violating the minimal stretch
property as the collection of subspaces are contained in
$\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i}^{L}\oplus\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i+1}^{R}$.
This will be verified in Lemma 3.6.

It therefore remains only to “stitch” together on
$(t_{i+1}-\eta_{i},t_{i+1}]\subsetneq(s_{i},t_{i+1}]$. Notice that
$\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i+1}^{R}\subset U_{i+1}$, and
$\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i+1}^{L}\subset U_{i+1}$. As the
minimal stretch property holds for all vectors in $U_{i+1}$, the minimal
stretch property also holds in
$\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i+1}^{R}+\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i+1}^{L}$.
Thus, we may appeal to Proposition 3.3 once again, and find a collection of
subspaces of dimension $\lfloor\frac{m_{0}}{4}\rfloor$ to traverse from
$\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i+1}^{R}$ at $t_{i+1}-\eta_{i}$,
to $\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i+1}^{L}$ at $t_{i+1}$.

To recapitulate, on each $[t_{i},t_{i+1}]$, we take:

$\displaystyle\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i}^{L}$
$\displaystyle\text{ for }t\in[t_{i},s_{i}-\eta_{i}],$
$\displaystyle\text{``stitch''
}\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i}^{L}\text{ and
}\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i+1}^{R}$ $\displaystyle\text{ for
}t\in(s_{i}-\eta_{i},s_{i}+\eta_{i}),$
$\displaystyle\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i+1}^{R}$
$\displaystyle\text{ for }t\in[s_{i}+\eta_{i},t_{i+1}-\eta_{i}],$
$\displaystyle\text{``stitch''
}\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i+1}^{R}\text{ and
}\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i+1}^{L}$ $\displaystyle\text{ for
}t\in(t_{i+1}-\eta_{i},t_{i+1}),$
$\displaystyle\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i+1,t}^{L}$
$\displaystyle\text{ for }t=t_{i+1}.\qed$

######  Lemma 3.6.

For any vector $x$ lying in
$\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i}^{L}\oplus\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i+1}^{R},\
i\in\mathbb{Z}$, the vector $x$ satisfies $\|A(t)x\|\geq\gamma c_{0}\|x\|$,
when $t\in[t_{i},t_{i+1}]$.

###### Proof.

If
$x\in\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i}^{L}\oplus\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i+1}^{R}$,
then $x=f+g$, where $f\in\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i}^{L}$
and $g\in U_{i+1}^{R}$. As $\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i}^{L}$
and $\stackon[.5pt]{U}{\scriptscriptstyle\sim}_{i+1}^{R}$ satisfy the minimal
stretch property, we know that $\|A(t)f\|\geq c_{0}\|f\|$ for
$t\in[t_{i-1},t_{i+1}]$, and $\|A(t)g\|\geq c_{0}\|g\|$ for
$t\in[t_{i},t_{i+2}]$. Then for $t\in[t_{i-1},t_{i+1}]$, we have

$\displaystyle\|A(t)x\|^{2}$
$\displaystyle=\|A(t)f\|^{2}+\|A(t)g\|^{2}+2\langle A(t)f,A(t)g\rangle$
$\displaystyle\geq c_{0}^{2}\|f\|^{2}+c_{0}^{2}\|g\|^{2}+2\langle
A(t)f,A(t)g\rangle$ $\displaystyle=c_{0}^{2}\|x\|^{2}+2\langle
A(t)f,A(t)g\rangle.$ (2)

Now recall that
$A(s_{i})f\in\stackon[.5pt]{V}{\scriptscriptstyle\sim}_{i+1,s_{i}}^{R}$ and
$A(s_{i})g\in\stackon[.5pt]{V}{\scriptscriptstyle\sim}_{i,s_{i}}^{L}$ so

$\displaystyle|\langle A(t)f,A(t)g\rangle|$ $\displaystyle=|\langle
A(t)f-A(s_{i})f,A(t)g\rangle+\langle A(s_{i})f,A(t)g-A(s_{i})g\rangle+\langle
A(s_{i})f,A(s_{i})g\rangle|$
$\displaystyle\leq\big{(}\big{\|}A(t)-A(s_{i})\big{\|}\|f\|\big{)}\big{(}\big{\|}A(t)\big{\|}\|g\|\big{)}+\big{(}\big{\|}A(s_{i})\big{\|}\|f\|\big{)}\big{(}\big{\|}A(t)-A(s_{i})\big{\|}\|g\|\big{)}$
$\displaystyle\phantom{\leq}+0$
$\displaystyle\leq\Lambda\|A(t)-A(s_{i})\|\|x\|^{2}.$

From Lemma 3.4 (ii), we know that $\|A(t)-A(s_{i})\|\leq\varepsilon$.
Substituting this in (2), we obtain

$\displaystyle\|A(t)x\|^{2}$ $\displaystyle\geq
c_{0}^{2}\|x\|^{2}\Big{(}1-2\Lambda\varepsilon c_{0}^{-2}\Big{)}.$

By taking $\varepsilon=c_{0}^{2}(1-\gamma^{2})/(2\Lambda)$ in Lemma 3.4, we
obtain $\|A(t)x\|\geq\gamma c_{0}\|x\|.$∎

######  Remark 3.7.

We sketch an argument that demonstrates that the dimensional estimate
$n/\|A\|^{2}$ in Theorem 1.1 (and hence also in Theorem 1.2) is optimal, up to
a constant. Assume that for $n\in\mathbb{N}$ and $1\leq\lambda\leq\sqrt{n}$,
there is a $m(n,\lambda)\in\mathbb{N}$ such that for any $n\times n$ matrix
$A$ with unit-length columns and $\|A\|\leq\lambda$, there exists
$\sigma\subset\\{1,\ldots,n\\}$ with $|\sigma|\geq m(n,\lambda)$ and
$m_{A|_{U_{\sigma}}}>0$. We will show that necessarily
$m(n,\lambda)<4n/\lambda^{2}$. To find an $A$ that confirms this, take
$m=\lceil n/\lambda^{2}\rceil$ and using Euclidean division write $n=dm+r$.
Find an orthonormal sequence $u_{1},\ldots,u_{m}$ in $\mathbb{R}^{n}$ such
that $\langle u_{1},\ldots,u_{m}\rangle\perp\langle
e_{1},\ldots,e_{r}\rangle$. Define $U=[u_{1}\cdots u_{m}]\in M_{n\times m}$,
$B=[U|\cdots|U]\in M_{n\times dm}$ (take $d$ copies of $U$), $D=[e_{1}\cdots
e_{r}]\in M_{n\times r}$ and $A=[D|B]\in M_{n\times n}$. Then, $A$ has unit-
length columns, $\|A\|=\sqrt{d}\leq\lambda$, and $\rank(A)=m+r<2m\leq
4n/\lambda^{2}$. Therefore, for any $\sigma\subset\\{1,\ldots,n\\}$ such that
$m_{A|_{U_{\sigma}}}>0$ must satisfy
$m(n,\lambda)\leq|\sigma|\leq\rank(A)<4n/\lambda^{2}$.

###  3.2. Continuous factorization of the identity

In this subsection we explain how Theorem 1.2 yields a solution to Problem 2.
We begin with a lemma that will help us find the left matrix in the
factorization of the identity.

######  Lemma 3.8.

Let $I$ be an interval of $\mathbb{R}$ and $A:I\to M_{n\times m}$ be a
continuous matrix function such that there exists $c>0$ with $m_{A(t)}\geq c$
for all $t$. Then there exists a continuous matrix function $L:\mathbb{R}\to
M_{m\times n}$ such that $L(t)A(t)=I_{m}$ and $\|L(t)\|\leq 1/c$ for all $t\in
I$.

###### Proof.

For each fixed $t\in I$ we have that $m_{A(t)}>0$ and thus $A(t)$ has trivial
kernel. This implies that the $m\times m$ matrix $A^{T}(t)A(t)$ has trivial
kernel and is thus invertible. Since the matrix function $A^{T}A:I\to
M_{m\times m}$ is continuous and pointwise invertible, $(A^{T}A)^{-1}:I\to
M_{m\times m}$ is continuous as well (see, e.g., [8, Lemma 3.2]). Then,
$L=(A^{T}A)^{-1}A^{T}:I\to M_{m\times n}$ is continuous and for each $t\in I$,
$L(t)A(t)=I_{m}$. To find $\|L(t)\|$, for fixed $t\in I$, write the singular
value decomposition $A(t)=U\Sigma V^{T}$ where $U,V$ are unitary and $\Sigma$
is rectangular diagonal. A direct computation yields
$L(t)=V\tilde{\Sigma}U^{T}$, where
$\tilde{\Sigma}=(\Sigma^{T}\Sigma)^{-1}\Sigma^{T}$, which is the matrix formed
by taking reciprocals of all non-zero diagonal elements of $\Sigma$ and then
taking the transpose. Since $V,U$ are unitary and thus preserve the matrix
norm under multiplication, $\|L(t)\|=\|\tilde{\Sigma}\|\leq 1/c$. ∎

To find the right matrix, we will use Theorem 1.2 and Theorem 2.5.

######  Theorem 3.9.

Let $A:\mathbb{R}\to M_{n\times n}$ be a continuous matrix function and
$\theta>0$ with $\|A(t)e_{i}\|\geq\theta$ for $1\leq i\leq n$ and
$\|A(t)\|\leq 1$ for $t\in\mathbb{R}$. Then for any $\gamma\in(0,1)$ and
$m\leq\lceil(d_{0}/7)n\theta^{2}\rceil$ there exist continuous matrix
functions $L,R$ of appropriate dimensions such that $L(t)A(t)R(t)=I_{m}$ with
$\|L(t)\|\|R(t)\|\leq C/\theta$ for all $t\in\mathbb{R}$, where $C=(\gamma
c_{0})^{-1}$.

###### Proof.

Let $a_{k}(t)$ denote the $k$th column of $A(t)$,

$D(t)=\bigg{[}\frac{e_{1}}{\|a_{1}(t)\|}\cdots\frac{e_{n}}{\|a_{n}(t)\|}\bigg{]}\quad\text{
and }\tilde{A}(t)=A(t)D(t).$

Note that

$\|\tilde{A}(t)\|\leq\|A(t)\|\max_{1\leq i\leq
n}\|a_{i}(t)\|\leq\frac{1}{\theta}.$

Also, $A$ satisfies the hypothesis of Theorem 3.5, so that we have the
existence of a collection of $m$-dimensional subspaces
$\\{U(t)\\}_{t\in\mathbb{R}}$ that vary continuously such that
$m_{\tilde{A}(t)|_{U(t)}}\geq\gamma c_{0}$ for all $t\in\mathbb{R}$, where

$m\geq\frac{d_{0}}{7}\frac{n}{\sup_{t}\|\tilde{A}(t)\|^{2}}\geq\frac{d_{0}}{7}n\theta^{2}.$

By Theorem 2.5 there exists a continuous choice of orthonormal basis
$u_{1},\ldots,u_{m}:\mathbb{R}\to\mathbb{R}^{n}$. Define $W(t)=[u_{1}(t)\cdots
u_{m}(t)]$, which is a continuous matrix function with the property
$\operatorname{Im}(W(t))=U(t)$ and for all $x\in\mathbb{R}^{m}$,
$\|W(t)x\|=\|x\|$. Let $R(t)=D(t)W(t)$, which is continuous and satisfies
$\|R(t)\|=\|D(t)\|\leq 1/\theta$.

Now since

$\displaystyle m_{A(t)R(t)}$
$\displaystyle=\inf\Big{\\{}\|\tilde{A}(t)W(t)x\|:x\in\mathbb{R}^{m},\|x\|=1\Big{\\}}$
$\displaystyle=\inf\Big{\\{}\|\tilde{A}(t)x\|:x\in
U(t),\|x\|=1\Big{\\}}\geq\gamma c_{0}$

we can apply Lemma 3.8 to $A(t)R(t)$ to show the existence of a continuous
left inverse $L(t)$ of $A(t)R(t)$ that satisfies $\|L(t)\|\leq(\gamma
c_{0})^{-1}$ for all $t\in\mathbb{R}$. ∎

##  4\. Method II: Column Space Approach

In this section, we prove Theorem 1.4. The goal is to attain a continuous
choice of subspaces on which a given matrix function satisfies the desired
minimal stretch property that more closely resembles spaces spanned by a
subset of the unit vector basis. These will be quadratic convex combinations
of disjoint basis vectors (see Definition 1.3). Therefore, we require a
statement that guarantees the existence of suitable pairs of subspaces spanned
by disjoint basis vectors that behave sufficiently well with one another so
that they can be “stitched” together.

###  4.1. A Bourgain-Tzafriri Theorem for disjoint subsets of the basis

We first prove the static result that is necessary in the proof of Theorem
1.4.

######  Theorem 4.1.

There exist constants $1>d_{1}>d_{2}>d_{3}>0$ such that the following holds.
For every $n\times n$ matrix $A$ with $\|Ae_{i}\|=1$ for $i=1,\ldots,n$, and
for every $\sigma_{1}\subset\\{1,\ldots,n\\}$ with $|\sigma_{1}|\leq
d_{1}n\|A\|^{-2}$, there exists

$\sigma_{2}\subset\\{1,\ldots,n\\}\setminus\sigma_{1}\text{ with
}|\sigma_{2}|\geq d_{2}n\|A\|^{-2}$

such that for any choice of scalars
$\\{a_{j}\\}_{j\in{\sigma_{1}\cup\sigma_{2}}}$, we have

$\Big{\|}\sum_{j\in\sigma_{1}\cup\sigma_{2}}a_{j}Ae_{j}\Big{\|}\geq\frac{1}{16\sqrt{2}}\Big{(}\sum_{j\in\sigma_{2}}|a_{j}|^{2}\Big{)}^{1/2}.$

If we additionally assume that $|\sigma_{1}|\geq d_{2}n\|A\|^{-2}$ and
$d_{1}d_{2}n\|A\|^{-4}\geq 1$ then there also exist

$\tau_{1}\subset\sigma_{1}\text{ and
}\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}_{2}\subset\sigma_{2}\text{
with }|\tau_{1}|\geq d_{3}n\|A\|^{-4}\text{ and
}|\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}_{2}|\geq d_{3}n\|A\|^{-4}$

such that for any choice of scalars
$\\{a_{j}\\}_{j\in\tau_{1}\cup\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}_{2}}$,
we have

$\Big{\|}\sum_{j\in\tau_{1}\cup\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}_{2}}a_{j}Ae_{j}\Big{\|}\geq\frac{1}{32}\Big{(}\sum_{j\in\tau_{1}\cup\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}_{2}}|a_{j}|^{2}\Big{)}^{1/2}.$

In order to make the theorem more tractable, the proof is broken down into
lemmata. The argument below follows the general shape of the argument first
made in [4]. In Lemmata 4.3, 4.4, and 4.5 below it is assumed that we are
given an $n\times n$ matrix $A$ that satisfies the assumptions of Theorem 4.1
(i.e., $\left\|Ae_{i}\right\|=1$ for $i=1,\ldots,n$).

######  Remark 4.2.

The constants in the Theorem 4.1 are $d_{1}=1/320$ (proof of Lemma 4.3),
$d_{2}=d_{1}/4$ (Lemma 4.4), and $d_{3}=d_{2}^{2}/2$ (proof of Lemma 4.5).

######  Lemma 4.3.

There exists a constant $d_{1}>0$ such that the following holds: For every
$\sigma_{1}\subset\\{1,\ldots,n\\}$ with $|\sigma_{1}|\leq d_{1}n\|A\|^{-2}$
there exists $\sigma_{2}\subset\\{1,\ldots,n\\}$ with $\sigma_{2}\geq
d_{1}n\|A\|^{-2}$ such that for every $i\in\sigma_{2}$,

$\big{\|}P_{\langle
Ae_{j}:j\in(\sigma_{1}\cup\sigma_{2})\setminus\\{i\\}\rangle}Ae_{i}\big{\|}<\frac{1}{\sqrt{2}}.$

###### Proof.

Take $\delta=1/(8\|A\|^{2})$ and $d_{1}=1/(8\cdot 40)$. Let
$\left\\{\xi_{i}\right\\}_{i\in\sigma_{1}^{c}}$ be a sequence of independent
random variables of mean $\delta$ over a probability space
$(\Omega,\Sigma,\mu)$ taking only the values 0 and 1. Define

$D=\Big{\\{}\omega\in\Omega:\Big{|}\sum_{i\in\sigma_{1}^{c}}\xi_{i}(\omega)-\delta|\sigma_{1}^{c}|\Big{|}\geq\delta|\sigma_{1}^{c}|/2\Big{\\}}.$

By Bernstein’s inequality (see, e.g., [4, Lemma 1.3] or [3]),

$\mu(D)\leq 2e^{-\delta|\sigma_{1}^{c}|/10}.$ (3)

For each $\omega\in\Omega$, let

$\sigma(\omega)=\left\\{j\in\sigma_{1}^{c}:\xi_{j}(\omega)=1\right\\}.$

We will show that there must be at least one $\sigma(\omega)$ which can be
modified slightly to have the desired property. Set $V=\langle
Ae_{i}:i\in\sigma_{1}\rangle$. Then

$\displaystyle\int_{\Omega}\sum_{i\in\sigma_{1}^{c}}\xi_{i}(\omega)\left\|P_{\langle\xi_{j}(\omega)Ae_{j}\cup
V\rangle_{j\neq i,j\in\sigma_{1}^{c}}}(Ae_{i})\right\|^{2}d\mu$
$\displaystyle=\sum_{i\in\sigma_{1}^{c}}\bigg{(}\int_{\Omega}\xi_{i}(\omega)d\mu\bigg{)}\bigg{(}\int_{\Omega}\left\|P_{\langle\xi_{j}(\omega)Ae_{j}\cup
V\rangle_{j\neq i,j\in\sigma_{1}^{c}}}(Ae_{i})\right\|^{2}d\mu\bigg{)}$
$\displaystyle=\delta\int_{\Omega}\sum_{i\in\sigma_{1}^{c}}\left\|P_{\langle\xi_{j}(\omega)Ae_{j}\cup
V\rangle_{j\neq i,j\in\sigma_{1}^{c}}}(Ae_{i})\right\|^{2}d\mu$
$\displaystyle\leq\delta\int_{\Omega}\sum_{i\in\sigma_{1}^{c}}\left\|P_{\langle\xi_{j}(\omega)Ae_{j}\cup
V\rangle_{j\in\sigma_{1}^{c}}}(Ae_{i})\right\|^{2}d\mu$

where the first equality used the fact that $\xi_{i}(\omega)$ and
$\left\|P_{\langle\xi_{j}(\omega)Ae_{j}\cup V\rangle_{j\neq
i,j\in\sigma_{1}^{c}}}(Ae_{i})\right\|^{2}$ are independent (since the latter
is a function of $(\xi_{1},\ldots\xi_{i-1},\xi_{i+1},\ldots\xi_{n})$ so that
we may split up the integral into a product) and the last line used the
monotonicity of projection norms. By letting
$W(\omega)=\\{\xi_{j}(\omega)Ae_{j}:j\in\sigma_{1}^{c}\\}\cup V,$ we have

$\displaystyle\int_{\Omega}\sum_{i\in\sigma_{1}^{c}}\xi_{i}(\omega)\left\|P_{\langle\xi_{j}(\omega)Ae_{j}\cup
V\rangle_{j\neq i,j\in\sigma_{1}^{c}}}(Ae_{i})\right\|^{2}d\mu$
$\displaystyle\leq\delta\int_{\Omega}\sum_{i\in\sigma_{1}^{c}}\left\|P_{\langle
W(\omega)\rangle}(Ae_{i})\right\|^{2}d\mu$
$\displaystyle\leq\delta\int_{\Omega}\sum_{i=1}^{n}\left\|P_{\langle
W(\omega)\rangle}(Ae_{i})\right\|^{2}d\mu$
$\displaystyle=\delta\int_{\Omega}\left\|P_{\langle
W(\omega)\rangle}A\right\|_{\mathrm{HS}}^{2}d\mu$
$\displaystyle\leq\delta\|A\|^{2}\int_{\Omega}\left(|\sigma_{1}|+\sum_{j\in\sigma_{1}^{c}}\xi_{j}(\omega)\right)\
d\mu$
$\displaystyle=\delta\|A\|^{2}\left(|\sigma_{1}|+\delta|\sigma_{1}^{c}|\right)$

where we used the standard inequality
$\|A\|^{2}_{\mathrm{HS}}\leq\|A\|^{2}\mathrm{rank}(A)$ and then made use of
the fact that $\mathrm{rank}(P_{\langle W(\omega)\rangle}A)$ is bounded above
by the number of non-zero vectors in
$\\{\xi_{i}(\omega):i\in\sigma_{1}^{c}\\}\cup\\{Ae_{i}:i\in\sigma_{1}\\}$
which has the crude bound
$|\sigma_{1}|+\sum_{j\in\sigma_{1}^{c}}\xi_{j}(\omega)$.

Since all functions involved are non-negative this yields:

$\displaystyle\int_{\Omega\setminus
D}\,\sum_{i\in\sigma_{1}^{c}}\xi_{i}(\omega)\left\|P_{\langle\xi_{j}(\omega)Ae_{j}\cup
V\rangle_{j\neq i,j\in\sigma_{1}^{c}}}\left(Ae_{i}\right)\right\|^{2}d\mu$
$\displaystyle\leq\int_{\Omega}\,\sum_{i\in\sigma_{1}^{c}}\xi_{i}(\omega)\left\|P_{\langle\xi_{j}(\omega)Ae_{j}\cup
V\rangle_{j\neq i,j\in\sigma_{1}^{c}}}\left(Ae_{i}\right)\right\|^{2}d\mu$
$\displaystyle\leq\delta\|A\|^{2}\left(|\sigma_{1}|+\delta|\sigma_{1}^{c}|\right)$

which, with (3), implies that there exists a point
$\omega_{0}\in\Omega\setminus D$ such that

$\displaystyle\displaystyle\sum_{i\in\sigma(\omega_{0})}\left\|P_{\langle
Ae_{j}\cup
V\rangle_{j\in\sigma(\omega_{0})\setminus\\{i\\}}}(Ae_{i})\right\|^{2}$
$\displaystyle=\sum_{i\in\sigma_{1}^{c}}\xi_{i}(\omega_{0})\left\|P_{\langle\xi_{j}(\omega_{0})Ae_{j}\cup
V\rangle_{j\neq i,j\in\sigma_{1}^{c}}}\left(Ae_{i}\right)\right\|^{2}$
$\displaystyle\leq\frac{\delta\|A\|^{2}(|\sigma_{1}|+\delta|\sigma_{1}^{c}|)}{1-\mu(D)}$
$\displaystyle\leq\frac{\delta\|A\|^{2}(|\sigma_{1}|+\delta|\sigma_{1}^{c}|)}{1-2\exp\bigg(\tfrac{-\delta|\sigma_{1}^{c}|}{10}\bigg{missing})}.$

The exponential factor in the denominator can be dealt with by working with
working with two separate cases:

Case 1: $\delta n<40$. In this case since $d_{1}=1/(8\cdot 40)$ we have that

$\displaystyle d_{1}\frac{n}{\|A\|^{2}}$ $\displaystyle=\frac{n\delta}{40}<1$

so that $|\sigma_{1}|=0,$ and for any $\sigma_{2}\subset\\{1,\dots n\\}$, with
$|\sigma_{2}|=1$ the statement is vacuously true.

Case 2: $\delta n\geq 40$. Note that the assumption made on the columns of $A$
imply that $\|A\|^{2}\geq 1$. So since $d_{1}<1/2$ and $|\sigma_{1}|\leq
d_{1}n\|A\|^{-2}$ we must have that $|\sigma_{1}^{c}|\geq n/2$. Some simple
calculus shows that $1-2e^{-x}\geq 2/3$ for all $x\geq 2$ and thus

$\displaystyle\displaystyle\sum_{i\in\sigma(\omega_{0})}\left\|P_{\langle
Ae_{j}\cup
V\rangle_{j\in\sigma(\omega_{0})\setminus\\{i\\}}}(Ae_{i})\right\|^{2}\leq\frac{\delta\|A\|^{2}(|\sigma_{1}|+\delta|\sigma_{1}^{c}|)}{1-2\exp\bigg(\tfrac{-\delta|\sigma_{1}^{c}|}{10}\bigg{missing})}\leq\frac{3}{2}\delta\|A\|^{2}(|\sigma_{1}|+\delta|\sigma_{1}^{c}|).$

By definition of $D$, we also have:

$\displaystyle\left|\sigma(\omega_{0})\right|=\sum_{i\in\sigma_{1}^{c}}\xi_{i}\left(\omega_{0}\right)\geq\delta|\sigma_{1}^{c}|/2.$

Let

$\sigma_{2}=\bigg{\\{}i\in\sigma(\omega_{0}):\left\|P_{\langle Ae_{j}\cup
V\rangle_{j\in\sigma(\omega_{0})\setminus\\{i\\}}}(Ae_{i})\right\|<2\|A\|\sqrt{\delta}\bigg{\\}}.$

Note that, given our choice of $\delta,$ $\sigma_{2}$ satisfies the desired
conclusion. We just need to provide a lower bound on its size. Now,

$\displaystyle\sum_{i\in\sigma(\omega_{0})\setminus\sigma_{2}}\left\|P_{\langle
Ae_{j}\cup
V\rangle_{j\in\sigma(\omega_{0})\setminus\\{i\\}}}(Ae_{i})\right\|^{2}\leq\sum_{i\in\sigma(\omega_{0})}\left\|P_{\langle
Ae_{j}\cup
V\rangle_{j\in\sigma(\omega_{0})\setminus\\{i\\}}}(Ae_{i})\right\|^{2}$
$\displaystyle\leq\frac{3}{2}\delta\|A\|^{2}\left(|\sigma_{1}|+\delta|\sigma_{1}^{c}|\right).$

so, using the definition of $\sigma_{2}$,

$4\|A\|^{2}\delta|\sigma(\omega_{0})\setminus\sigma_{2}|\leq\frac{3}{2}\delta\|A\|^{2}(|\sigma_{1}|+\delta|\sigma_{1}^{c}|).$

Since $|\sigma_{1}|\leq d_{1}n\|A\|^{-2}$ and
$|\sigma(\omega_{0})|\geq\delta|\sigma_{1}^{c}|/2$, we have

$\displaystyle 4\|A\|^{2}\delta|\sigma(\omega_{0})\setminus\sigma_{2}|$
$\displaystyle\leq\frac{3}{2}\delta\|A\|^{2}\left(d_{1}\frac{n}{\|A\|^{2}}+2|\sigma(\omega_{0})|\right).$

Solving this inequality for $|\sigma_{2}|$ yields

$\displaystyle|\sigma_{2}|$
$\displaystyle\geq\frac{1}{4}|\sigma(\omega_{0})|-\frac{3}{8}d_{1}\frac{n}{\|A\|^{2}}$
$\displaystyle\geq\delta\frac{|\sigma_{1}^{c}|}{8}-d_{1}\frac{n}{\|A\|^{2}}$
$\displaystyle=\frac{|\sigma_{1}^{c}|}{64\|A\|^{2}}-\frac{n}{320\|A\|^{2}}$
$\displaystyle\geq\frac{n}{128\|A\|^{2}}-\frac{n}{320\|A\|^{2}}\geq\frac{n}{320\|A\|^{2}}=d_{1}\frac{n}{\|A\|^{2}}.\qed$

######  Lemma 4.4.

For every $\sigma_{1}\subset\\{1,\ldots,n\\}$ with $|\sigma_{1}|\leq
d_{1}n\|A\|^{-2}$ there exists
$\sigma_{2}\subset\\{1,\ldots,n\\}\setminus\sigma_{1}$ with
$\sigma_{2}\geq(d_{1}/2)n\|A\|^{-2}$ such that for every
$\\{a_{j}\\}_{j\in\sigma_{1}\cup\sigma_{2}}$:

$\norm{\sum_{j\in\sigma_{1}\cup\sigma_{2}}a_{j}Ae_{j}}\geq\frac{1}{4\sqrt{2|\sigma_{2}}|}\sum_{j\in\sigma_{2}}|a_{j}|.$

###### Proof.

From Lemma 4.3 there exists $\sigma\subset\\{1,\dotsc,n\\}\setminus\sigma_{1}$
with $|\sigma|\geq d_{1}n/\|A\|^{2}$, such that if for every $i\in\sigma$ we
let $Ae_{i}=x_{i}$, then

$\norm{P_{\langle
Te_{k}:k\in(\sigma_{1}\cup\sigma)\setminus\\{i\\}\rangle}x_{i}}<\frac{1}{\sqrt{2}}.$

For every $i\in\sigma$, let $u_{i}^{\prime}=x_{i}-P_{\langle
Te_{k}:k\in(\sigma_{1}\cup\sigma)\setminus\\{i\\}\rangle}x_{i}$. Then, by
orthogonality,

$\norm{u_{i}^{\prime}}^{2}=\norm{x_{i}}^{2}-\norm{P_{\langle
Te_{k}:k\in(\tau\cup\sigma)\setminus\\{i\\}\rangle}x_{i}}^{2}>1-\frac{1}{2}=\frac{1}{2}$

and $\norm{u_{i}^{\prime}}\leq 1$. In addition, for $i\in\sigma_{1}\cup\sigma$
and $j\in\sigma$ with $i\neq j$,

$\displaystyle\langle x_{i},u^{\prime}_{j}\rangle$ $\displaystyle=\langle
x_{i},x_{j}-P_{\langle
Te_{k}:k\in(\sigma_{1}\cup\sigma)\setminus\\{j\\}\rangle}x_{j}\rangle$
$\displaystyle=\langle x_{i},x_{j}\rangle-\langle x_{i},P_{\langle
Te_{k}:k\in(\sigma_{1}\cup\sigma)\setminus\\{j\\}\rangle}x_{j}\rangle$
$\displaystyle=\langle x_{i},x_{j}\rangle-\langle P_{\langle
Te_{k}:k\in(\sigma_{1}\cup\sigma)\setminus\\{j\\}\rangle}x_{i},x_{j}\rangle=0.$

Similarly, for $i\in\sigma$

$\displaystyle\langle x_{i},u^{\prime}_{i}\rangle$
$\displaystyle=\|x_{i}\|^{2}-\langle x_{i},P_{\langle
Te_{k}:k\in(\sigma_{1}\cup\sigma)\setminus\\{i\\}\rangle}x_{i}\rangle$
$\displaystyle=1-\|P_{\langle
Te_{k}:k\in(\sigma_{1}\cup\sigma)\setminus\\{i\\}\rangle}x_{i}\|^{2}>1/2.$

For $i\in\sigma$ let $u_{i}=\|u_{i}^{\prime}\|^{-1}u_{i}^{\prime}$, so that
$1\geq\langle x_{i},u_{i}\rangle>1/2$.

If $E(X)$ denotes the expected value of the random variable $X$ over
$\\{-1,1\\}^{\sigma}$ with the uniform probability measure, a simple
calculation yields

$\mathbb{E}\Big{(}\Big{\|}\sum_{i\in\sigma}\varepsilon_{i}u_{i}\Big{\|}^{2}\Big{)}=\sum_{i\in\sigma}\norm{u_{i}}^{2}=|\sigma|.$

Thus if

$\mathcal{E}=\Big{\\{}(\varepsilon_{i})_{i\in\sigma}\in\\{-1,1\\}^{\sigma}:\Big{\|}\sum_{i\in\sigma}\varepsilon_{i}u_{i}\Big{\|}\leq
2\sqrt{|\sigma|}\Big{\\}},$

it follows then by Markov’s inequality that

$|\mathcal{E}|\geq\frac{3}{4}2^{|\sigma|}.$

By a theorem of Sauer and Shelah (see, e.g., [4, Page 144] or [17]), whenever
$k$ satisfies

$|\mathcal{E}|>\sum_{i=0}^{k-1}\binom{|\sigma|}{i},$ (4)

then there exists a subset $\sigma_{2}\subset\sigma$ of cardinality $k$ such
that for each tuple $(\varepsilon_{i})_{i\in\sigma_{2}}$ there exists an
extension $(\varepsilon_{i})_{i\in\sigma}$ which belongs to $\mathcal{E}$.
Note that (4) holds for $k\geq\frac{|\sigma|}{2}$ and therefore we may choose
$\sigma_{2}$ with $|\sigma_{2}|\geq(d_{1}n)/(2\|A\|^{2})$ and
$|\sigma_{2}|\geq|\sigma|/2$.

To see that $\sigma_{2}$ satisfies the conclusion, let
$\\{a_{j}\\}_{j\in\sigma_{1}\cup\sigma_{2}}$ be given. Define
$\theta_{i}\in\\{-1,1\\}$ for each $i\in\sigma_{2}$ so that
$\theta_{i}a_{i}=|a_{i}|$. Then let $(\varepsilon_{i})_{i\in\sigma}$ be an
extension of $(\theta_{i})_{i\in\sigma_{2}}$ that belongs to $\mathcal{E}$. It
follows that

$\displaystyle\Big{|}\Big{\langle}\sum_{j\in\sigma}\varepsilon_{j}u_{j},\sum_{j\in\sigma_{1}\cup\sigma_{2}}a_{j}x_{j}\Big{\rangle}\Big{|}$
$\displaystyle\leq\Big{\|}\sum_{j\in\sigma}\varepsilon_{j}u_{j}\Big{\|}\Big{\|}\sum_{j\in\sigma_{1}\cup\sigma_{2}}a_{j}x_{j}\Big{\|}$
$\displaystyle\leq
2\sqrt{|\sigma|}\Big{\|}\sum_{j\in\sigma_{1}\cup\sigma_{2}}a_{j}x_{j}\Big{\|}$
$\displaystyle\leq
2\sqrt{2|\sigma_{2}|}\Big{\|}\sum_{j\in\sigma_{1}\cup\sigma_{2}}a_{j}x_{j}\Big{\|}.$

Hence

$\displaystyle
2\sqrt{2}\sqrt{|\sigma_{2}|}\Big{\|}\sum_{j\in\sigma_{1}\cup\sigma_{2}}a_{j}x_{j}\Big{\|}$
$\displaystyle\geq\Big{|}\Big{\langle}\sum_{j\in\sigma}\varepsilon_{j}u_{j},\sum_{j\in\sigma_{1}\cup\sigma_{2}}a_{j}x_{j}\Big{\rangle}\Big{|}=\sum_{j\in\sigma_{2}}|a_{j}|\langle
x_{j},u_{j}\rangle\geq\frac{1}{2}\sum_{j\in\sigma_{2}}|a_{j}|.\qed$

In the next step, we will require Khintchine’s inequality which states the
following. Let $\\{1,-1\\}^{n}$ be endowed with the uniform probability
measure. For $\\{b_{\ell}\\}_{\ell=1}^{n}$ in $\mathbb{R}$ we have

$\mathbb{E}\left(\left|\sum_{\ell=1}^{n}\varepsilon_{\ell}b_{\ell}\right|\right)\geq\frac{1}{\sqrt{2}}\left(\sum_{\ell=1}^{n}\left|b_{\ell}\right|^{2}\right)^{1/2}.$

######  Lemma 4.5.

For every $\sigma_{1}\subset\\{1,\ldots,n\\}$ with $|\sigma_{1}|\leq
d_{1}n\|A\|^{-2}$, there exists
$\sigma_{2}\subset\\{1,\ldots,n\\}\setminus\sigma_{1}$ with
$\sigma_{2}\geq(d_{1}/4)n\|A\|^{-2}$ such that for every
$\\{a_{j}\\}_{j\in\sigma_{1}\cup\sigma_{2}}$ in $\mathbb{R}$:

$\norm{\sum_{j\in\sigma_{1}\cup\sigma_{2}}a_{j}Ae_{j}}\geq\frac{1}{16\sqrt{2}}\left(\sum_{j\in\sigma_{2}}|a_{j}|^{2}\right)^{1/2}.$

###### Proof.

Consider the set $\sigma$ supplied by applying Lemma 4.4 and denote
$c^{\prime}=1/(4\sqrt{2})$. We need to establish a subset
$\sigma_{2}\subset\sigma$ of cardinality $|\sigma_{2}|\geq|\sigma|/2$ such
that for any choice of coefficients in
$\\{a_{j}\\}_{j\in\sigma_{1}\cup\sigma_{2}}$:

$\norm{\sum_{j\in\sigma_{1}\cup\sigma_{2}}a_{j}Ae_{j}}\geq\frac{c^{\prime}}{4}\left(\sum_{j\in\sigma_{2}}|a_{j}|^{2}\right)^{1/2}.$

Suppose, for contradiction, that such a subset does not exist. Let
$Ae_{j}=x_{j}$. Put $\upsilon_{1}=\sigma$. Then there exists a vector
$y_{1}=\sum_{k\in\upsilon_{1}\cup\sigma_{1}}b_{1,k}x_{k}$ such that
$\|y_{1}\|<c^{\prime}/4$, but
$\sum_{k\in\upsilon_{1}}\left|b_{1,k}\right|^{2}=1$.

Assume that we have already constructed subsets
$\upsilon_{1}\supset\upsilon_{2}\supset\cdots\supset\upsilon_{p}$ with
$|\upsilon_{p}|\geq|\sigma|/2$, and vectors $\\{y_{\ell}\\}_{\ell=1}^{p}$ such
that $y_{\ell}=\sum_{k\in\upsilon_{\ell}\cup\sigma_{1}}b_{\ell,k}x_{k}$ and
$\|y_{\ell}\|<c^{\prime}/4$ and
$\sum_{k\in\upsilon_{\ell}}\left|b_{{\ell},k}\right|^{2}=1$, for
$1\leq\ell\leq p$. Consider the set

$\upsilon_{p+1}=\left\\{k\in\upsilon_{p}\ :\
\sum_{\ell=1}^{p}\left|b_{\ell,k}\right|^{2}<1\right\\}.$

If $|\upsilon_{p+1}|<|\sigma|/2$, then stop the procedure. On the other hand,
if $|\upsilon_{p+1}|\geq|\sigma|/2$, then there exists a vector

$y_{p+1}=\sum_{k\in\upsilon_{p+1}\cup\sigma_{1}}b_{p+1,k}x_{k}$

such that $\|y_{l+1}\|<c^{\prime}/4$ and
$\sum_{k\in\upsilon_{p+1}}\left|b_{j,k}\right|^{2}=1$.

By the pigeon-hole principle, this algorithm must eventually terminate, say
after $m$ steps. Then

$|\upsilon_{m+1}|<\frac{|\sigma|}{2}$

and thus, for $\ell\in\sigma\setminus\upsilon_{m+1}$, we have that

$\sum_{\ell=1}^{m}\left|b_{\ell,k}\right|^{2}\geq 1$

with the convention that $b_{\ell,k}=0$ for those $\ell$ and $k$ for which
$b_{\ell,k}$ has not been defined.

Hence

$\displaystyle m$
$\displaystyle=\sum_{\ell=1}^{m}\sum_{k\in\upsilon_{\ell}}\left|b_{\ell,k}\right|^{2}=\sum_{k\in\sigma}\sum_{\ell=1}^{m}\left|b_{\ell,k}\right|^{2}\geq\sum_{k\in\sigma\setminus\upsilon_{m+1}}\sum_{\ell=1}^{m}\left|b_{\ell,k}\right|^{2}\geq|\sigma\setminus\upsilon_{m+1}|$

and this implies that $m\geq|\sigma|/2$.

On the other hand, we have

$\displaystyle\frac{c^{\prime}\sqrt{m}}{4}>\left(\sum_{\ell=1}^{m}\left\|y_{\ell}\right\|^{2}\right)^{\frac{1}{2}}$
$\displaystyle=\left(\int\left\|\sum_{\ell=1}^{m}\varepsilon_{\ell}y_{\ell}\right\|^{2}d\varepsilon\right)^{\frac{1}{2}}$
$\displaystyle\geq\int\left\|\sum_{\ell=1}^{m}\varepsilon_{\ell}y_{\ell}\right\|d\varepsilon$
$\displaystyle=\int\left\|\sum_{k\in\sigma\cup\sigma_{1}}\left(\sum_{\ell=1}^{m}\varepsilon_{\ell}b_{\ell,k}\right)x_{k}\right\|d\varepsilon$
$\displaystyle\geq\frac{c^{\prime}}{\sqrt{\left|\sigma\right|}}\sum_{k\in\sigma}\int\left|\sum_{\ell=1}^{m}\varepsilon_{\ell}b_{\ell,k}\right|d\varepsilon$
(5)
$\displaystyle\geq\frac{c^{\prime}}{\sqrt{2\left|\sigma\right|}}\sum_{k\in\sigma}\left(\sum_{\ell=1}^{m}\left|b_{\ell,k}\right|^{2}\right)^{\frac{1}{2}}$
(6)

where (5) follows from Lemma 4.4, and (6) follows from Khintchine’s
inequality.

However, the inductive construction implies

$\displaystyle\sum_{\ell=1}^{m}\left|b_{\ell,k}\right|^{2}\leq 2$ (7)

for all $k\in\sigma$. This is clear if $k\in\upsilon_{m+1}$ because of how we
construct $\upsilon_{m+1}$, while if
$k\in\left(\upsilon_{p}\setminus\upsilon_{p+1}\right)$ for some $1\leq p\leq
m$, we have that

$\sum_{\ell=1}^{m}\left|b_{\ell,k}\right|^{2}=\sum_{\ell=1}^{p-1}\left|b_{\ell,k}\right|^{2}+\left|b_{p,k}\right|^{2}<2.$

It follows from (6) and (7) that

$\displaystyle\cfrac{\sqrt{m\left|\sigma\right|}}{2}$
$\displaystyle>\sqrt{2}\sum_{k\in\sigma}\left(\sum_{\ell=1}^{m}\left|b_{\ell,k}\right|^{2}\right)^{\frac{1}{2}}$
$\displaystyle\geq\sum_{k\in\sigma}\left(\sum_{\ell=1}^{m}\left|b_{\ell,k}\right|^{2}\right)^{\frac{1}{2}}\left(\sum_{\ell=1}^{m}\left|b_{\ell,k}\right|^{2}\right)^{\frac{1}{2}}$
$\displaystyle=\sum_{k\in\sigma}\sum_{\ell=1}^{m}\left|b_{\ell,k}\right|^{2}=m.$

Thus $m<|\sigma|/4$ which contradicts the fact that
$m\geq\left|\sigma\right|/2$. ∎

We now prove Theorem 4.1.

###### Proof of Theorem 4.1.

First apply Lemma 4.5 to obtain $\sigma_{2}$ that satisfies the desired
conclusion for $d_{2}=d_{1}/4$. We will next assume $|\sigma_{1}|\geq
d_{2}n\|A\|^{-2}$ and $d_{1}d_{2}n\|A\|^{-4}\geq 1$. Let $d_{3}=d_{2}^{2}$.
Choose $\tilde{\sigma}_{2}\subset\sigma_{2}$ with the largest possible
cardinality that satisfies the implicit bound
$|\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}_{2}|\leq
d_{1}(|\sigma_{1}|+|\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}_{2}|)/\|A\|^{2}$
(such sets exist; the empty set is one such example). Define
$n^{\prime}=|\sigma_{1}|+|\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}_{2}|$
and note that

$n^{\prime}\geq|\sigma_{1}|\geq d_{2}\frac{n}{\|A\|^{2}}.$

Since $|\sigma_{2}|\geq d_{2}n/\|A\|^{2}$, the set $\sigma_{2}$ is
sufficiently large to have allowed us to choose
$\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}_{2}$ such that

$\displaystyle|\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}_{2}|\geq\lfloor
d_{1}d_{2}n/\|A\|^{4}\rfloor$
$\displaystyle\geq(d_{1}d_{2}n/\|A\|^{4})/2\quad(\text{because
}d_{1}d_{2}n/\|A\|^{4}\geq 1)$ $\displaystyle\geq d_{3}n/\|A\|^{4}.$

Now we define $V=\langle
e_{j}:j\in\sigma_{1}\cup\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}_{2}\rangle$
and $A^{\prime}=A{|_{V}}$. An application of Lemma 4.5 to the matrix
$A^{\prime}$ and the set $\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}_{2}$,
yields a subset $\tau_{1}\subset\sigma_{1}$ such that

$|\tau_{1}|\geq d_{2}n^{\prime}/\|A^{\prime}\|^{2}\geq
d_{2}^{2}n/\|A\|^{4}\geq d_{3}n/\|A\|^{4},$

and for any choice of scalars
$\\{a_{j}\\}_{j\in\tau_{1}\cup\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}_{2}}$,
we have

$\displaystyle\norm{\sum_{j\in\tau_{1}\cup\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}_{2}}a_{j}Ae_{j}}\geq\frac{1}{16\sqrt{2}}\left(\sum_{j\in\tau_{1}}|a_{j}|^{2}\right)^{1/2}.$
(8)

As $\sigma_{2}$ was provided by Lemma 4.5 and $\tau_{1}\subset\sigma_{1}$,
$\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}_{2}\subset\sigma_{2}$ we also
have

$\displaystyle\norm{\sum_{j\in\tau_{1}\cup\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}_{2}}a_{j}Ae_{j}}\geq\frac{1}{16\sqrt{2}}\left(\sum_{j\in\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}_{2}}|a_{j}|^{2}\right)^{1/2}.$
(9)

Recall that for any two non-negative numbers $x$, $y$ we have
$\max\\{x,y\\}\geq(1/\sqrt{2})(x^{2}+y^{2})^{1/2}$, which in conjunction with
(8) and (9) yields the desired inequality. ∎

The above theorem guarantees the existence of subsets of columns that can be
“stitched” together without violating the minimal stretch property.

###  4.2. The proof of Theorem 1.4

Recall that an $m$-dimensional subspace $U$ of $\mathbb{R}^{n}$ is a
$\lambda$-quadratic convex combination of $U_{\sigma_{1}}$ and
$U_{\sigma_{2}}$, where $\lambda\in[0,1]$ and
$\sigma_{1}=\\{i_{1}<\cdots<i_{m}\\}$, $\sigma_{2}=\\{j_{1}<\cdots<j_{m}\\}$
are disjoint subsets of $\\{1,\ldots,n\\}$, such that $U$ is spanned by the
orthonormal sequence
$u_{k}=\lambda^{1/2}e_{i_{k}}+(1-\lambda)^{1/2}e_{j_{k}}$, $k=1,\ldots,m$.

In order to prove Theorem 1.4, we will combine Theorem 4.1 with a continuous
traversal between disjoint subsets of the basis via quadratic convex
combinations.

######  Lemma 4.6.

Let $A:[a,b]\to M_{n\times n}$ be a continuous matrix function and let
$\sigma_{1}$, $\sigma_{2}\subset\\{1,\dotsc,n\\}$ such that
$|\sigma_{1}|=|\sigma_{2}|$ and $\sigma_{1}\cap\sigma_{2}=\emptyset$. Let
$U=\langle e_{i}:i\in\sigma_{1}\cup\sigma_{2}\rangle$ and suppose there exists
a $c>0$ such that $m_{A(t)|_{U}}\geq c$ for all $t\in[a,b]$. Let
$\\{U(t)\\}_{t\in[a,b]}$ be such that, for each $t\in[a,b]$, $U(t)$ is the
$(1-(t-a)/(b-a))$-quadratic convex combination of $U_{\sigma_{1}}$ and
$U_{\sigma_{2}}$. Then $\\{U(t)\\}_{t\in[a,b]}$ is a continuous choice of
subspaces of $\mathbb{R}^{n}$ such that $U(a)=U_{\sigma_{1}}$,
$U(b)=U_{\sigma_{2}}$, and $m_{A(t)|_{U(t)}}\geq c$ for all $t\in[a,b]$.

###### Proof.

Write $\sigma_{1}=\\{i_{1}<\cdots<i_{m}\\}$,
$\sigma_{2}=\\{j_{1}<\cdots<j_{m}\\}$ so that for every $t\in[a,b]$,

$u_{k}(t)=\Big{(}1-\frac{t-a}{b-a}\Big{)}^{1/2}e_{i_{k}}+\Big{(}\frac{t-a}{b-a}\Big{)}^{1/2}e_{j_{k}},\;k=1,\ldots,m$

is an orthonormal basis for $U(t)$. As this is a continuous choice of
orthonormal basis, by Lemma 2.4, $\\{U(t)\\}_{t\in[a,b]}$ is a continuous
choice of subspaces and clearly $U(a)=U_{\sigma_{1}}$, $U(b)=U_{\sigma_{2}}$.

To complete the proof, for $t\in[a,b]$ note that

$\displaystyle m_{A(t)|_{U(t)}}$ $\displaystyle=\inf\\{\|A(t)x\|:x\in
U(t),\|x\|=1\\}$ $\displaystyle\geq\inf\\{\|A(t)x\|:x\in
U,\|x\|=1\\}\quad\text{(as $U(t)\subset U$)}$ $\displaystyle=m_{A(t)|_{U}}\geq
c.\qed$

We now have all the tools at our disposal to prove Theorem 1.4, which is
restated for convenience.

######  Theorem 4.7.

There exist universal constants $c=1/33$ and $d=2^{-15}/100$ such that for all
continuous matrix functions $A:\mathbb{R}\rightarrow M_{n\times n}$ with the
property that $\|A(t)e_{i}\|=1$ for all $t\in\mathbb{R}$ and $1\leq i\leq n$,
there exists a continuous family of $m$-dimensional subspaces
$\\{U(t)\\}_{t\in\mathbb{R}}$ of $\mathbb{R}^{n}$ with $m\geq dn/\Lambda^{4}$
where $\Lambda=\sup_{t\in\mathbb{R}}\|A(t)\|$ such that $\|A(t)v\|\geq c\|v\|$
for every $t\in\mathbb{R}$ and every $v\in U(t)$. Furthermore, each subspace
$U(t)$ is a quadratic convex combination of disjoint basis vectors.

###### Proof.

Note that $c=1/33$ is a perturbation of $1/32$ and $d=d_{3}$, which are from
the conclusion of Theorem 4.1 and Remark 4.2. If $d_{1}d_{2}n/\Lambda^{4}\leq
1$, then we may simply select $U(t)=\langle e_{1}\rangle$, for all
$t\in\mathbb{R}$. Hence, we may assume $d_{1}d_{2}n/\Lambda^{4}\geq 1$. Note
that

$\Big{\lceil}d_{2}\frac{n}{\Lambda^{2}}\Big{\rceil}=\Big{\lceil}\frac{1}{4}d_{1}\frac{n}{\Lambda^{2}}\Big{\rceil}\leq
d_{1}\frac{n}{\Lambda^{2}},$

since $d_{1}n/\Lambda^{2}\geq d_{1}d_{2}n/\Lambda^{4}\geq 1$. Furthermore,

$\displaystyle\Big{\lceil}d_{3}\frac{n}{\Lambda^{4}}\Big{\rceil}$
$\displaystyle\leq
d_{3}\frac{n}{\Lambda^{4}}+1\leq\frac{d_{2}}{2\Lambda^{2}}\Big{(}d_{2}\frac{n}{\Lambda^{2}}\Big{)}+\frac{d_{1}}{\Lambda^{2}}\Big{(}d_{2}\frac{n}{\Lambda^{2}}\Big{)}\leq
2d_{1}\Big{(}d_{2}\frac{n}{\Lambda^{2}}\Big{)}<\frac{1}{3}\Big{\lceil}d_{2}\frac{n}{\Lambda^{2}}\Big{\rceil}.$
(10)

By Lemma 3.4 we can find an increasing sequence of points
$(t_{i})_{i\in\mathbb{Z}}$ such that for all $i\in\mathbb{Z}$ and $t$ in
$[t_{i-1},t_{i+1}]$, $\|A(t_{i})-A(t)\|\leq\varepsilon=1/32-1/33$. Moreover,
by Theorem 4.1 applied to the matrix $A(t_{0})$ and the empty set, there
exists a subset $\sigma_{0}\subset\\{1,\ldots,n\\}$ with $|\sigma_{0}|=\lceil
d_{2}n/\Lambda^{2}\rceil\leq d_{1}n/\Lambda^{2}$ such that for any choice of
coefficients $\\{a_{j}\\}_{j\in\sigma_{0}}$ we have

$\Big{\|}\sum_{j\in\sigma_{0}}a_{j}A(t_{0})e_{j}\Big{\|}\geq\frac{1}{16\sqrt{2}}\Big{(}\sum_{j\in\sigma_{0}}|a_{j}|^{2}\Big{)}^{1/2}\geq\frac{1}{32}\Big{(}\sum_{j\in\sigma_{0}}|a_{j}|^{2}\Big{)}^{1/2}.$

By using $\|A(t_{0})-A(t)\|\leq\varepsilon=1/32-1/33$ we obtain that if
$U=\langle e_{j}:j\in\sigma_{0}\rangle$, then $m_{A(t)|_{U}}\geq 1/33$ for all
$t\in[t_{-1},t_{1}]$ (see the last part of Lemma 3.4).

We now focus on the interval $[t_{0},\infty)$ as a symmetric argument can be
applied to $(-\infty,t_{0}]$. In reality, an extra stitching needs to be
performed at $t_{0}$ to concatenate the two solutions. We omit this as it is
essentially contained in the ensuing argument.

Iteratively applying Theorem 4.1, for $i\geq 0$, we can obtain the sets with
following properties:

  1. (i)

$\sigma_{i+1}\subset\\{1,\ldots,n\\}\setminus\sigma_{i}$ with
$|\sigma_{i+1}|=\lceil d_{2}n/{\Lambda^{2}}\rceil\leq d_{1}n/{\Lambda^{2}}$
such that, for $U=\langle e_{j}:j\in\sigma_{i+1}\rangle$, we have
$m_{A(t)|_{U}}\geq 1/33$ for $t\in[t_{i},t_{i+2}]$.

  2. (ii)

$\stackon[-.5pt]{\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}}{\scriptscriptstyle\sim}_{i+1}\subset\sigma_{i+1}$
and $\stackon[.5pt]{\tau}{\scriptscriptstyle\sim}_{i}\subset\sigma_{i}$ with
$|\stackon[-.5pt]{\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}}{\scriptscriptstyle\sim}_{i+1}|=|\stackon[.5pt]{\tau}{\scriptscriptstyle\sim}_{i}|=\lceil
d_{3}n/\Lambda^{4}\rceil$ such that, for $U=\langle
e_{j}:j\in\stackon[.5pt]{\tau}{\scriptscriptstyle\sim}_{i}\cup\stackon[-.5pt]{\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}}{\scriptscriptstyle\sim}_{i+1}\rangle$,
we have $m_{A(t)|_{U}}\geq 1/33$ for $t\in[t_{i},t_{i+1}]$.

Indeed, suppose $\sigma_{i}$ has been constructed with $|\sigma_{i}|=\lceil
d_{2}n/{\Lambda^{2}}\rceil\leq d_{1}n/{\Lambda^{2}}$ such that, for $U=\langle
e_{j}:j\in\sigma_{i}\rangle$, we have $m_{A(t)|_{U}}\geq 1/33$ for
$t\in[t_{i},t_{i+2}]$. To obtain the sets $\sigma_{i+1}$,
$\stackon[.5pt]{\tau}{\scriptscriptstyle\sim}_{i}$ and
$\stackon[-.5pt]{\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}}{\scriptscriptstyle\sim}_{i+1}$,
we apply Theorem 4.1 to the matrix $A(t_{i+1})$ and the set $\sigma_{i}$.
Because $|\sigma_{i}|\leq d_{1}n/\Lambda^{2}$, we first get
$\sigma_{i+1}\subset\\{1,\ldots,n\\}$ with $|\sigma_{i+1}|\geq
d_{2}n/\Lambda^{2}$ (which, after truncating, we may assume satisfies
$|\sigma_{i+1}|=\lceil d_{2}n/\Lambda^{2}\rceil$) such that, for any choice of
coefficients $\\{a_{j}\\}_{j\in\sigma_{i}\cup\sigma_{i+1}}$,

$\Big{\|}\sum_{j\in\sigma_{i}\cup\sigma_{i+1}}a_{j}A(t_{i+1})e_{j}\Big{\|}\geq\frac{1}{32}\Big{(}\sum_{j\in\sigma_{i+1}}|a_{j}|^{2}\Big{)}^{1/2}.$

Using $\|A(t_{i+1})-A(t)\|\leq\varepsilon=1/32-1/33$ we obtain that, if
$U=\langle e_{j}:j\in\sigma_{i+1}\rangle$, then $m_{A(t)|_{U}}\geq 1/33$ for
all $t\in[t_{i},t_{i+2}]$. Since $|\sigma_{i}|=\lceil
d_{2}n/\Lambda^{2}\rceil\geq d_{2}n/\Lambda^{2}$, the second part of Theorem
4.1 yields $\stackon[.5pt]{\tau}{\scriptscriptstyle\sim}_{i}\subset\sigma_{i}$
and
$\stackon[-.5pt]{\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}}{\scriptscriptstyle\sim}_{i+1}\subset\sigma_{i+1}$
with
$|\stackon[.5pt]{\tau}{\scriptscriptstyle\sim}_{i}|,|\stackon[-.5pt]{\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}}{\scriptscriptstyle\sim}_{i+1}|\geq
d_{3}n/\Lambda^{4}$ (which after truncating we may assume
$|\stackon[.5pt]{\tau}{\scriptscriptstyle\sim}_{i}|=|\stackon[-.5pt]{\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}}{\scriptscriptstyle\sim}_{i+1}|=\lceil
d_{3}n/\Lambda^{4}\rceil$) such that for any choice of coefficients
$\\{a_{j}\\}_{j\in\stackon[.5pt]{\tau}{\scriptscriptstyle\sim}_{i}\cup\stackon[-.5pt]{\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}}{\scriptscriptstyle\sim}_{i+1}}$
we have

$\Big{\|}\sum_{j\in\stackon[.5pt]{\tau}{\scriptscriptstyle\sim}_{i}\cup\stackon[-.5pt]{\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}}{\scriptscriptstyle\sim}_{i+1}}a_{j}A(t_{i+1})e_{j}\Big{\|}\geq\frac{1}{32}\Big{(}\sum_{j\in\stackon[.5pt]{\tau}{\scriptscriptstyle\sim}_{i}\cup\stackon[-.5pt]{\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}}{\scriptscriptstyle\sim}_{i+1}}|a_{j}|^{2}\Big{)}^{1/2}.$

By using $\|A(t_{i+1})-A(t)\|\leq\varepsilon=1/32-1/33$ we obtain that, if
$U=\langle
e_{j}:j\in\stackon[.5pt]{\tau}{\scriptscriptstyle\sim}_{i}\cup\stackon[-.5pt]{\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}}{\scriptscriptstyle\sim}_{i+1}\rangle$,
then $m_{A(t)|_{U}}\geq 1/33$ for all $t\in[t_{i},t_{i+1}]$.

To construct our continuous collection of subspaces, consider the interval
$[t_{i},t_{i+1}]$. Using $\langle
e_{j}:j\in\stackon[.5pt]{\tau}{\scriptscriptstyle\sim}_{i}\rangle$ at $t_{i}$
and $\langle
e_{j}:j\in\stackon[-.5pt]{\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}}{\scriptscriptstyle\sim}_{i+1}\rangle$
at $t_{i+1}$, we will invoke Lemma 4.6 to construct a continuous collection of
subspaces $\\{U(t)\\}_{t\in[t_{i},t_{i+1}]}$, that has dimension $\lceil
d_{3}n/\Lambda^{4}\rceil$ for every $i\geq 0$. A diagram of the construction
has been provided below for the reader’s convenience:

$\sigma_{i}$$\sigma_{i}{}_{+}{}_{1}$$\sigma_{i}{}_{+}{}_{2}$$\tau_{i}$$\tau_{i}{}_{+}{}_{1}$$\sigma_{i}{}_{+}{}_{1}$$\sigma_{i}{}_{+}{}_{2}$$\widetilde{\
\ }$$\widetilde{\ \ }$$\widetilde{\ \ }$$\widetilde{\ \ }$$\widetilde{\ \
}$$\widetilde{\ \ }$$t_{i}$$t_{i+1}$$t_{i}{}_{+}{}_{2}$

As indicated on the diagram there is no reason to suppose
$\stackon[.5pt]{\tau}{\scriptscriptstyle\sim}_{i+1}=\stackon[-.5pt]{\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}}{\scriptscriptstyle\sim}_{i+1}$,
so we must devise a way to “stitch” together the collection of subspaces at
each endpoint, in order to construct a continuous collection of subspaces
$\\{U(t)\\}_{t\in\mathbb{R}}$. We choose an
$\eta_{i}\in(0,\frac{t_{i+1}-t_{i}}{2})$ and allow for another instance of
“stitching” in the interval $[t_{i+1}-\eta_{i},t_{i+1})$. This allows for us
to continuously switch between $[t_{i},t_{i+1}]$ and $[t_{i+1},t_{i+2}]$.

It is necessary to observe here that both
$\stackon[.5pt]{\tau}{\scriptscriptstyle\sim}_{i+1}$ and
$\stackon[-.5pt]{\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}}{\scriptscriptstyle\sim}_{i+1}$
are subsets of $\sigma_{i+1}$. Thus the minimal stretch property holds for
$U=\langle
e_{j}:j\in\stackon[.5pt]{\tau}{\scriptscriptstyle\sim}_{i+1}\cup\stackon[-.5pt]{\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}}{\scriptscriptstyle\sim}_{i+1}\rangle.$
We would like to switch from $\langle
e_{j}:j\in\stackon[-.5pt]{\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}}{\scriptscriptstyle\sim}_{i+1}\rangle$
at $t_{i-1}-\eta_{i}$ to $\langle
e_{j}:j\in\stackon[.5pt]{\tau}{\scriptscriptstyle\sim}_{i+1}\rangle$ at
$t_{i+1}$. To do this, it suffices to choose a new subset
$\xi_{i+1}\subset\sigma_{i+1}\setminus(\stackon[.5pt]{\tau}{\scriptscriptstyle\sim}_{i+1}\cup\stackon[-.5pt]{\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}}{\scriptscriptstyle\sim}_{i+1})$
with
$|\xi_{i+1}|=|\stackon[.5pt]{\tau}{\scriptscriptstyle\sim}_{i+1}|=|\stackon[-.5pt]{\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}}{\scriptscriptstyle\sim}_{i+1}|=\lceil
d_{3}n/\Lambda^{4}\rceil$. This is possible because

$|\stackon[.5pt]{\tau}{\scriptscriptstyle\sim}_{i+1}\cup\stackon[-.5pt]{\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}}{\scriptscriptstyle\sim}_{i+1}|\leq
2\Big{\lceil}d_{3}\frac{n}{\Lambda^{4}}\Big{\rceil}<\frac{2}{3}\Big{\lceil}d_{2}\frac{n}{\Lambda^{2}}\Big{\rceil}=\frac{2}{3}|\sigma_{i+1}|\quad\text{(by
\eqref{onesixth}).}$

We can now switch between the following subspaces for each $[t_{i},t_{i+1}]$:

$\displaystyle\text{At }t_{i}$ $\displaystyle:\text{Begin with
}U(t_{i})=\langle
e_{j}:j\in\stackon[.5pt]{\tau}{\scriptscriptstyle\sim}_{i}\rangle.$
$\displaystyle\text{At }t_{i+1}-\eta_{i}$ $\displaystyle:\text{Switch to
}U(t_{i+1}-\eta_{i})=\langle
e_{j}:j\in\stackon[-.5pt]{\stackon[.5pt]{\sigma}{\scriptscriptstyle\sim}}{\scriptscriptstyle\sim}_{i+1}\rangle\text{
using Lemma \ref{columnswitch}.}$ $\displaystyle\text{At }t_{i+1}-\eta_{i}/2$
$\displaystyle:\text{Switch to }U(t_{i+1}-\eta_{i}/2)=\langle
e_{j}:j\in\xi_{i}\rangle\text{ using Lemma \ref{columnswitch}.}$
$\displaystyle\text{At }t_{i+1}$ $\displaystyle:\text{Switch to
}U(t_{i+1})=\langle
e_{j}:j\in\stackon[.5pt]{\tau}{\scriptscriptstyle\sim}_{i+1}\rangle\text{
using Lemma \ref{columnswitch}.}\qed$

## Acknowledgements

The fourth and fifth authors are greatly indebted to Professors Alfonso
Gracia-Saz (1976-2021) and Inder Bir Passi (1939-2021), without whose
unfaltering support and encouragement the authors would never have considered
continued studies in mathematics and to whom far more is owed than can be
expressed. This paper is dedicated to their memories.

## References

  * [1] J. Anderson.  Extensions, restrictions, and representations of states on $C^{\ast}$-algebras.  Trans. Amer. Math. Soc., 249(2):303–329, 1979.
  * [2] D. Andrew, A.  Perturbations of Schauder bases in the spaces $C(K)$ and $L^{p}$, $p>1$.  Studia Math., 65(3):287–298, 1979.
  * [3] G. Bennett.  Upper bounds on the moments and probability inequalities for the sum of independent, bounded random variables.  Biometrika, 52:559–569, 1965.
  * [4] J. Bourgain and L. Tzafriri.  Invertibility of “large” submatrices with applications to the geometry of Banach spaces and harmonic analysis.  Israel J. Math., 57(2):137–224, 1987.
  * [5] J. Bourgain and L. Tzafriri.  Restricted invertibility of matrices and applications.  In Analysis at Urbana, Vol. II (Urbana, IL, 1986–1987), volume 138 of London Math. Soc. Lecture Note Ser., pages 61–107. Cambridge Univ. Press, Cambridge, 1989.
  * [6] J. Bourgain and L. Tzafriri.  On a problem of Kadison and Singer.  J. Reine Angew. Math., 420:1–43, 1991.
  * [7] P. G. Casazza and J. C. Tremain.  Revisiting the Bourgain-Tzafriri restricted invertibility theorem.  Oper. Matrices, 3(1):97–110, 2009.
  * [8] Y. Dai, A. Hore, S Jiao, T. Lan, and P. Motakis.  Continuous factorization of the identity matrix.  Involve, 13(1):149–164, 2020.
  * [9] R. V. Kadison and I. M. Singer.  Extensions of pure states.  Amer. J. Math., 81:383–400, 1959.
  * [10] N. J. Laustsen, R. Lechner, and P. F. X. Müller.  Factorization of the identity through operators with large diagonal.  J. Funct. Anal., 275(11):3169–3207, 2018.
  * [11] R. Lechner.  Factorization in mixed norm Hardy and BMO spaces.  Studia Math., 242(3):231–265, 2018.
  * [12] R. Lechner, P. Motakis, P. F. X. Müller, and Th. Schlumprecht.  Strategically reproducible bases and the factorization property.  Israel J. Math., 238(1):13–60, 2020.
  * [13] R. Lechner, P. Motakis, P. F. X. Müller, and Th. Schlumprecht.  The factorisation property of $\ell^{\infty}(X_{k})$.  Math. Proc. Cambridge Philos. Soc., 171(2):421–448, 2021.
  * [14] S. J. Leon.  Linear algebra with applications.  Macmillan, Inc., New York; Collier-Macmillan Publishers, London, 1980\.
  * [15] A. W. Marcus, D. A. Spielman, and N. Srivastava.  Interlacing families II: Mixed characteristic polynomials and the Kadison-Singer problem.  Ann. of Math. (2), 182(1):327–350, 2015.
  * [16] A. Naor and P. Youssef.  Restricted invertibility revisited.  In A journey through discrete mathematics, pages 657–691. Springer, Cham, 2017.
  * [17] N. Sauer.  On the density of families of sets.  J. Combinatorial Theory Ser. A, 13:145–147, 1972.
  * [18] D. A. Spielman and N. Srivastava.  An elementary proof of the restricted invertibility theorem.  Israel J. Math., 190:83–91, 2012.
  * [19] R. Vershynin.  John’s decompositions: selecting a large part.  Israel J. Math., 122:253–277, 2001.