Time for a little intro to (finite-dimensional) linear algebra. This requires a few preliminary definitions. A **group** is a nonempty set with an operation satisfying

- Associativity: For all , .
- Existence of identity: There exists such that for all , .
- Existence of inverse elements: For each , there exists such that .

For convenience we will write for when the operation is assumed. If in addition

for all , we say that is an **abelian** group.

Now suppose is a non-empty set. If is an abelian group under operation (i.e. “addition”) with identity and is an abelian group under operation (i.e. “multiplication”) with identity (with ), we say that is a **field** provided that

- For all , .

Now, a nonempty set is a **vector space** over the field if is an abelian group under with identity and

- For all and , .
- For all , (where is again the multiplicative identity)
- For all and , .
- For all and , .

We call elements of **vectors** and elements of **scalars** I’ll skip the tedious (but important things!) such as proving that the additive/multiplicative identity in a group/field is unique.

On to a very fundamental definition: A finite set of vectors is said to be **linearly independent** if the equation

implies that . If a set of vectors is not linearly independent, it is said to be **linearly dependent**. From here on I will write “(in)dependent” for “linearly (in)dependent.” A basic (but important) consequence of this definition:

Theorem 1If is independent, then any subset of is independent.

*Proof:* Let and assume without loss of generality that for some (we can always renumber the elements in ). Then if

we have

where . By independence of , it follows that , so that is independent.

Another consequence:

Theorem 2If and , then is dependent.

*Proof:* Let . Then

which means that is dependent.

By a similar argument, we can see that if is dependent, then any is also dependent.

A new definition: If , the **span** of is the set of all linear combinations of elements of , i.e.

It is clear that for any , , for (if , we interpret this as the empty sum, which is again ). One basic result about span:

Theorem 3For any , . For any , .

*Proof:* If , then

If ,

Now for a theorem that is less trivial:

Theorem 4If is dependent, there is a set such that is independent, and .

*Proof:* We construct the set as follows. If , take . If not, then there is an element such that

with . Let . Then we can write

so that . Let . Continue this process until there are no more such vectors (this algorithm terminates in finite time since is a finite set). Then by construction, is independent, as no element in can be written as a linear combination of the other elements of . Further, and , so .

The next post will introduce the concepts of **subspace** and **basis**.