IMC 2009 · Day 2 · P10

(a) We will prove the claim by constructing a suitable decomposition $T = Z_0 \oplus Z_1 \oplus \cdots$ and a corresponding decomposition of the space spanned by all columns of $T$ as $W_0 \oplus W_1 \oplus \cdots$, such that $\dim W_0 \leqslant n - 1$, $\dim W_1 \leqslant n - 2$, etc., from which the bound follows.

We first claim that, in every covering matrix space $S$, we can find an $A \in S$ with $\operatorname{rk} A \leqslant \dim S - 1$. Indeed, let $S_0 \subseteq S$ be some minimal covering matrix space. Let $s = \dim S_0$ and fix some subspace $S' \subset S_0$ of dimension $s - 1$. $S'$ is not covering by minimality of $S_0$, so that we can find an $u \in \mathbb{R}^p$ with $u \notin \bigcup_{B \in S', B \ne 0} \operatorname{Ker} B$. Let $V = S'(u)$; by the rank-nullity theorem, $\dim V = s - 1$. On the other hand, as $S_0$ is covering, we have that $Au = 0$ for some $A \in S_0 \setminus S'$. We claim that $\operatorname{Im} A \subset V$ (and therefore $\operatorname{rk}(A) \leqslant s - 1$).

For suppose that $Av \notin V$ for some $v \in \mathbb{R}^p$. For every $\alpha \in \mathbb{R}$, consider the map $f_\alpha : S_0 \to \mathbb{R}^m$ defined by $f_\alpha : (\tau + \beta A) \mapsto \tau(u + \alpha v) + \beta A v$, $\tau \in S'$, $\beta \in \mathbb{R}$. Note that $f_0$ is of rank $s = \dim S_0$ by our assumption, so that some $s \times s$ minor of the matrix of $f_0$ is non-zero. The corresponding minor of $f_\alpha$ is thus a nonzero polynomial of $\alpha$, so that it follows that $\operatorname{rk} f_\alpha = s$ for all but finitely many $\alpha$. For such an $\alpha \ne 0$, we have that $\operatorname{Ker} f_\alpha = \{0\}$ and thus $$0 \ne \tau(u + \alpha v) + \beta A v = (\tau + \alpha^{-1} \beta A)(u + \alpha v)$$ for all $\tau \in S'$, $\beta \in \mathbb{R}$ not both zero, so that $B(u + \alpha v) \ne 0$ for all nonzero $B \in S_0$, a contradiction.

Let now $T$ be a minimal covering matrix space, and write $\dim T = n$. We have shown that we can find an $A \in T$ such that $W_0 = \operatorname{Im} A$ satisfies $w_0 = \dim W_0 \leqslant n - 1$. Denote $Z_0 = \{ B \in T : \operatorname{Im} B \subset W_0 \}$; we know that $t_0 = \dim Z_0 \geqslant 1$. If $T = Z_0$, then $\delta(T) \leqslant n - 1$ and we are done. Else, write $T = Z_0 \oplus T_1$, also write $\mathbb{R}^m = W_0 \oplus V_1$ and let $\pi_1 : \mathbb{R}^m \to \mathbb{R}^m$ be the projection onto the $V_1$-component. We claim that $$T_1^{\sharp} = \{ \pi_1 \tau_1 : \tau_1 \in T_1 \}$$ is also a covering matrix space. Note here that $\pi_1^{\sharp} : T_1 \to T_1^{\sharp}$, $\tau_1 \mapsto (\pi_1 \tau_1)$ is an isomorphism. In particular we note that $\delta(T) = w_0 + \delta(T_1^{\sharp})$.

Suppose that $T_1^{\sharp}$ is not a covering matrix space, so we can find a $v_1 \in \mathbb{R}^p$ with $v_1 \notin \bigcup_{\tau_1 \in T_1, \tau_1 \ne 0} \operatorname{Ker}(\pi_1 \tau_1)$. On the other hand, by minimality of $T$ we can find a $u_1 \in \mathbb{R}^p$ with $u_1 \notin \bigcup_{\tau_0 \in Z_0, \tau_0 \ne 0} \operatorname{Ker} \tau_0$. The maps $g_\alpha : Z_0 \to V_0$, $\tau_0 \mapsto \tau_0 (u_1 + \alpha v_1)$ and $h_\beta : T_1 \to V_1$, $\tau_1 \mapsto \pi_1 (\tau_1 (v_1 + \beta u_1))$ have $\operatorname{rk} g_0 = t_0$ and $\operatorname{rk} h_0 = n - t_0$ and thus both $\operatorname{rk} g_\alpha = t_0$ and $\operatorname{rk} h_{\alpha^{-1}} = n - t_0$ for all but finitely many $\alpha \ne 0$ by the same argument as above. Pick such an $\alpha$ and suppose that $$(\tau_0 + \tau_1)(u_1 + \alpha v_1) = 0$$ for some $\tau_0 \in Z_0$, $\tau_1 \in T_1$. Applying $\pi_1$ to both sides we see that we can only have $\tau_1 = 0$, and then $\tau_0 = 0$ as well, a contradiction given that $T$ is a covering matrix space.

In fact, the exact same proof shows that, in general, if $T$ is a minimal covering matrix space, $\mathbb{R}^m = V_0 \oplus V_1$, $T_0 = \{ \tau \in T : \operatorname{Im} \tau \subset V_0 \}$, $T = T_0 \oplus T_1$, $\pi_1 : \mathbb{R}^m \to \mathbb{R}^m$ is the projection onto the $V_1$-component, and $T_1^{\sharp} = \{ \pi_1 \tau_1 : \tau_1 \in T_1 \}$, then $T_1^{\sharp}$ is a covering matrix space.

We can now repeat the process. We choose a $\pi_1 A_1 \in T_1^{\sharp}$ such that $W_1 = (\pi_1 A_1)(\mathbb{R}^p)$ has $w_1 = \dim W_1 \leqslant n - t_0 - 1 \leqslant n - 2$. We write $Z_1 = \{ \tau_1 \in T_1 : \operatorname{Im}(\pi_1 \tau_1) \subset W_1 \}$, $T_1 = Z_1 \oplus T_2$ (and so $T = (Z_0 \oplus Z_1) \oplus T_2$), $t_1 = \dim Z_1 \geqslant 1$, $V_1 = W_1 \oplus V_2$ (and so $\mathbb{R}^m = (W_0 \oplus W_1) \oplus V_2$), $\pi_2 : \mathbb{R}^m \to \mathbb{R}^m$ is the projection onto the $V_2$-component, and $T_2^{\sharp} = \{ \pi_2 \tau_2 : \tau_2 \in T_2 \}$, so that $T_2^{\sharp}$ is also a covering matrix space, etc.

We conclude that $$\delta(T) = w_0 + \delta(T_1^{\sharp}) = w_0 + w_1 + \delta(T_2^{\sharp}) = \cdots \leqslant (n-1) + (n-2) + \cdots \leqslant \binom{n}{2}.$$

(b) We consider $\binom{n}{2} \times n$ matrices whose rows are indexed by $\binom{n}{2}$ pairs $(i, j)$ of integers $1 \leqslant i < j \leqslant n$. For every $u = (u_1, u_2, \dots, u_n) \in \mathbb{R}^n$, consider the matrix $A(u)$ whose entries $(A(u))_{(i,j),k}$ with $1 \leqslant i < j \leqslant n$ and $1 \leqslant k \leqslant n$ are given by $$(A(u))_{(i,j),k} = \begin{cases} u_i, & k = j, \\ -u_j, & k = i, \\ 0, & \text{otherwise.} \end{cases}$$ It is immediate that $\operatorname{Ker} A(u) = \mathbb{R} \cdot u$ for every $u \ne 0$, so that $S = \{ A(u) : u \in \mathbb{R}^n \}$ is a covering matrix space, and in fact a minimal one.

On the other hand, for any $1 \leqslant i < j \leqslant n$, we have that $A(e_i)_{(i,j),j}$ is the $(i,j)$-th vector in the standard basis of $\mathbb{R}^{\binom{n}{2}}$, where $e_i$ denotes the $i$-th vector in the standard basis of $\mathbb{R}^n$. This means that $\delta(S) = \binom{n}{2}$, as required.

(for part a)

Let us denote $X = \mathbb{R}^p$, $Y = \mathbb{R}^m$. For each $x \in X$, denote by $\mu_x : T \to Y$ the evaluation map $\tau \mapsto \tau(x)$. As $T$ is a covering matrix space, $\ker \mu_x > 0$ for every $x \in X$. Let $U = \{ x \in X : \dim \ker \mu_x = 1 \}$.

Let $T_1$ be the span of the family of subspaces $\{ \ker \mu_x : x \in U \}$. We claim that $T_1 = T$. For suppose the contrary, and let $T' \subset T$ be a subspace of $T$ of dimension $n - 1$ such that $T_1 \subseteq T'$. This implies that $T'$ is a covering matrix space. Indeed, for $x \in U$, $(\ker \mu_x) \cap T' = \ker \mu_x \ne 0$, while for $x \notin U$ we have $\dim \mu_x \ge 2$, so that $(\ker \mu_x) \cap T' \ne 0$ by computing dimensions. However, this is a contradiction as $T$ is minimal.

Now we may choose $x_1, x_2, \dots, x_n \in U$ and $\tau_1, \tau_2, \dots, \tau_n \in T$ in such a way that $\ker \mu_{x_i} = \mathbb{R} \tau_i$ and $\tau_i$ form a basis of $T$. Let us complete $x_1, \dots, x_n$ to a sequence $x_1, \dots, x_d$ which spans $X$. Put $y_{ij} = \tau_i(x_j)$. It is clear that $y_{ij}$ span the vector space generated by the columns of all matrices in $T$. We claim that the subset $\{ y_{ij} : i > j \}$ is enough to span this space, which clearly implies that $\delta(T) \leqslant \binom{n}{2}$.

We have $y_{ii} = 0$. So it is enough to show that every $y_{ij}$ with $i < j$ can be expressed as a linear combination of $y_{ki}$, $k = 1, \dots, n$. This follows from the following lemma:

Lemma. For every $x_0 \in U$, $0 \ne \tau_0 \in \ker \mu_{x_0}$ and $x \in X$, there exists a $\tau \in T$ such that $\tau_0(x) = \tau(x_0)$.

Proof. The operator $\mu_{x_0}$ has rank $n - 1$, which implies that for small $\varepsilon$ the operator $\mu_{x_0 + \varepsilon x}$ also has rank $n - 1$. Therefore one can produce a rational function $\tau(\varepsilon)$ with values in $T$ such that $m_{x_0 + \varepsilon x}(\tau(\varepsilon)) = 0$.

Taking the derivative at $\varepsilon = 0$ gives $\mu_{x_0}(\tau_0) + \mu_x(\tau'(0)) = 0$.

Therefore $\tau = -\tau'(0)$ satisfies the desired property.

Remark. Lemma in solution 2 is the same as the claim $\operatorname{Im} A \subset V$ at the beginning of solution 1, but the proof given here is different. It can be shown that all minimal covering spaces $T$ with $\dim T = \binom{n}{2}$

are essentially the ones described in our example.