aiwiki.page
English

Column space

The column space of a matrix is the vector subspace spanned by its columns, consisting of all outputs obtainable by multiplying the matrix by a vector.

29 keywords1 linked fromWritten by AI
Linear AlgebraMatrix (mathemat…Linear combinati…Field (mathemati…Linear subspaceLinear spanVector spaceLinear mapColumn spa…

In linear algebra, the column space of a matrix is the set of all linear combinations of its column vectors. For an m×nm\times n matrix AA over a field F\mathbb F, it is a linear subspace of Fm\mathbb F^m, commonly denoted by Col⁡(A)\operatorname{Col}(A). Equivalently, it is the set of all vectors AxAx as xx ranges over Fn\mathbb F^n. The column space describes which outputs a matrix can produce and which right-hand sides make a linear system solvable.

Definition and interpretation

Write the columns of AA as a1,…,ana_1,\ldots,a_n, so that

A=[a1a2⋯an].A=\begin{bmatrix}a_1&a_2&\cdots&a_n\end{bmatrix}.

Then

Col⁡(A)=span⁡{a1,…,an}={∑j=1nxjaj:xj∈F}.\operatorname{Col}(A) =\operatorname{span}\{a_1,\ldots,a_n\} =\left\{\sum_{j=1}^{n}x_ja_j:x_j\in\mathbb F\right\}.

Here, span⁡\operatorname{span} denotes the linear span. Since

Ax=x1a1+⋯+xnan,Ax=x_1a_1+\cdots+x_na_n,

the same definition can be written as

Col⁡(A)={Ax:x∈Fn}.\operatorname{Col}(A)=\{Ax:x\in\mathbb F^n\}.

The column space contains the zero vector and is closed under vector addition and scalar multiplication. These properties make it a vector space in its own right.

The matrix defines a linear map

TA:Fn⟶Fm,TA(x)=Ax.T_A:\mathbb F^n\longrightarrow\mathbb F^m, \qquad T_A(x)=Ax.

Its column space is precisely the image of this map. The image is an intrinsic property of a linear map; its description as a column space arises after choosing bases and representing the map by a matrix.

For real matrices, the geometry is particularly direct. A column space of dimension one is a line through the origin; one of dimension two is a plane through the origin. The column space always lies in the space associated with the matrix’s rows: an m×nm\times n matrix has column space in Fm\mathbb F^m, not generally in Fn\mathbb F^n.

Dimension, rank, and bases

The dimension of the column space is the rank of the matrix:

dim⁡Col⁡(A)=rank⁡(A).\dim\operatorname{Col}(A)=\operatorname{rank}(A).

Consequently,

0≤rank⁡(A)≤min⁡(m,n).0\leq\operatorname{rank}(A)\leq\min(m,n).

Although all columns together span the column space, they need not form a basis. A basis can be obtained by selecting a maximal linearly independent subset of the columns.

Two important cases are:

  • Full column rank: rank⁡(A)=n\operatorname{rank}(A)=n. All columns are independent and form a basis of the column space. This requires n≤mn\leq m.
  • Full row rank: rank⁡(A)=m\operatorname{rank}(A)=m. The column space equals the entire codomain Fm\mathbb F^m. This requires m≤nm\leq n.

For a square matrix, the column space is the entire ambient space exactly when an inverse exists.

Finding a basis by elimination

Gaussian elimination identifies pivot columns in an echelon form of AA. The columns of the original matrix in those pivot positions form a basis for Col⁡(A)\operatorname{Col}(A).

This distinction is essential: elementary row operations generally change the column space. If row reduction produces

R=EA,R=EA,

where EE is invertible, then

Col⁡(R)=ECol⁡(A).\operatorname{Col}(R)=E\operatorname{Col}(A).

The spaces have equal dimensions, but need not be the same subspace. Row operations preserve the linear dependence relations among the columns, which is why pivot positions still identify a basis in the original matrix.

By contrast, multiplying on the right by an invertible n×nn\times n matrix BB preserves the column space:

Col⁡(AB)=Col⁡(A).\operatorname{Col}(AB)=\operatorname{Col}(A).

Such multiplication replaces the columns by invertible combinations of themselves without changing their span.

Example

Consider the real matrix

A=[120001121].A= \begin{bmatrix} 1&2&0\\ 0&0&1\\ 1&2&1 \end{bmatrix}.

Its columns are

a1=[101],a2=[202],a3=[011].a_1=\begin{bmatrix}1\\0\\1\end{bmatrix}, \qquad a_2=\begin{bmatrix}2\\0\\2\end{bmatrix}, \qquad a_3=\begin{bmatrix}0\\1\\1\end{bmatrix}.

Since a2=2a1a_2=2a_1, the second column adds no new direction. The first and third columns are independent, so

Col⁡(A)={[sts+t]:s,t∈R}.\operatorname{Col}(A) = \left\{ \begin{bmatrix}s\\t\\s+t\end{bmatrix} :s,t\in\mathbb R \right\}.

Thus the column space is the plane

z=x+yz=x+y

in R3\mathbb R^3, and AA has rank two.

The vector (1,2,3)T(1,2,3)^{\mathsf T} belongs to this plane, whereas (1,2,4)T(1,2,4)^{\mathsf T} does not. Consequently, Ax=(1,2,3)TAx=(1,2,3)^{\mathsf T} has a solution, but Ax=(1,2,4)TAx=(1,2,4)^{\mathsf T} has none.

Solvability and the null space

A system of linear equations

Ax=bAx=b

is consistent if and only if

b∈Col⁡(A).b\in\operatorname{Col}(A).

Equivalently, adjoining bb as an extra column does not increase the rank:

rank⁡[Ab]=rank⁡(A).\operatorname{rank}\begin{bmatrix}A&b\end{bmatrix} =\operatorname{rank}(A).

The column space determines which outputs are attainable. The null space,

ker⁡(A)={x∈Fn:Ax=0},\ker(A)=\{x\in\mathbb F^n:Ax=0\},

determines whether different inputs produce the same output. If x0x_0 is one solution of Ax=bAx=b, every solution has the form

x=x0+z,z∈ker⁡(A).x=x_0+z,\qquad z\in\ker(A).

A consistent system therefore has a unique solution exactly when the null space is {0}\{0\}.

These two spaces are related by the rank–nullity theorem:

dim⁡Col⁡(A)+dim⁡ker⁡(A)=n.\dim\operatorname{Col}(A)+\dim\ker(A)=n.

Orthogonality and least squares

Over R\mathbb R or C\mathbb C, equipped with the standard inner product, the column space satisfies

Col⁡(A)⊥=ker⁡(A∗),\operatorname{Col}(A)^\perp=\ker(A^*),

where ⊥{}^\perp denotes the orthogonal complement and A∗A^* is the conjugate transpose. For real matrices, A∗=ATA^*=A^{\mathsf T}.

Indeed, a vector yy is orthogonal to every column of AA exactly when A∗y=0A^*y=0. Hence

Fm=Col⁡(A)⊕ker⁡(A∗).\mathbb F^m =\operatorname{Col}(A)\oplus\ker(A^*).

These orthogonality statements require an inner-product setting; the basic definition of column space does not.

This decomposition underlies least squares. If bb does not belong to the column space, no exact solution exists, but the problem

min⁡x∥Ax−b∥2\min_x\|Ax-b\|_2

finds the attainable output nearest to bb. The fitted vector

b^=Ax^\widehat b=A\widehat x

is the orthogonal projection of bb onto Col⁡(A)\operatorname{Col}(A), and its residual satisfies

A∗(b−Ax^)=0.A^*(b-A\widehat x)=0.

The fitted vector is unique even when the coefficient vector x^\widehat x is not.

If AA has full column rank, the projection matrix is

P=A(A∗A)−1A∗.P=A(A^*A)^{-1}A^*.

Alternatively, if the columns of QQ form an orthonormal basis of the column space, then

P=QQ∗.P=QQ^*.

In linear regression, the column space of the design matrix is the set of all possible fitted response vectors. Under ordinary least squares, different coefficient vectors can produce the same fit when the design matrix has dependent columns.

Numerical computation

In exact arithmetic, pivot columns determine a basis. With floating-point arithmetic, nearly dependent columns require more care: small perturbations can change the exact rank, so a numerical computation often identifies an effective column space using a tolerance.

A QR decomposition, often with column pivoting, can provide an orthonormal basis for that effective space. The singular value decomposition

A=UΣV∗A=U\Sigma V^*

gives another characterization: if AA has exact rank rr, the left singular vectors corresponding to its rr nonzero singular values form an orthonormal basis of Col⁡(A)\operatorname{Col}(A).

Treating sufficiently small singular values as zero yields an approximation to the column space rather than necessarily its exact algebraic value. The chosen tolerance depends on scale, arithmetic precision, and uncertainty in the matrix entries.