6.8 Basis extension and change of basis

The previous notes explain what a basis is and how dimension is used. This note adds the structural theorems that make the theory reliable.

There are three questions behind the results:

1. If a subspace is nonzero, must it have a basis?
2. If we already have a basis, when can we replace some old basis vectors by new independent vectors?
3. If two different bases describe the same subspace, how do their coordinate systems talk to each other?

The answers are not just formal background. They explain why dimension is well-defined, why independent lists can be extended, why spanning lists can be trimmed, and why diagonalization later is really a change of coordinates.

Why existence is not automatic

For familiar spaces such as $R^n$, it is easy to write down the standard basis. For an arbitrary subspace $W \subseteq R^n$, a basis is less obvious. The subspace might be given by equations, by a span, or by a condition such as $x_1+x_2+x_3=0$.

The first theorem says that the situation is still controlled.

The proof is a controlled selection process.

Start with any nonzero vector $u_1\in W$. If every vector in $W$ is already a multiple of $u_1$, then $\{u_1\}$ is a basis. If not, choose $u_2\in W$ that is not a multiple of $u_1$. Then $u_1,u_2$ are linearly independent.

Continue in the same way. At step j, if the current list $u_1,\ldots,u_j$ does not span $W$, choose a new vector $u_{j+1}\in W$ outside the current span. The new list stays linearly independent because the new vector was chosen not to be a linear combination of the old ones.

This process cannot go on forever: no more than n vectors in $R^n$ can be linearly independent. Therefore it must stop, and when it stops the chosen vectors span $W$. They are independent by construction, so they form a basis.

The replacement idea

The basis-existence proof grows an independent list. The replacement theorem explains the complementary operation: insert new independent vectors into an old basis while deleting the correct old vectors.

This theorem is the precise version of the slogan:

independent vectors can replace the same number of old basis vectors.

The proof begins with the one-vector case. Suppose $t_1,\ldots,t_q$ is a basis and

$$u=\alpha_1t_1+\cdots+\alpha_qt_q,\qquad u\ne 0.$$

At least one coefficient is nonzero. If $\alpha_1\ne 0$, then

$$t_1=\frac{1}{\alpha_1}u -\frac{\alpha_2}{\alpha_1}t_2-\cdots -\frac{\alpha_q}{\alpha_1}t_q.$$

So the list

$$u,t_2,\ldots,t_q$$

spans the same space as the old basis. It is also independent. If the first nonzero coefficient is not $\alpha_1$, relabel the old basis vectors and do the same argument.

The full replacement theorem repeats this one-vector replacement step. Each new independent vector replaces one old basis vector, and independence prevents the process from getting stuck.

Dimension consequences

The replacement theorem gives the rigorous reason why dimension works.

Indeed, apply the replacement theorem twice. If $B$ has p vectors and $C$ has q vectors, then the independence of $B$ inside a space with basis $C$ gives $p\le q$. Reversing the roles gives $q\le p$. Therefore $p=q$.

Several useful statements follow immediately.

These are not separate tricks. They all express the same fact: a basis is the exact size of a nonredundant spanning list.

Ordered bases and coordinate vectors

A basis as a set tells us which vectors are available. An ordered basis also fixes their order. Order matters for coordinates.

If

$$B=(b_1,\ldots,b_p)$$

is an ordered basis for $W$, then every $x\in W$ has a unique expression

$$x=\alpha_1b_1+\cdots+\alpha_pb_p.$$

The coordinate vector of x relative to $B$ is

$$[x]_B= \begin{bmatrix} \alpha_1\\ \vdots\\ \alpha_p \end{bmatrix}.$$

Changing the order of the basis changes the coordinate vector, even if the underlying basis vectors are the same.

Change-of-basis theorem

Now suppose the same p-dimensional subspace $W$ has two ordered bases:

$$U=(u_1,\ldots,u_p),\qquad V=(v_1,\ldots,v_p).$$

Write the basis matrices

$$\mathcal U=[u_1\ \cdots\ u_p], \qquad \mathcal V=[v_1\ \cdots\ v_p].$$

Read this carefully. The matrix $S$ does not move the vector x in the ambient space. It converts the coordinate column from the $U$-basis language into the $V$-basis language:

$$[x]_V=S[x]_U.$$

Because $S$ is invertible, the reverse conversion is

$$[x]_U=S^{-1}[x]_V.$$

If $W=R^n$, then $\mathcal U$ and $\mathcal V$ are square invertible matrices, and the formula becomes especially concrete:

$$S=\mathcal V^{-1}\mathcal U.$$

For a proper subspace, $\mathcal V$ is usually not square, so you should find each column of $S$ by solving

$$\mathcal V s_j=u_j.$$

Worked example: changing coordinates in a plane

Let

$$u_1=\begin{bmatrix}2\\1\\1\end{bmatrix}, \quad u_2=\begin{bmatrix}0\\-1\\1\end{bmatrix}, \quad v_1=\begin{bmatrix}1\\1\\0\end{bmatrix}, \quad v_2=\begin{bmatrix}1\\0\\1\end{bmatrix}.$$

Let $W=Span\{u_1,u_2\}$. One checks that both $(u_1,u_2)$ and $(v_1,v_2)$ are ordered bases for the same plane $W$.

The vector equalities

$$u_1=v_1+v_2,\qquad u_2=-v_1+v_2$$

combine into the matrix equality

$$\mathcal U=\mathcal V \begin{bmatrix} 1&-1\\ 1&1 \end{bmatrix}.$$

Therefore

$$S= \begin{bmatrix} 1&-1\\ 1&1 \end{bmatrix}$$

is the change-of-basis matrix from the ordered basis $U$ to the ordered basis $V$.

For example, if

$$[x]_U= \begin{bmatrix}3\\2\end{bmatrix},$$

then

$$[x]_V =S[x]_U = \begin{bmatrix} 1&-1\\ 1&1 \end{bmatrix} \begin{bmatrix}3\\2\end{bmatrix} = \begin{bmatrix}1\\5\end{bmatrix}.$$

So

$$x=3u_1+2u_2=v_1+5v_2.$$

The actual vector has not changed. Only its coordinates have changed.

How to compute a change-of-basis matrix

Use this workflow.

1. Decide the direction of conversion. If you want $[x]_V$ from $[x]_U$, you need $\mathcal U=\mathcal V S$.
2. For each $u_j$, solve $\mathcal V s_j=u_j$.
3. Put the solution columns together:

$$S=[s_1\ \cdots\ s_p].$$

If $\mathcal V$ is square and invertible, this is just

$$S=\mathcal V^{-1}\mathcal U.$$

If $\mathcal V$ is not square, solve the systems directly. The solution exists and is unique because the $v_j$'s form a basis for the same subspace.

Common mistakes

Quick checks

Exercises

Read this first

This note depends on 6.5 Basis and dimension and 6.4 Linear dependence and independence.