3
$\begingroup$

This question has been bothering me for some time now. All theorems in my linear algebra notes use ordered lists of vectors. For example consider the theorem here:

A spanning list of vectors may be reduced to a basis.

(Note: A basis is a linearly independent spanning set/list. A list is understood to be finite.)

Let $v_1....,v_n$ denote the spanning vectors in the statement. Then the proof proceeds like this: by a first step either keep or discard $v_1$ depending on whether $v_1=0$ or not. Subsequent steps assume $v_1....,v_{i-1}$ have been considered. Then $v_i$ is thrown away iff it is in the span of the already considered vectors.

Now here is my question: why does one generally use ordered lists in linear algebra? It appears to me that one can prove the statement without order as follows: Let $v_1,....v_n$ be a spanning set of $V$. If it is linearly independent we are done. If not, a $v_k$ can be written as a combintation of the others: $v_k = \sum_{i\neq k} a_i v_i$. Now proceed with the set $\{v_i\}_{i=k}$.

Similarly, I can prove statements like

The length of a linearly independent set is less equals the length of any spanning set (where $V$ is finite dimensional)

without ordered lists. Yet, the proofs in my notes all use ordered lists. Quick thinking even led me to the conclusion that the two approaches are in fact equivalent. But as this is all new to me, I suspect I can't rely on my thoughts.

Are my proofs likely to be wrong? If not, why is it good to use ordered lists?

$\endgroup$
  • $\begingroup$ I feel that either approach works. Some people may prefer the approach used in your notes because it gives an explicit algorithm for constructing such a basis. Also, it is relatively easier to convert the ordered lists approach to an argument that explicitly uses induction. $\endgroup$ – Adriano Aug 11 '13 at 9:42
  • $\begingroup$ See this article to understand how these two correspond each other. $\endgroup$ – Orat Aug 11 '13 at 10:09
3
$\begingroup$

It makes a difference in some ways. For example, you might want to state a theorem like "A list of vectors containing two repeated vectors is always linearly dependent". Then you cannot replace "list" by "set" because a set cannot contain 2 repeated vectors. Also, when you write a linear transformation between vector spaces as a matrix (in terms of given bases of the vector spaces), then the bases need to be ordered, because the rows/columns of the matrix are definitely ordered.

$\endgroup$
2
$\begingroup$

This question sheds some light on the way in which order matters and the way in which order does not matter.

In his answer posted before this one, Ted wrote:

"Also, when you write a linear transformation between vector spaces as a matrix (in terms of given bases of the vector spaces), then the bases need to be ordered, because the rows/columns of the matrix are definitely ordered."

To be sure, they are written in a particular order, and the order in which they are written matters.

Suppose I say a certain $3\times3$ matrix is the matrix of a certain linear transformation $\mathbb R^3\to\mathbb R^3$ with respect to the basis $\{v_1,v_2,v_3\}\subseteq\mathbb R^3$.

I could interchange the first two rows of that matrix and then the first two columns, and say that's the matrix with respect to the basis $\{v_2,v_1,v_3\}$.

The fact that the second item lists the vectors in a different order and puts the rows and columns of the matrix in a different order does not mean the information it conveys is different. In that sense, the order is not important. But is is important that rows of the matrix and columns of the matrix correspond in a certain way to vectors in the basis.

In some other types of problems, the actual order rather than just the correspondence may matter. It would not be correct to say that all problems are of that sort, so there is an actual difference between contexts in which the actual order matters and contexts in which the order of writing things is used to indicate the correspondence.

$\endgroup$

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.