How to find dimension of null space of a given matrix? Let $A$ be a $5×4$ matrix with real entries such that the space of all solutions of linear system $AX^t = \begin{pmatrix}{1,2,3,4,5}\end{pmatrix}$ is given by $\{[1+2s,2+3s,3+4s,4+5s]^t : s \in \Bbb R \}$ (Here $M^t$ denotes the transpose of a matrix $M$). Then how to find dimension of null space.

My attempt
I saw somewhere that
$$\begin{pmatrix}{1+2s \\ 2+3s \\ 3+4s \\ 4+5s}\end{pmatrix}  = \begin{pmatrix}{1 \\ 2 \\ 3 \\ 4}\end{pmatrix} + s 
 \begin{pmatrix}{2 \\ 3 \\ 4 \\ 5}\end{pmatrix}$$
where $s$ is a free variable. So $\dim(\mbox{null}(A)) = 1$. But don't know concept that is hidden behind it. Please help me.
 A: Short Answer
I'd say the fastest way to get there is by the Rank-Nullity theorem from which you can deduce:
$$\mathrm{dim}(\mathrm{Nul}\, A) = \text{ the number of free variables}$$
I believe that you referred to it in a comment. For an explanation of its validity in the context of the echelon form of a matrix, see this answer.
Long Answer
Say, we were unaware of the Rank-Nullity theorem and wanted to find the dimension of $\mathrm{Nul}\, A$. One way to find the dimension of the null space of a matrix is to find a basis for the null space. The number of vectors in this basis is the dimension of the null space. As I will show for the case of one free variable,$^1$ the number of vectors in the basis corresponds to the number of free variables.
We are told that all solutions $\mathbf{x}$ to the given matrix equation
$$A\mathbf{x} = \mathbf{b}\tag1$$ where
$$\mathbf{b} = \begin{bmatrix}1\\2\\3\\4\\5\end{bmatrix}$$
are of the form $\mathbf{x} = \mathbf{p} + s\mathbf{q}$ for $s \in \mathbb{R}$ where
$$\mathbf{p} = \begin{bmatrix}1\\2\\3\\4\end{bmatrix} \qquad \text{and} \qquad \mathbf{q} = \begin{bmatrix}2\\3\\4\\5\end{bmatrix} \tag2$$
[The vector $\mathbf{p}$ is called a particular solution of (1).]
Let $X$ denote the solution set of (1)–that is, $X = \{\mathbf{x} : \mathbf{x} = \mathbf{p} + s\mathbf{q} \text{ for } s \in \mathbb{R}\}$, and recall that the null space of $A$ is the set of all vectors $\mathbf{x}$ which satisfy the equation
$$A\mathbf{x} = \mathbf{0} \tag3$$
There exists an intimate relationship between the vectors in $X$ and those in $\mathrm{Nul}\, A$. Denote the set $Z = X - X = \{\mathbf{z} : \mathbf{z} = \mathbf{x} - \mathbf{y} \text{ for }\mathbf{x}, \mathbf{y} \in X\}$, and observe that any $\mathbf{z} \in Z$ is a solution to (3).
$$A\mathbf{z} = A(\mathbf{x} - \mathbf{y}) = A\mathbf{x} - A\mathbf{y} = \mathbf{b} - \mathbf{b} = \mathbf{0} \qquad \text{where $\mathbf{x},\mathbf{y} \in X$} $$
Thus, $Z \subset \mathrm{Nul}\, A$.
Since $\mathbf{x} = \mathbf{p} + r\mathbf{q}$ and $\mathbf{y} = \mathbf{p} + s\mathbf{q}$ for some $r,s \in \mathbb{R}$, we have that $\mathbf{z} = \mathbf{x} - \mathbf{y} = (r-s)\mathbf{q}$. Thus, any $\mathbf{z} \in Z$ can be written in the form $t\mathbf{q}$ (choose $t = r -s$), and every vector $t\mathbf{q}$ corresponds to a vector $\mathbf{z} \in Z$ (choose $r-s =t$). In other words, $Z = \mathrm{Span}\{\mathbf{q}\}$, so similarly, we have $\mathrm{Span}\{\mathbf{q}\} \subset \mathrm{Nul}\, A$.
Next, we will show that every vector in the null space of $A$ is in $\mathrm{Span}\, \{\mathbf{q}\}$.
Let $\mathbf{x} = \mathbf{p} + r\mathbf{q}$ where $r \in \mathbb{R}$ (that is, $\mathbf{x} \in X$), and suppose $\mathbf{u} \in \mathrm{Nul}\, A$. Then, we have
$$A(\mathbf{x} + \mathbf{u}) = A(\mathbf{p} + r\mathbf{q} + \mathbf{u}) = A(\mathbf{p} + \mathbf{u}) + A(r\mathbf{q}) = A(\mathbf{p} + \mathbf{u}) = \mathbf{b} + \mathbf{0} = \mathbf{b}$$
Thus, $\mathbf{p} + \mathbf{u}$ is a solution to (1) and must be of the form $\mathbf{p} + s\mathbf{q}$. That is,
$$\mathbf{p} + \mathbf{u} = \mathbf{p} + s\mathbf{q}  \quad \text{or equivalently} \quad \mathbf{u} = s\mathbf{q} \quad \text{for some $s \in \mathbb{R}$}$$
Thus, if $\mathbf{u} \in \mathrm{Nul}\, A$, $\mathbf{u}$ is a scalar multiple of $\mathbf{q}$, which by definition means that $\mathbf{u} \in \mathrm{Span}\{\mathbf{q}\}$.
As we have shown that $\mathrm{Nul}\, A \subset \mathrm{Span} \{\mathbf{q}\}$ and $\mathrm{Span} \{\mathbf{q}\} \subset \mathrm{Nul}\, A$, we have that $\mathrm{Span} \{\mathbf{q}\} = \mathrm{Nul}\, A$.
Since $\{\mathbf{q}\}$ is a linearly independent set which spans $\mathrm{Nul}\, A$, $\{\mathbf{q}\}$ is a basis for $\mathrm{Nul}\, A$, and $\mathrm{dim}(\mathrm{Nul})\, A = 1$.

$^1$ For the case of $n$ free variables, this relationship holds as well. Any solution $\mathbf{x}$ to a nonhomogeneous system can be written as
$$\mathbf{x} =\mathbf{p} + \sum_{i = 1}^n s_i \mathbf{q}_i$$
where $\mathbf{p} \ne \mathbf{0}$ denotes a particular solution to the nonhomogeneous system, $s_i$ denotes a free variable, and each $\mathbf{q}_i$ is analogous to $\mathbf{q}$ from (2). From here, we would show that each $\mathbf{q}_i \in \mathrm{Nul}\, A$ and that if $\mathbf{x} \in \mathrm{Nul}\, A$, then $\mathbf{x} \in \mathrm{Span}\{\mathbf{q}_1,\dotsc,\mathbf{q}_n\}$. Confirming the linear independence of the set $\{\mathbf{q}_1,\dotsc,\mathbf{q}_n\}$ establishes $\{\mathbf{q}_1,\dotsc,\mathbf{q}_n\}$ as a basis for $\mathrm{Nul}\, A$ with $n$ vectors, so that we may conclude $\mathrm{dim}(\mathrm{Nul}\, A) = n$.
A: The general solution for a linear system $Ax=b$ is given by two terms:
$$x=x_p+x_h$$
with

*

*particular solution $Ax_p =b$

*homogeneous solution $Ax_h =0$
such that
$$Ax=A(x_p+x_h)=Ax_p+Ax_h=b+0=b$$
In your case we have
$$x_p=\begin{pmatrix}{1 \\ 2 \\ 3 \\ 4}\end{pmatrix}\quad x_h= s 
 \begin{pmatrix}{2 \\ 3 \\ 4 \\ 5}\end{pmatrix}$$
and since $x_h$ is a subspace with dimension $1$ we have that $\dim(\mbox{null}(A)) = 1$.
