# “Algorithmic” proofs in linear algebra

Although I am new to linear algebra, I want to study it with as much rigor as possible. After searching around, I picked up Halmos' Finite Dimensional Vector Spaces and Axler's Linear Algebra Done Right.

I've noticed that they state theorems which they prove by a method which I would describe as "algorithmic". For example, verbatim from Axler (although Halmos is very similar):

Theorem: In a finite-dimensional vector space, the length of every lin. ind. tuple is $\leq$ to the length of every spanning tuple of vectors.

Proof: Suppose that ($u_1$, ... $u_m$) is lin. ind. in $\mathcal{V}$ and ($w_1$, ... $w_n$) spans $\mathcal{V}$. We need to prove $m \leq n$. We do so through the multi-step process described below....

Step 1: The tuple $(w_1, ... w_n)$ spans $\mathcal{V}$, and thus adjoining any vector produces a linearly dependent tuple. In particular, the tuple $(u_1, w_1, ... w_n)$ is linearly independent. Thus, by the linear dependence lemma, we can remove one of the $w$'s so that the n-tuple B consisting of $u_1$ and the remaining $w$'s spans $\mathcal{V}$.

Step j: The n-tuple B from step $j-1$ spans $\mathcal{V}$, and thus adjoining any vector to it produces a linearly dependent tuple. In particular, the $(n+1)$-tuple obtained by adjoining $u_j$ to B, placing it just after $u_1,...u_{j-1},$ is linearly dependent. By the linear dependence lemma (2.4), one of the vectors in this tuple is in the span of the previous ones.... We can remove that $w$ from $B$ so that the new $n$-tuple $B$ consisting of $u_1, ... u_j$ and the remaining $w$'s spans $\mathcal{V}$.

After step $m$, we have added all the $u$'s and the process stops. If at any step we added a $u$ and had no more $w$'s to remove, then we would have a contradiction. Thus there must be at least as many $w$'s as $u$'s.

I take issue with the level of rigor of "algorithmic" proof. Although I think these proofs might be amenable to treatment by induction, I'm not sure how to carry it out. As they stand, although I get the intuition, they don't really convince me.

If I had to be precise about what bothers me, I'd say that the actual sets resulting from each step of the operation aren't stated explicitly, and I'm not sure how these sets are being ordered/indexed (they play fast and loose there).

(Disclosure: I am generally not thrilled with ...'s, unless I can see a clear way to come up with an argument which doesn't rely on imagining "what's going on in there", so dealing with about ten of these arguments at one sitting is irritating for me.)

Is there a way to make these arguments - in particular, this one - more precise?

-
This basic result is known as the Steinitz exchange lemma. If you google that you should find all sorts of proofs at any level of detail that you desire. –  Bill Dubuque Oct 15 '12 at 23:44

Prove by induction $k$ that for $0\le k\le m$ there is a tuple $(v_1,\ldots, v_n)$ such that
• $(v_1,\ldots, v_n)$ spans $\mathcal V$
• $k\le n$
• $v_i=u_i$ for $1\le i \le k$
• $v_i\in\{w_1,\ldots,w_n\}$ for $k<i\le m$.
For $k=0$ this is given. For $k=m$ it especially says $m\le n$. The induction step from $k\to k+1$ works just as described in the book.