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.

  • $\begingroup$ 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! $\endgroup$
    – diff2
    Apr 10 '18 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.