Find the least squares solution for rank deficient system 
Find the least squares solution to the system
$$x - y = 4$$
$$x - y = 6$$

Normally if I knew what the matrix $A$ was and what $b$ was I could just do $(A^TA)^{-1} A^Tb$, but in this case I'm not sure how to set up my matrices. How can I find the least square solution to the system?
 A: Problem statement: underdetermined system
Start with the linear system
$$
\begin{align}
\mathbf{A} x &= b \\
%
\left[
\begin{array}{cc}
 1 & -1 \\
 1 & -1 \\
\end{array}
\right]
%
\left[
\begin{array}{c}
 x \\
 y
\end{array}
\right]
%
&=
%
\left[
\begin{array}{c}
 4 \\
 6
\end{array}
\right]
%
\end{align}
$$
The system has matrix rank $\rho = 1$; therefore, if a solution exists, it will not be unique.
Provided $b\notin \color{red}{\mathcal{N} \left( \mathbf{A}^{*} \right)}$, we are guaranteed a least squares solution
$$
  x_{LS} = \left\{ x\in\mathbb{C}^{2} \colon \lVert \mathbf{A} x_{LS} - b \rVert_{2}^{2} \text{ is minimized} \right\}
\tag{1}
$$
Subspace resolution
By inspection, we see that the row space is resolved as
$$
\color{blue}{\mathcal{R} \left( \mathbf{A}^{*} \right)} \oplus
    \color{red}{\mathcal{N} \left( \mathbf{A} \right)} 
=
\color{blue}{\left[
\begin{array}{r}
  1 \\
 -1
\end{array}
\right]} \oplus
    \color{red}{\left[
\begin{array}{c}
  1 \\
  1
\end{array}
\right]} 
$$
The column space is resolved as
$$
\color{blue}{\mathcal{R} \left( \mathbf{A} \right)} \oplus
    \color{red}{\mathcal{N} \left( \mathbf{A}^{*} \right)} 
=
\color{blue}{\left[
\begin{array}{c}
  1 \\
  1
\end{array}
\right]} \oplus
    \color{red}{\left[
\begin{array}{r}
  -1 \\
   1
\end{array}
\right]} 
$$
The coloring indicates vectors in the $\color{blue}{range}$ space and the $\color{red}{null}$ space. 
Finding the least squares solution
Since there is only one vector in $\color{blue}{\mathcal{R} \left( \mathbf{A}^{*} \right)}$, the solution vector will have the form
$$
 \color{blue}{x_{LS}} = \alpha 
\color{blue}{\left[
\begin{array}{r}
  1 \\
 -1
\end{array}
\right]}
$$
The goal is to find the constant $\alpha$ to minimize (1):
$$
 \color{red}{r}^{2} = \color{red}{r} \cdot \color{red}{r} = 
\lVert
 \color{blue}{\mathbf{A} x_{LS}} - b
\rVert_{2}^{2}
=
8 \alpha ^2-40 \alpha +52
$$
The minimum of the polynomial is at 
$$
 \alpha = \frac{5}{2}
$$
Least squares solution
The set of least squares minimizers in (1) is then the affine set given by
$$ 
 x_{LS} = \frac{5}{2}
\color{blue}{\left[
\begin{array}{r}
  1 \\
 -1
\end{array}
\right]}
+
\xi
\color{red}{\left[
\begin{array}{r}
  1 \\
  1
\end{array}
\right]}, \qquad \xi\in\mathbb{C}
$$
The plot below shows how the total error $\lVert \mathbf{A} x_{LS} - b \rVert_{2}^{2}$ varies with the fit parameters. The blue dot is the particular solution, the dashed line homogeneous solution as well as the $0$ contour - the exact solution.
Addendum: Existence of the Least Squares Solution
To address the insightful question of @RodrigodeAzevedo, consider the linear system:
$$
\begin{align}
\mathbf{A} x &= b \\
%
\left[
\begin{array}{cc}
 1 & 0 \\
 0 & 0 \\
\end{array}
\right]
%
\left[
\begin{array}{c}
 x \\
 y
\end{array}
\right]
%
&=
%
\left[
\begin{array}{c}
 0 \\
 1
\end{array}
\right]
%
\end{align}
$$
The data vector $b$ is entirely in the null space of $\mathbf{A}^{*}$: 
$b\in \color{red}{\mathcal{N} \left( \mathbf{A}^{*} \right)}$
As pointed out, the system matrix has the singular value decomposition. One instance is:
$$\mathbf{A} = \mathbf{U}\, \Sigma\, \mathbf{V}^{*} = \mathbf{I}_{2} 
\left[
\begin{array}{cc}
 1 & 0 \\
 0 & 0 \\
\end{array}
\right]
\mathbf{I}_{2}$$
and the concomitant pseudoinverse,
$$\mathbf{A}^{\dagger} = \mathbf{V}\, \Sigma^{\dagger} \mathbf{U}^{*} = 
\mathbf{I}_{2}
\left[
\begin{array}{cc}
 1 & 0 \\
 0 & 0 \\
\end{array}
\right]
\mathbf{I}_{2} = \mathbf{A}$$
Following least squares canon, the particular solution to the least squares problem is computed as
$$
\color{blue}{x_{LS}} = \mathbf{A}^{\dagger} b =
\color{red}{\left[
\begin{array}{c}
 0 \\
 0 \\
\end{array}
\right]}
\qquad \Rightarrow\Leftarrow
$$
The color collision (null space [red] = range space [blue]) indicates a problem. There is no component of a particular solution vector in a range space! 
Mathematicians habitually exclude the $0$ vector a solution to linear problems. 
A: The linear system
$$\begin{bmatrix} 1 & -1\\ 1 & -1\end{bmatrix} \begin{bmatrix} x\\ y\end{bmatrix} = \begin{bmatrix} 4 \\ 6\end{bmatrix}$$
has no solution. Left-multiplying both sides by $\begin{bmatrix} 1 & -1\\ 1 & -1\end{bmatrix}^T$, we obtain the normal equations
$$\begin{bmatrix} 2 & -2\\ -2 & 2\end{bmatrix} \begin{bmatrix} x\\ y\end{bmatrix} = \begin{bmatrix} 10 \\ -10\end{bmatrix}$$
Dividing both sides by $2$ and removing the redundant equation,
$$x - y = 5$$
Thus, there are infinitely many least-squares solutions. One of them is
$$\begin{bmatrix} \hat x\\ \hat y\end{bmatrix} = \begin{bmatrix} 6\\ 1\end{bmatrix}$$
The least-squares solution is a solution to the normal equations, not to the original linear system.
A: First, choose points (x,y) that satisfy each equation.
$\begin{cases}
x - y = 4,  & \text{(6,2)} \\
x - y = 6, & \text{(10,4)}
\end{cases}$
Then, proceed as usual
$Ax = \begin{bmatrix}
1 & 6 \\
1 & 10 \\
\end{bmatrix}  \begin{bmatrix}
b \\
m \\
\end{bmatrix} = \begin{bmatrix}
2 \\
4 \\
\end{bmatrix}$
$\begin{bmatrix}
b \\
m \\
\end{bmatrix} =\begin{bmatrix}
5 \\
1/2 \\
\end{bmatrix}$
$y = 1/2x + 5$
A: Your matrix is just the coefficients of your system of equations.  In this case 
$$ x-y = 4  $$
$$ x-y = 6  $$
leads to 
$$
\begin{bmatrix}
1 & -1 \\ 1 & -1 
\end{bmatrix}
\begin{bmatrix}
x \\ y
\end{bmatrix} 
=
\begin{bmatrix}
4 \\ 6
\end{bmatrix}
$$
but you should see that there is no solution to this since you can't have $x-y$ be both $4$ and $6$...
A: We have the linear system
$$\begin{bmatrix} 1 & -1\\ 1 & -1\end{bmatrix} \begin{bmatrix} x\\ y\end{bmatrix} = \begin{bmatrix} 4 \\ 6\end{bmatrix}$$
which can be rewritten in the form
$$\begin{bmatrix} 1\\ 1\end{bmatrix} \eta = \begin{bmatrix} 4 \\ 6\end{bmatrix}$$
where $\eta = x - y$. Left-multiplying both sides by $\begin{bmatrix} 1\\ 1\end{bmatrix}^\top$, we obtain $2 \eta = 10$, or, $\eta = 5$. Hence,
$$x - y = 5$$
Thus, there are infinitely many least-squares solutions. One of them is
$$\begin{bmatrix} \hat x\\ \hat y\end{bmatrix} = \begin{bmatrix} 6\\ 1\end{bmatrix}$$
