# "Dimension inequality" preserving linear map for vector spaces

This is related to another question that I posted earlier. That one seems like stuck in dead space, have managed to obtained a partial solution to the problem, now stuck at the next stage (explained below): Vector space dimension after nonlinearly mapping spanning vectors

Let $\mathbb{R}^d \supset V = span(v_1, \dots, v_n)$ be a linear space spanned by not necessarily linearly independent elements $v_1, \dots, v_n$. Let each vector have the representation $v_i = \sum_{j=1}^d v_{ij}\mathbf{e}_j$ in the canonical basis.

Let $\mathbb{R}^d \supset W = span(w_1, \dots, w_n)$ be the linear space spanned by elements $w_i$ defined as, $$w_i = v_{ij}\mathbf{e}_j$$ where $j$ is the maximum index such that $v_{ij} \neq 0$.

The following can be shown: $$\dim V \geq \dim W.$$

The problem is as follows. Let $A$ be a $\bar{d}\times d$ matrix, $\bar{d} < d$, of full rank. Define the vector spaces $V'$ and $W'$ as, $$V' = span(Av_1, \dots, Av_n),\quad W' = span(Aw_1, \dots, Aw_n).$$

To prove: If none of the $v_i$ are in the nullspace of $A$, then $$\dim V' \geq \dim W'.$$

It seems like the claim should be true. Any hints on how a proof can be approached? Or a counterexample? Or if the sufficiency conditions are not enough, any idea on how I could tighten them?

Thanks very much!

Sketch of proof of $\dim V \geq \dim W$:

Assume that for both $v_i$ and $v_j$, the maximum index where $v_{ik} \neq 0$ and $v_{jk} \neq 0$ is the same, say $k_0$. Then $w_i = v_{ik_0}\mathbf{e}_{k_0}$ and $w_j = v_{jk_0}\mathbf{e}_{k_0}$ will span the same space, even if $v_{i}$ and $v_j$ do not. The dimension of $W$ is equal to the number of different maximal indices at which non-zero entries occur in the $v_i$s. This is clearly less than the dimension of $V$, as at least the same number of $v_i$s are linearly independent.

1. To properly prove $\dim V\ge\dim W$, we need to show that if $(w_i)_{i\in I}$ is linearly independent for an index set $I\subseteq\{1,2,\dots,n\}$, then so is $(v_i)_{i\in I}$.
By definition of $w_i$, they will be independent only if the corresponding maximal indices $j(i)$ are all different. Now suppose $\sum_{i\in I}\lambda_iv_i=0$, write it out in coordinates (or use a matrix), and conclude that all $\lambda_i=0$.
2. A counterexample: $$v_1:=\pmatrix{1\\1\\0},\ v_2:=\pmatrix{0\\0\\1}\ \implies\ w_1=\pmatrix{0\\1\\0},\ w_2=v_2$$ Take $A$ so that $v_1-v_2=\pmatrix{1\\1\\-1}$ spans its kernel, then $\dim V'=\dim\mathrm{span}(Av_1,Av_2)=1$ but $\dim W'=\dim\mathrm{span}(Aw_1,Aw_2)=2$.
For a specific example, $$A:=\pmatrix{1&-1&0\\0&1&1}\\ A(v_1\vert v_2)=\pmatrix{0&0\\1&1}\quad\quad A(w_1\vert w_2)=\pmatrix{-1&0\\1&1}$$
3. A sufficient condition would be that the nullspace of $A$ is disjoint to the whole $\mathrm{span}(v_1,\dots, v_n)=V$, so that $A$ restricted to $V$ is one-to-one.
• Thanks. +1 The sufficient condition that you mention is correct. Can it can be weakened as follows? If, for some set $I$, $A(\sum_{i\in I} a_i v_i) = 0$, then so is $A(\sum_{i\in I} a_i w_i)$. Any comments? Thanks! Apr 10 '18 at 20:32