Homogeneous systems and null space

Proof of the finite real matrix product laws

Let $m,n,p,q$ be positive integers, let $A\in\mathbb R^{m\times n}$, $B\in\mathbb R^{n\times p}$, and $C\in\mathbb R^{p\times q}$. All the following arguments use the row-by-column definition and finite real sums. For any output position $(i,\ell)$,

$$\begin{aligned} ((AB)C)_{i\ell} &=\sum_{k=1}^{p}\left(\sum_{j=1}^{n}a_{ij}b_{jk}\right)c_{k\ell}\\ &=\sum_{j=1}^{n}a_{ij}\left(\sum_{k=1}^{p}b_{jk}c_{k\ell}\right) =(A(BC))_{i\ell}. \end{aligned}$$

The middle equality only reorders two finite sums and uses real distributivity. Both products are $m\times q$, so equality at every position proves associativity. No factor has changed its order.

For $D\in\mathbb R^{n\times p}$, the same definition gives

$$[A(B+D)]_{ik}=\sum_{j=1}^{n}a_{ij}(b_{jk}+d_{jk}) =(AB)_{ik}+(AD)_{ik}.$$

For $E\in\mathbb R^{m\times n}$, it gives

$$[(A+E)B]_{ik}=\sum_{j=1}^{n}(a_{ij}+e_{ij})b_{jk} =(AB)_{ik}+(EB)_{ik}.$$

Thus both distributive laws hold with the displayed matching sizes. For every real scalar $c$,

$$[(cA)B]_{ik}=\sum_j(ca_{ij})b_{jk} =c\sum_j a_{ij}b_{jk} =\sum_j a_{ij}(cb_{jk})=[A(cB)]_{ik},$$

proving $(cA)B=c(AB)=A(cB)$ by entrywise equality. In particular, for $x,y\in\mathbb R^n$ and real $s,t$,

$$[A(sx+ty)]_i=\sum_j a_{ij}(sx_j+ty_j) =s(Ax)_i+t(Ay)_i.$$

This proves the matrix-vector linearity used when comparing solutions of the same linear system. All identities concern compatible finite real matrices; they do not assert commutativity or cancellation of arbitrary matrix factors.

Finite elimination terminates and preserves the solution set

Let $A\in\mathbb R^{m\times n}$, $b\in\mathbb R^m$, with positive finite integers $m,n$. The permitted row operations are an exchange of two distinct rows, multiplication of a row by a nonzero scalar, and addition of a scalar multiple of one row to a different row. Their inverses are respectively the same exchange, multiplication by the reciprocal, and subtraction of that multiple. Applying an operation to the entire augmented array therefore preserves exactly the solutions of $Ax=b$: the new equations are consequences of the old, and its inverse gives the reverse implication. Each operation is also multiplication on the left by the result of applying it to the identity matrix, an invertible elementary matrix.

Scan the coefficient columns from left to right, maintaining the next unused row. If the current column has a nonzero entry in an unused row, exchange that row into the next position, divide by its nonzero pivot, and subtract multiples of it from every other row to clear that column. Advance the unused-row index. If every unused entry in the column is zero, skip the column. Previously chosen pivot columns remain unit columns: the current unused rows have zeros in them, so the new pivot row and every subsequent subtraction preserve those zeros and earlier pivots. There are only $n$ column scans and at most $\min(m,n)$ pivots, each with finitely many row operations. Thus the algorithm terminates. At its end, the nonzero coefficient rows have increasing pivot columns and zeros below and above each pivot; any remaining coefficient row is zero. This proves the reduced echelon form used below, without assuming it will eventually appear.

Classification and the homogeneous freedom

Write $r$ for the number of pivots in the coefficient part. A zero coefficient row with a nonzero transformed right side is the impossible equation $0=c$, so the system has no solution. Otherwise assign arbitrary real values to all $n-r$ nonpivot variables. In each pivot row, its pivot variable equals the transformed right side minus the displayed linear combination of these free variables; no other pivot variable occurs. These formulas both construct a solution and recover every solution. If $r=n$ the solution is unique. If $r<n$, changing a free variable changes the vector, giving infinitely many solutions.

For $Az=0$ the free variables can all be zero, giving the zero solution. If $r<n$, set one free variable to one and the others to zero, and use the pivot formulas. This constructs a nonzero homogeneous solution. If $r=n$, the formulas force every homogeneous variable to zero. For a consistent system, fixing one solution $x_p$, subtraction proves that every solution has the form $x_p+z$ with $Az=0$, and substitution proves the converse.

For square $A$, if every column has a pivot, the coefficient form is $I$. The product $E$ of the finitely many elementary matrices satisfies $EA=I$. Since $E$ is invertible, $A=E^{-1}$ and therefore also $AE=I$: $E$ is a two-sided inverse. If a pivot is missing, the nonzero homogeneous solution constructed above rules out any inverse. This also justifies applying the same row operations to $[A\mid I]$ to obtain $[I\mid A^{-1}]$ in the invertible case.

A vector space is a set with addition and scalar multiplication satisfying the usual abelian-group and distributive axioms over a field $F$. Columns are one model. Polynomials of degree at most $d$, denoted $P_d(F)$, and linear maps between spaces are others. The zero polynomial is included in $P_d(F)$ although its degree is not ordinarily defined.

A subspace contains zero and is closed under sums and scalar multiples. A list spans if every vector is a linear combination of its entries; it is independent if only the zero coefficients give zero. A basis is both. A finite spanning list can be reduced to a basis by deleting dependent entries; an independent list can be extended to a basis by adding vectors outside its span until the given finite spanning list is spanned.

Exchange lemma. An independent list of $r$ vectors in the span of $s$ vectors has $r\le s$. To see this, express the first independent vector in the spanning list, use a nonzero coefficient to replace one spanning vector by it, and repeat. At each stage independence ensures the next independent vector has a nonzero coefficient on an as-yet unreplaced spanning vector. There must be at least $r$ such slots. Comparing two bases in both directions proves that their lengths agree; this common length is $\dim V$.

Consequently, in dimension $n$, any $n$ independent vectors form a basis, as do any $n$ spanning vectors. Counting a list is useful only after its independence or spanning has been justified.

Finite basis existence and extension, without a counting assumption

Let $V$ be a real vector space supplied with a finite spanning list $t_1,\ldots,t_N$. First prove that every independent list $u_1,\ldots,u_k$ has length at most $N$. After $j$ insertions, maintain a spanning list consisting of $u_1,\ldots,u_j$ and $N-j$ surviving old vectors. Expand $u_{j+1}$ in this list. Some coefficient on a surviving old vector is nonzero; otherwise $u_{j+1}$ would be in the span of the earlier $u_i$, contradicting independence. Solve for that old vector and replace it by $u_{j+1}$. The new list spans the same space and keeps every earlier insertion. If $k>N$, after $N$ steps the first $N$ independent vectors already span $V$, contradicting independence of $u_{N+1}$. This proves the bound, including $N=0$.

Every subspace $W$ has a finite basis. Start with the empty independent list. If its current span is not $W$, choose one vector of $W$ outside that span. A relation with nonzero coefficient on the new vector would express it in the old span, so the enlarged list remains independent. The proved bound permits at most $N$ additions; therefore the process stops with an independent spanning list for $W$. If $W=\{0\}$, it stops immediately with the empty basis. Starting instead with any given independent list in $W$ proves that list extends to a basis of $W$. Only a bounded finite selection is used. Finally, if two bases have sizes $p,q$, use each as the finite spanning list in the bound to obtain $p\le q$ and $q\le p$. Thus basis size, called dimension, is well-defined. This supplies the existence, extension and dimension facts used in rank–nullity.

A map $T:V\to W$ is linear if $T(\alpha v+\beta u)=\alpha Tv+\beta Tu$. Its kernel and image are subspaces. Choose a basis $k_1,\ldots,k_r$ of $\ker T$ and extend to a basis with $v_1,\ldots,v_s$. Then $Tv_1,\ldots,Tv_s$ form a basis of $\operatorname{im}T$: spanning follows by expanding any input; a dependence among these images places the corresponding input combination in the kernel, and independence of the extended basis makes all coefficients zero. Thus

$$\dim V=\dim\ker T+\dim\operatorname{im}T.$$

This is rank–nullity. In equal finite dimensions, injectivity and surjectivity are equivalent, but the equivalence can fail in infinite-dimensional spaces.

If $x$ and $x_p$ solve the same system $Ax=b$, their difference satisfies $A(x-x_p)=b-b=0$. Thus a question about all solutions leads to a homogeneous system: which changes to one solution leave the right-hand side unchanged? The null space collects precisely those changes.

Why homogeneous systems are special

Definition

Homogeneous system

A homogeneous linear system is a linear system of the form

$$Ax = 0.$$

Its trivial solution is the zero vector $x = 0$.

Since $A0=0$, a homogeneous system is always consistent. The remaining question is whether it has any nonzero solutions.

The null space collects all homogeneous solutions

Definition

Null space

For a real $m\times n$ matrix $A$, the null space of $A$ is

$$N(A) = \{x\in\mathbb R^n : Ax = 0_m\}.$$

So $N(A)$ is exactly the solution set of the homogeneous system $Ax = 0$.

The input vectors lie in $\mathbb R^n$, while their outputs lie in $\mathbb R^m$. Membership in $N(A)$ asks whether the output is the zero vector.

Worked example

Membership in the null space is a direct test

Let

$$A = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix}, \qquad x = \begin{bmatrix} 1 \\ -1 \\ 1 \end{bmatrix}, \qquad z = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}.$$

Then

$$Ax = \begin{bmatrix} 0 \\ 0 \end{bmatrix}, \qquad Az = \begin{bmatrix} 1 \\ 0 \end{bmatrix}.$$

So $x \in N(A)$ but $z \notin N(A)$. This is the practical meaning of the definition: to test membership in $N(A)$, compute $Ax$ and check whether the result is exactly the zero vector.

Row reduction tells you the shape of the null space

To find $N(A)$, you solve $Ax = 0$ by reducing the augmented system $[A \mid 0]$. The pivots tell you which variables are determined; the free variables tell you how many directions of freedom remain.

Worked example

Solve a homogeneous system and describe the null space

Let

$$A = \begin{bmatrix} 1 & 2 & -1 \\ 2 & 4 & -2 \end{bmatrix}.$$

To solve $Ax = 0$, row-reduce:

$$\left[ \begin{array}{ccc|c} 1 & 2 & -1 & 0 \\ 2 & 4 & -2 & 0 \end{array} \right] \sim \left[ \begin{array}{ccc|c} 1 & 2 & -1 & 0 \\ 0 & 0 & 0 & 0 \end{array} \right].$$

So the equation is

$$x_1 + 2x_2 - x_3 = 0.$$

Take $x_2 = s$ and $x_3 = t$ as free variables. Then

$$x_1 = -2s + t.$$

Therefore

$$x = \begin{bmatrix} -2s + t \\ s \\ t \end{bmatrix} = s \begin{bmatrix} -2 \\ 1 \\ 0 \end{bmatrix} + t \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix}.$$

So

$$N(A) = \operatorname{Span} \left\{ \begin{bmatrix} -2 \\ 1 \\ 0 \end{bmatrix}, \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} \right\}.$$

Here $\operatorname{Span}$ means the set of all real linear combinations of the displayed vectors. The parameters $s$ and $t$ range independently, so the formula describes every homogeneous solution. The set notation is developed in 4.2 Set language and solution sets.

Why free variables force infinitely many homogeneous solutions

Theorem

A free variable creates infinitely many solutions

If the homogeneous system $Ax = 0$ has at least one free variable, then it has infinitely many solutions.

A free variable may be assigned any real value. Since that variable is itself a coordinate of the solution vector, changing its value changes the vector. A parameter chosen as an actual free coordinate cannot disappear from the full solution vector.

If a homogeneous system has more variables than pivot equations, at least one free variable remains. The same argument therefore gives infinitely many solutions.

Worked example

One free variable already produces a whole line of solutions

Suppose row reduction shows that

$$x_1 - 3x_2 = 0.$$

If $x_2 = t$, then $x_1 = 3t$, so every solution has the form

$$\begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = t \begin{bmatrix} 3 \\ 1 \end{bmatrix}, \qquad t \in R.$$

Different values of $t$ give different vectors, so the homogeneous system has infinitely many solutions, not just more than one.

Worked example

A trivial null space can also occur

Let

$$A = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}.$$

Then $Ax = 0$ is simply

$$x_1 = 0, \qquad x_2 = 0.$$

So the only solution is the zero vector, and therefore

$$N(A) = \{0\}.$$

This is the opposite extreme from the earlier example with free variables.

The null space is a subspace

Adding two homogeneous solutions or multiplying one by a scalar produces another homogeneous solution. Together with the zero solution, these are the closure properties that define a subspace of $\mathbb R^n$.

Theorem

The null space is closed under linear combinations

For any matrix $A$, the null space $N(A)$ is a subspace. In particular:

• $0 \in N(A)$,
• if $u, v \in N(A)$, then $u + v \in N(A)$,
• if $u \in N(A)$ and $c$ is a scalar, then $cu \in N(A)$.

Proof

Why the null space is a subspace

We already know $0 \in N(A)$ because $A0 = 0$.

Now take $u, v \in N(A)$. Then $Au = 0$ and $Av = 0$. By linearity,

$$A(u+v) = Au + Av = 0 + 0 = 0,$$

so $u+v \in N(A)$.

Likewise, if $u \in N(A)$ and $c$ is a scalar, then

$$A(cu) = c(Au) = c \cdot 0 = 0,$$

so $cu \in N(A)$.

The general definition and closure test are developed in 6.2 Subspaces. Here the equations above establish the properties needed for linear combinations of null-space vectors.

How to read a basis for the null space from RREF

A basis is a linearly independent spanning list. For $N(A)$, the free-coordinate description gives such a list directly: it generates every solution, and no nonzero choice of its coefficients gives the zero vector. The general notions of basis and dimension are developed in 6.5 Basis and dimension.

To construct this list:

1. row-reduce $A$,
2. identify pivot and free variables,
3. set one free variable to $1$ and the others to $0$,
4. solve for the pivot variables,
5. repeat once for each free variable.

These vectors really form a basis, not merely a candidate. Suppose there are $k$ free coordinates, and let $v_j$ be the solution obtained by setting the $j$th free coordinate to one and all other free coordinates to zero. For any $x\in N(A)$, let $t_1,\ldots,t_k$ be its free coordinates. Closure shows that $t_1v_1+\cdots+t_kv_k$ is a homogeneous solution. It has exactly the same free coordinates as $x$, and the reduced pivot equations determine all remaining coordinates uniquely. Thus it equals $x$, proving spanning.

For independence, suppose $c_1v_1+\cdots+c_kv_k=0$. Its $j$th free coordinate is precisely $c_j$, because only $v_j$ has a one there. Hence every $c_j=0$. This proves independence without an extra reduction. The vectors therefore form a basis and their number is the nullity. If there are no free variables, the null space is $\{0\}$ and its basis is the empty list, not the list containing the zero vector. This boundary agrees with nullity zero.

Nullity counts the free coordinates

The basis just constructed has one vector for each free coordinate. Its size is the dimension of $N(A)$, called the nullity of $A$. If an RREF of an $m\times n$ matrix has $r$ pivots, it has $n-r$ free variables, so

$$\operatorname{nullity}(A)=n-r.$$

The pivot count $r$ is called the rank. Its independence from the reduction path is justified in 5.2 RREF uniqueness and rank. In that notation, the count becomes

$$\operatorname{nullity}(A)=n-\operatorname{rank}(A).$$

Homogeneous solutions control nonhomogeneous ones

Once one solution $x_p$ of $Ax=b$ is known, the homogeneous solutions give all changes that preserve the right-hand side.

Theorem

Every solution is a particular solution plus a null-space vector

Suppose $x_p$ is one particular solution of $Ax = b$.

Then a vector $x$ solves $Ax = b$ if and only if

$$x = x_p + v$$

for some $v \in N(A)$.

Writing $S(A,b)$ for the solution set, the theorem states $S(A,b)=x_p+N(A)$.

Proof

Why the full solution set has the form $x_p + N(A)$

First suppose $x$ is any solution of $Ax = b$. Then

$$Ax = b \qquad \text{and} \qquad Ax_p = b.$$

Subtracting gives

$$A(x - x_p) = 0.$$

So $x - x_p \in N(A)$, which means $x = x_p + v$ for some $v \in N(A)$.

Conversely, if $v \in N(A)$, then $Av = 0$. Hence

$$A(x_p + v) = Ax_p + Av = b + 0 = b.$$

So every vector of the form $x_p + v$ is also a solution.

Concept lensGeometric

A fixed displacement of the null space

For a fixed particular solution $x_p$, the notation $x_p+N(A)$ means the set of all vectors $x_p+v$ with $v\in N(A)$. Addition by $x_p$ moves each point of the null space by the same displacement. It gives a one-to-one correspondence between homogeneous and nonhomogeneous solutions: its inverse subtracts $x_p$. The original proof establishes both that every displaced point works and that every solution is reached.

The chosen particular solution is not unique in general, but the displaced set is independent of that choice. If $x_q$ is another solution, then $h=x_q-x_p\in N(A)$. For every $v\in N(A)$, $x_q+v=x_p+(h+v)$, and closure gives $h+v\in N(A)$. This proves $x_q+N(A)\subseteq x_p+N(A)$; replacing $h$ by $-h$ proves the reverse inclusion. Different starting points along the solution set therefore produce the same family.

Consistency is essential: if there is no particular solution, this description cannot be started. For $b\ne0$, a consistent solution set contains no zero vector because $A0=0\ne b$. It is a translate of a subspace, called an affine subspace, but is not itself a vector subspace. Adding two of its solutions gives right-hand side $2b$, rather than $b$. The homogeneous case $b=0$ is exactly the case in which the solution set is the null space itself.

Worked example

Use one particular solution and two null-space directions

Suppose a system $Ax=b$ has one known solution

$$p= \begin{bmatrix} 1\\0\\-1\\0\\1\\0 \end{bmatrix},$$

and suppose the homogeneous system $Ax=0$ has solution directions

$$q_1= \begin{bmatrix} 2\\-3\\1\\0\\0\\0 \end{bmatrix}, \qquad q_2= \begin{bmatrix} -3\\1\\0\\-2\\2\\1 \end{bmatrix}.$$

If these two directions span $N(A)$, then every solution of $Ax=b$ has the form

$$x=p+s q_1+t q_2, \qquad s,t\in R.$$

Written out, this is

$$x= \begin{bmatrix} 1\\0\\-1\\0\\1\\0 \end{bmatrix} +s \begin{bmatrix} 2\\-3\\1\\0\\0\\0 \end{bmatrix} +t \begin{bmatrix} -3\\1\\0\\-2\\2\\1 \end{bmatrix}.$$

Here $Ap=b$, whereas $Aq_1=Aq_2=0$. The vector $p$ supplies a solution with the required output; the directions $q_1$ and $q_2$ allow the input to vary without changing that output. Their spanning condition is what guarantees that the formula reaches every solution.

A one-dimensional null space gives an affine line

Worked example

Describe all solutions as a translate of the null space

Suppose the system $Ax = b$ has one particular solution

$$x_p = \begin{bmatrix} 3 \\ 0 \\ 1 \end{bmatrix},$$

and suppose

$$N(A) = \operatorname{Span} \left\{ \begin{bmatrix} 1 \\ -1 \\ 0 \end{bmatrix} \right\}.$$

Then every solution has the form

$$x = \begin{bmatrix} 3 \\ 0 \\ 1 \end{bmatrix} + t \begin{bmatrix} 1 \\ -1 \\ 0 \end{bmatrix} = \begin{bmatrix} 3 + t \\ -t \\ 1 \end{bmatrix}, \qquad t \in R.$$

The null space gives the direction of freedom; the particular solution tells you where that family of solutions sits.

Scaling a solution usually changes its right-hand side. For a different system, the effect can be checked directly: if $Ap=b$, then

$$2A\left({3\over 2}p\right)=3Ap=3b.$$

So ${3\over 2}p$ is a solution of $2Ax=3b$. This is not because solution sets can be rescaled freely in every situation. It works here because the coefficient matrix and the right-hand side have both been scaled, and the calculation checks the claim directly.

Homogeneous solutions and column dependence

The null-space equation also explains when the columns of a matrix are dependent.

Let the columns of $A$ be $a_1, a_2, \ldots, a_n$. Then

$$Ax = 0$$

is the same as

$$x_1 a_1 + x_2 a_2 + \cdots + x_n a_n = 0.$$

So a nontrivial solution of the homogeneous system is exactly a nontrivial linear relation among the columns.

Worked example

A nontrivial null-space vector gives a dependence relation

Suppose

$$x = \begin{bmatrix} 1 \\ -2 \\ 1 \end{bmatrix} \in N(A).$$

Then

$$Ax = 0$$

means

$$1 \cdot a_1 - 2 \cdot a_2 + 1 \cdot a_3 = 0.$$

This is a nontrivial dependence relation among the columns of $A$.

What null space says about uniqueness

The structure theorem gives an immediate test.

• If $N(A) = \{0\}$, then a consistent system $Ax = b$ has exactly one solution.
• If $N(A)$ contains a nonzero vector, then every consistent system $Ax = b$ has infinitely many solutions, because you can add scalar multiples of that vector to a particular solution.

The consistency hypothesis is necessary: a zero null space guarantees at most one solution for each $b$, but does not by itself guarantee that a solution exists.

Multiplying equations can discard information

Row operations preserve a homogeneous solution set because they are reversible. A general matrix multiplier need not be reversible. The precise result keeps the direction of set inclusion visible.

Theorem

Null-space transport under left multiplication

Let $A$ be a real $m\times n$ matrix and $G$ a real $p\times m$ matrix. Then

$$N(A)\subseteq N(GA).$$

If $G$ is square and invertible, then $N(A)=N(GA)$.

Proof

Where invertibility is needed

Take any $x\in N(A)$. Then $Ax=0_m$, so $(GA)x=G(Ax)=G0_m=0_p$. Thus $x\in N(GA)$, proving the inclusion for arbitrary compatible $G$. Notice that both null spaces consist of vectors in $\mathbb R^n$, even when the matrices have different numbers of rows.

For the reverse inclusion, suppose $G$ is square and invertible, so $p=m$, and take $x\in N(GA)$. Then $GAx=0_p$. Multiplying by $G^{-1}$ gives $Ax=G^{-1}0_p=0_m$, so $x\in N(A)$. Only this second direction needs an inverse. Together the two inclusions prove equality.

Every row of $GA$ is a linear combination of rows of $A$. Consequently, the new equations are consequences of the old ones: every old solution satisfies them. If the combinations lose information, new solutions may appear. This is why arbitrary row combinations cannot replace elementary row operations without checking what has been preserved.

Worked example

A multiplier that loses a constraint

Take

$$A=\begin{bmatrix}1&0\\0&1\end{bmatrix},\qquad G=\begin{bmatrix}1&0\end{bmatrix}.$$

Then $GA=[1\ 0]$. The original equation $Ax=0$ imposes both $x_1=0$ and $x_2=0$, whereas the new equation only imposes $x_1=0$. Therefore

$$N(A)=\{0_2\},\qquad N(GA)=\left\{\begin{bmatrix}0\\t\end{bmatrix}:t\in\mathbb R\right\}.$$

The vector $(0,1)^T$ belongs to the second set and not the first, so the inclusion is strict. This verifies the lost condition directly rather than inferring it merely from the number of equations. Invertibility is a sufficient condition for equality, but not a necessary condition for each particular $A$: if $A$ is zero, both null spaces are all of $\mathbb R^n$, even for a noninvertible multiplier. The theorem must not be silently reversed.

Stacking equations means intersecting null spaces

There is another way to combine systems: keep all their equations together. Unlike taking selected row combinations, stacking retains each condition.

Theorem

The null space of a stacked matrix

Let $A$ be $m\times n$ and $B$ be $p\times n$, both real. For

$$C=\begin{bmatrix}A\\B\end{bmatrix},$$

we have $N(C)=N(A)\cap N(B)$. Here intersection means membership in both sets simultaneously. The row counts may differ; the column counts must agree.

Proof

Prove the stacked identity in both directions

First take $x\in N(C)$. By the block multiplication rule,

$$0_{m+p}=Cx=\begin{bmatrix}Ax\\Bx\end{bmatrix}.$$

Equality of the top $m$ and bottom $p$ entries gives $Ax=0_m$ and $Bx=0_p$. Thus $x$ belongs to each null space and hence to their intersection.

Conversely, take $x\in N(A)\cap N(B)$. Membership supplies both equations $Ax=0_m$ and $Bx=0_p$. Stacking their outputs gives

$$Cx=\begin{bmatrix}0_m\\0_p\end{bmatrix}=0_{m+p},$$

so $x\in N(C)$. Every membership step has now been checked in both directions, which proves equality of the sets.

For example, stacking $A=[1\ 0\ 0]$ and $B=[0\ 1\ 0]$ imposes both $x_1=0$ and $x_2=0$, leaving exactly the vectors $(0,0,t)^T$. Each individual null space is larger, but their intersection keeps only their common vectors. Repeated stacking similarly represents the intersection of finitely many homogeneous solution sets. The next note uses this identity to distinguish retaining every equation from retaining only a linear combination of them.

Common mistakes

Common mistake

The zero vector always belongs to the null space

Students sometimes think a homogeneous system can have no solution. That is impossible, because $x = 0$ always satisfies $Ax = 0$.

Common mistake

A particular solution is not the whole solution set

Finding one vector $x_p$ with $Ax_p = b$ is only the start. You still need to add the whole null space to describe every solution.

Common mistake

Do not confuse a particular solution with a direction

If $u$ and $v$ both solve $Ax=b$, then $v-u$ solves $Ax=0$. The vector $v-u$ is a direction inside the null space, not a new right-hand side.

Quick checks

Checkpoint

Why does $Ax = 0$ always have at least one solution?

Answer in one sentence.

Solution · Answer

Because the zero vector always satisfies $A0 = 0$.

Checkpoint

If $N(A) = \{0\}$ and $Ax = b$ is consistent, how many solutions does it have?

Use the theorem from this note.

Solution · Answer

Exactly one, because there is no nonzero null-space vector to add to a particular solution.

Checkpoint

If $Ax = 0$ has a free variable, can the solution set contain only two vectors?

Answer from the parameter form, not from a guess.

Solution · Answer

No. A free variable can vary through infinitely many scalar values, so it produces infinitely many solution vectors.

Checkpoint

Suppose $u$ and $v$ both solve $Ax=b$. What homogeneous system does $v-u$ solve?

Use one line of matrix algebra.

Solution · Answer

It solves $Ax=0$, because

$$A(v-u)=Av-Au=b-b=0.$$

Exercise

Checkpoint

Suppose $x_p$ solves $Ax = b$ and $u, v \in N(A)$. Why do $x_p + u$ and $x_p + v$ both solve $Ax = b$?

Write one line using linearity.

Solution · Guided solution

Because $Au = 0$ and $Av = 0$, we have

$$A(x_p + u) = Ax_p + Au = b + 0 = b,$$

and similarly

$$A(x_p + v) = Ax_p + Av = b + 0 = b.$$

So adding any null-space vector to a particular solution keeps you inside the solution set.

Related notes

This note builds on 2.3 Gaussian elimination and RREF and 2.4 Solution-set types. It prepares the way for 5.1 Invertible matrices and connects naturally with 6.2 Subspaces.