Basis extension and change of basis

A basis must generate the whole space without redundant vectors. If a subspace is described by equations, finding such a list is not immediate. If some independent vectors have already been chosen, the basis must also retain them.

Throughout, scalars are real and $W\subseteq\mathbb R^n$. Selecting vectors outside the current span produces a basis; replacing suitable vectors in an existing basis makes it possible to retain a prescribed independent list. Once two ordered bases are available, their unique coefficients determine how coordinates convert between them.

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$.

Theorem

Existence of a basis for subspaces of $R^n$

Every nonzero subspace $W$ of $R^n$ has a basis. More precisely, there are vectors

$$u_1,\ldots,u_p\in W$$

such that $1\le p\le n$, the list is linearly independent, and

$$W=\operatorname{Span}\{u_1,\ldots,u_p\}.$$

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.

To justify preservation of independence, suppose a relation involving the new vector has a nonzero coefficient on it. Solving for that vector would put it in the old span, contrary to its selection. Its coefficient must therefore be zero; independence of the old list forces all remaining coefficients to vanish.

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 bound used here follows directly from homogeneous systems and does not require equality of basis sizes. A matrix of $r\gt n$ vectors in $\mathbb R^n$ has $r$ unknowns but at most $n$ pivots. A free unknown supplies a nonzero solution of the homogeneous system, hence a dependence relation. Thus selection cannot produce $n+1$ independent vectors. The bound controls termination; it is the stopping condition, namely that no vector of $W$ lies outside the current span, that proves spanning.

The zero subspace is the boundary case: its basis is the empty list. The empty linear combination is zero, so this list spans $\{0\}$ and has no nontrivial relation. The list containing the zero vector is dependent and is not a basis. Thus the dimension is zero, and no selection step is needed.

Worked example

A basis produced by the selection idea

Let

$$W=\left\{ \begin{bmatrix}x\\y\\z\end{bmatrix}\in R^3:x+y+z=0 \right\}.$$

Choose

$$u_1=\begin{bmatrix}1\\-1\\0\end{bmatrix}\in W.$$

This one vector does not span all of $W$, because

$$u_2=\begin{bmatrix}1\\0\\-1\end{bmatrix}\in W$$

is not a scalar multiple of $u_1$. Therefore $u_1,u_2$ are linearly independent.

Now every vector in $W$ can be written as

$$\begin{bmatrix}x\\y\\z\end{bmatrix} = x\begin{bmatrix}1\\0\\-1\end{bmatrix} +y\begin{bmatrix}0\\1\\-1\end{bmatrix},$$

or, using our chosen list,

$$\begin{bmatrix}x\\y\\z\end{bmatrix} = -y\begin{bmatrix}1\\-1\\0\end{bmatrix} +(x+y)\begin{bmatrix}1\\0\\-1\end{bmatrix},$$

because $z=-x-y$. Hence $u_1,u_2$ span $W$ and form a basis. This also gives $\dim(W)=2$.

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.

Theorem

Replacement theorem

Let $W$ be a subspace of $R^n$. Suppose

$$t_1,\ldots,t_q$$

is a basis for $W$, and suppose

$$u_1,\ldots,u_p\in W$$

are linearly independent. Then:

1. $p\le q$;
2. the vectors $u_1,\ldots,u_p$, together with some $q-p$ of the old basis vectors $t_1,\ldots,t_q$, form another basis for $W$.

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: all new vectors lie in $W$, and the displayed expression recovers the only deleted old vector. Independence needs its own argument. Suppose

$$\beta u+\sum_{i=2}^q\gamma_i t_i=0.$$

Substituting the expression for $u$ gives

$$\beta\alpha_1t_1+\sum_{i=2}^q(\beta\alpha_i+\gamma_i)t_i=0.$$

Independence of the old basis implies $\beta\alpha_1=0$ and $\beta\alpha_i+\gamma_i=0$ for every $i\ge2$. Since $\alpha_1\ne0$, first $\beta=0$, then every $\gamma_i=0$. This proves both basis conditions without appealing to an unproved counting rule. Any nonzero coefficient allows the corresponding old vector to be replaced; relabelling only simplifies notation.

The nonzero coefficient also identifies exactly which deletions are permitted. If $\alpha_j=0$, then $u$ already lies in the span of the old vectors other than $t_j$. Deleting $t_j$ leaves a list unable to recover it, since the old basis is independent. Thus a nonzero new vector does not permit an arbitrary deletion. When $q=1$, the argument simply says that a nonzero multiple of the single basis vector is another basis.

Why repeated replacement keeps every inserted vector

Suppose we have already constructed a basis consisting of $u_1,\ldots,u_k$ and $q-k$ remaining old vectors, denoted $r_1,\ldots,r_{q-k}$. Expand the next vector in this current basis:

$$u_{k+1}=\sum_{i=1}^k a_i u_i+\sum_{j=1}^{q-k}c_jr_j.$$

At least one coefficient $c_j$ on a remaining old vector is nonzero. Otherwise $u_{k+1}$ would belong to the span of $u_1,\ldots,u_k$, giving a nontrivial relation among the assumed independent new vectors. Apply the one-vector proof at that nonzero coefficient. It deletes $r_j$, retains every previously inserted $u_i$, and produces another basis of the same size. This is the invariant that permits the next step; merely knowing that some coefficient is nonzero would not protect the earlier insertions.

We have not assumed $p\le q$ to establish the count. If $p\gt q$, perform the first $q$ insertions. The list $u_1,\ldots,u_q$ then spans $W$, so $u_{q+1}\in W$ is a combination of that list. This contradicts independence. Hence $p\le q$, and after exactly $p$ steps the surviving $q-p$ old vectors complete the requested basis. When $p=q$, none remain. If $p=0$, keep the original basis; if $q=0$, then $W=\{0\}$ and an independent list in it must also be empty.

Worked example

Two replacements that preserve the first insertion

In $\mathbb R^3$, start with the standard basis $(e_1,e_2,e_3)$ and prescribe

$$u_1=e_1+e_2,\qquad u_2=e_1+e_3.$$

These vectors are independent: the second and third entries of $a u_1+b u_2=0$ give $a=b=0$. First replace $e_1$ by $u_1$, since $e_1=u_1-e_2$. The current basis is $(u_1,e_2,e_3)$. To insert the second vector, express it in this current basis, rather than reusing its original standard coordinates:

$$u_2=u_1-e_2+e_3,\qquad e_2=u_1-u_2+e_3.$$

The coefficient on the remaining old vector $e_2$ is $-1$, so replace $e_2$ and retain $u_1$. The result is $(u_1,u_2,e_3)$. Replacing $u_1$ instead would discard the first prescribed vector and fail our extension objective, even though a different valid basis could result.

Verify the final basis directly. For any $(a,b,c)^T$,

$$\begin{bmatrix}a\\b\\c\end{bmatrix} =b u_1+(a-b)u_2+(c-a+b)e_3.$$

The three entries on the right are respectively $a,b,c$, proving spanning. A relation $A u_1+B u_2+C e_3=0$ gives $(A+B,A,B+C)^T=0$; its second, first, and third entries successively force $A=B=C=0$. Thus the calculation verifies independence as well as recording which old vector survives.

Dimension consequences

The replacement theorem gives another proof of the equal-size result established in 6.5 Basis and dimension, with the additional construction of a basis containing any prescribed independent list.

Theorem

All bases of the same finite-dimensional subspace have the same size

If $B$ and $C$ are both bases for the same subspace $W\subseteq R^n$, then $B$ and $C$ contain the same number of vectors.

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.

Theorem

Counting rules inside a $q$-dimensional subspace

Let $\dim(W)=q$.

1. Any linearly independent list in $W$ has at most $q$ vectors.
2. Any list of more than $q$ vectors in $W$ is linearly dependent.
3. A linearly independent list in $W$ can be extended to a basis of $W$.
4. A spanning list for $W$ can be reduced to a basis of $W$ by deleting redundant vectors.

For extension, the replacement construction supplies the missing old basis vectors explicitly. For reduction, start with a finite spanning list. Whenever it is dependent, solve a nontrivial relation for a vector with nonzero coefficient and delete that vector. The span stays unchanged, and the list gets shorter, so the process ends with an independent spanning list. These procedures preserve different data: extension retains the given independent vectors, while reduction selects from the given generators.

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}.$$

Spanning gives existence of this expression. If two coefficient columns represented the same vector, subtracting the expressions would give a zero combination of the basis vectors. Independence forces the coefficient difference to be $0_p$, proving uniqueness. Notice that $x$ has $n$ ambient entries, while $[x]_B$ has $p$ entries. They are different kinds of columns even when their lengths happen to agree.

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 nonzero $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].$$

Theorem

Change-of-basis theorem

There is a unique invertible $p\times p$ matrix $S$ such that

$$\mathcal U=\mathcal V S.$$

The columns of $S$ are the coordinate vectors of the $u_j$'s in the ordered basis $V$. If

$$x=\mathcal U a=\mathcal V b,$$

then the coordinate vectors satisfy

$$b=Sa.$$

Proof

Independence replaces cancellation by a matrix inverse

The two basis matrices have size $n\times p$; neither needs to be square. The proof uses uniqueness of coefficients each time a basis matrix must be cancelled.

Construct the columns. For each $u_j\in W$, spanning by $V$ supplies a column $s_j\in\mathbb R^p$ with $\mathcal V s_j=u_j$. Independence makes this column unique. Assemble $S=[s_1\ \cdots\ s_p]$; the column rule for multiplication gives $\mathcal U=\mathcal V S$.

Construct the reverse matrix. Similarly, let $t_j=[v_j]_U$ and $T=[t_1\ \cdots\ t_p]$. Then $\mathcal V=\mathcal U T$, so

$$\mathcal U=\mathcal U TS,\qquad \mathcal V=\mathcal V ST.$$

For each standard coordinate column $e_j\in\mathbb R^p$, the first equality implies

$$\mathcal U(TS e_j-e_j)=0_n.$$

Independence of the columns of $\mathcal U$ forces $TS e_j-e_j=0_p$. This holds for every column, hence $TS=I_p$. The second equality and independence of the columns of $\mathcal V$ likewise give $ST=I_p$. Thus $T=S^{-1}$. No inverse of a rectangular basis matrix was used.

Prove uniqueness and the conversion rule. If also $\mathcal U=\mathcal V S'$, then each column of $S-S'$ satisfies $\mathcal V(s_j-s'_j)=0_n$. Independence forces $s_j-s'_j=0_p$, hence $S=S'$, even without assuming the competing matrix invertible. Finally,

$$\mathcal V b=x=\mathcal U a=\mathcal V Sa \quad\Longrightarrow\quad \mathcal V(b-Sa)=0_n.$$

The same independence argument gives $b-Sa=0_p$, which is the desired coordinate formula. Spanning supplied the conversion columns; independence supplied uniqueness, invertibility, and the rule for every vector.

The matrix $S$ converts the coordinate column from basis $U$ to basis $V$ while leaving the ambient vector $x$ fixed:

$$[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 $W\subsetneq\mathbb R^n$, its dimension $p$ is less than $n$. The $n\times p$ basis matrix $\mathcal V$ is therefore not square; find each column of $S$ by solving

$$\mathcal V s_j=u_j.$$

Worked example: changing coordinates in a plane

Worked example

One plane, two coordinate columns

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=\operatorname{Span}\{u_1,u_2\}$. In a relation $a u_1+b u_2=0$, the first entry gives $2a=0$ and the second then gives $-b=0$. Thus $U$ is a basis of $W$. Similarly $c v_1+d v_2=0$ has second and third entries $c=d=0$, so $V$ is independent. To check that these independent lists span the same plane, use both directions:

$$v_1=\tfrac12u_1-\tfrac12u_2,\qquad v_2=\tfrac12u_1+\tfrac12u_2.$$

These put the $v_j$ in $W$, and the following equalities put the $u_j$ in the span of the $v_j$. Mutual inclusion of the spans proves that $V$ is also a basis of $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.$$

Compute the ambient vector independently in both descriptions:

$$3\begin{bmatrix}2\\1\\1\end{bmatrix} +2\begin{bmatrix}0\\-1\\1\end{bmatrix} =\begin{bmatrix}6\\1\\5\end{bmatrix} =\begin{bmatrix}1\\1\\0\end{bmatrix} +5\begin{bmatrix}1\\0\\1\end{bmatrix}.$$

The reverse equalities above give

$$S^{-1}=\tfrac12\begin{bmatrix}1&1\\-1&1\end{bmatrix},\qquad S^{-1}\begin{bmatrix}1\\5\end{bmatrix} =\tfrac12\begin{bmatrix}6\\4\end{bmatrix} =\begin{bmatrix}3\\2\end{bmatrix}.$$

Multiplying the displayed matrices in either order gives $I_2$, checking the inverse directly. The actual vector has three entries and stays fixed; the two coordinate columns each have two entries because the plane has dimension two. This also checks the direction of conversion without relying on a memorized matrix formula.

Two coordinate descriptions of one vector

The following sequence records the same plane example. Read how $u_1=v_1+v_2$ and $u_2=-v_1+v_2$ supply the columns of $S$, and why $S$ converts $U$-coordinates into $V$-coordinates while the ambient vector stays fixed.

How to compute a change-of-basis matrix

To convert coordinates from $U$ to $V$:

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.

The hypotheses are useful computational checks. An inconsistent column system means the proposed source vector is outside the target span. Multiple solutions mean the target columns are dependent. For two actual bases of the same subspace, neither outcome can occur, even when there are more equations than coefficient unknowns.

Common mistakes

Common mistake

Using the inverse direction by accident

If $\mathcal U=\mathcal V S$, then $S$ sends $U$-coordinates to $V$-coordinates: $[x]_V=S[x]_U$. The inverse $S^{-1}$ sends $V$-coordinates back to $U$-coordinates.

Common mistake

Forgetting that the bases are ordered

The ordered basis $(b_1,b_2)$ and the ordered basis $(b_2,b_1)$ give different coordinate vectors. A change-of-basis matrix compares ordered bases, not just unordered sets.

Common mistake

Trying to invert a non-square basis matrix for a proper subspace

If $W$ is a plane inside $R^3$, a basis matrix has size $3\times2$, so it is not invertible as a square matrix. Solve $\mathcal V s_j=u_j$ column by column instead.

Quick checks

Checkpoint

If $\dim(W)=4$, can five vectors in $W$ be linearly independent?

Use the replacement-theorem counting rule.

Solution · Answer

No. In a 4-dimensional space, every linearly independent list has at most four vectors. Any five vectors in $W$ are linearly dependent.

Checkpoint

If $\mathcal U=\mathcal V S$, which coordinate vector is $S[x]_U$ equal to?

Track the equality $x=\mathcal U[x]_U=\mathcal V[x]_V$.

Solution · Answer

It is $[x]_V$. Since $x=\mathcal U[x]_U=\mathcal V S[x]_U$, uniqueness of coordinates in the $V$-basis gives $[x]_V=S[x]_U$.

Exercises

Checkpoint

Let $B=(b_1,b_2,b_3)$ be a basis for $W$, and let $u=b_1+2b_2-b_3$. Which old vector can be replaced immediately by $u$?

Look for a nonzero coefficient in the expression of $u$ using the old basis.

Solution · Guided solution

The coefficient of $b_1$ is $1$, which is nonzero. Therefore

$$b_1=u-2b_2+b_3.$$

So $u,b_2,b_3$ spans the same space as $b_1,b_2,b_3$. It is also independent, so $u$ can replace $b_1$. The nonzero coefficients of $b_2$ and $b_3$ would also allow replacement after relabelling.

Checkpoint

Use the example matrix $S=\begin{bmatrix}1&-1\\1&1\end{bmatrix}$ to convert $[x]_U=(4,-1)^T$ into $[x]_V$.

Multiply $S[x]_U$.

Solution · Guided solution

Compute

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

Thus $[x]_V=(5,3)^T$.

Read this first

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