I wonder where the author used (I) in the above proof. (“Linear Algebra” by Ichiro Satake.)

algebra-precalculusintuitionlinear algebraproof-explanation

I am reading "Linear Algebra" (in Japanese) by Ichiro Satake.

Theorem 2:

The necessary and sufficient condition for $m$ $n$-dimensional vectors
$a_j = (a_{ij})$ ($1 \leq j \leq m$) to be linearly independent is that $m \leq n$ and there exists a non-zero $m$-th order determinant among the determinants of the $m$-th order matrices formed by selecting $m$ rows from the $n$ rows of the $(n, m)$ matrix $A = (a_{ij})$.

For a proof of Theorem 2, the author first defines the term "strongly linearly independent."

We define $m$ $n$-dimensional vectors $a_j = (a_{ij})$ ($1 \leq j \leq m$) to be "strongly linearly independent" if $m \leq n$ and there exists a non-zero $m$-th order determinant among the determinants of the $m$-th order matrices formed by selecting $m$ rows from the $n$ rows of the $(n, m)$ matrix $A = (a_{ij})$.

If $a_1, \ldots, a_m$ are strongly linearly independent, it is easy to see that they are linearly independent. The author proves that if $a_1, \ldots, a_m$ are linearly independent, then they are also strongly linearly independent.

To prove this, the author proved (I) and (II):

(I) If $a_1, \ldots, a_r$ are strongly linearly independent, then any subset of them is also strongly linearly independent.

(II) If $a_1, \ldots, a_r$ are strongly linearly independent, and $a_1, \ldots, a_r, a_{r+1}$ are not strongly linearly independent, then $a_{r+1}$ can be uniquely expressed as a linear combination of $a_1, \ldots, a_r$.

Then, the author wrote as follows:

Using (I) and (II), if $\{a_1, \ldots, a_m\}$ is any given set of $n$-dimensional vectors, by selecting the maximal subset $\{a_{i_1}, \ldots, a_{i_r}\}$ that is strongly linearly independent, any $a_i$ ($1 \leq i \leq m$) will be linearly dependent on $\{a_{i_k}\}$ ($1 \leq k \leq r$). Therefore, if $a_1, \ldots, a_m$ are linearly independent, then $r = m$. In other words, $a_1, \ldots, a_m$ are also strongly linearly independent. (End of Proof)

Where did the author use (I) in the above sentences?

enter image description here
enter image description here

Best Answer

It seems that (I) is used implicitly when using the words "selecting the maximal subset" there.
[[ We might have to see the whole argument to be certain , though I think this is where the author used (1) ]]

Certain Properties will not allow selecting "selecting the maximal subset" , like this Eg 1 :
Let Set $X=\{1,2,-3,4,-5,6,-7,-8\}$
We want Sub-Set $Y$ where the Sum is Positive.
We can check that $Y$ can be $\{1,2\}$ , $\{1,2,4\}$ , $\{1,-3,4\}$ , $\{-3,4,-5,6\}$ , where Sum is indeed Positive.
Let $Y=\{1,-3,4\}$ , with Positive Sum.
Yet , there are Sub-Sets of $Y$ whose Sum goes Negative too : $\{1,-3\}$ , $\{-3\}$
Hence , we can not talk about "selecting the maximal subset" here.

When we include new element $-5$ to $Y$ , then Sum goes Negative.
Yet , we can add two new elements $-5$ & $6$ to $Y$ , where Sum will remain Positive.
It reiterates that we can not talk about "selecting the maximal subset" here.

Consider this Eg 2 :
We have list of numbers $Z = [+5,-5,+5,-5,+5]$ where we want to pick out "contiguous" numbers with Positive Sum.
We have various ways to try that :

  • Only first $+5$
  • Only first three numbers $+5,-5,+5$
  • Only last $+5$
  • Only last three $+5,-5,+5$
  • $\cdots$

There is not much meaning to unique maximal subset here too.

[[ I am just making explanatory examples to show that maximal subset may or may not exist , the answer will stand without these examples too ]]

When the author talks about "selecting the maximal subset" with the Property "strongly linearly independent" , then (I) implicitly allows it.

When we have made the selection , it can not occur that we can add new element which makes it lose that Property yet we can add two new elements to retain that Property.
In other words , "selecting the maximal subset" will make sense here.

Related Question