Solve an overdetermined system of linear equations

Question

I have doubt to solve this system of equations

\begin{cases} x+y=r_1\\ x+z=c_1\\ x+w=d_1\\ y+z=d_2\\ y+w=c_2\\ z+w=r_2 \end{cases}

Is it an overdetermined system because I see there are more equations than unknowns.

Can we just solve this system in a simple way?

Answer 1

Hint:

Write the system of linear equations in matrix form: set $$A=\begin{bmatrix} 1&1&0&0\\1&0&1&0\\1&0&0&1\\0&1&1&0\\0&1&0&1\\0&0&1&1 \end{bmatrix},\quad X=\begin{bmatrix}x\\y\\z\\w\end{bmatrix},\quad B=\begin{bmatrix}r_1\\c_1\\d_1\\d_2\\c_2\\w_2\end{bmatrix}$$ $A$ is the matrix of a linear mapping from $\mathbf R^4$ to $\mathbf R^6$ (supposing the base field is $\mathbf R$) and the linear system can be written as $$AX=B.$$ Now this system has solutions, by definition, if $B$ is in the image of the linear map. A criterion for this is the following:

The linear system $\;AX=B$ has a solution if and only if the matrix $A$ and the augmented matrix $(A\mid B)$ have the same rank. Furthermore, the set of solutions, if any, is an affine space directed by the subvectorspace $\ker A$ and has codimension the rank of $A$.

Using row reduction, you should find $A$ has maximal rank ($4$), and if the augmented matrix also has rank $4$, there is a unique solution, which you'll find with full row reduction.

Answer 2

Your system is described by the augmented matrix $$ A= \left[\begin{array}{rrrr|r} 0 & 1 & 1 & 0 & r_{1} \\ 0 & 1 & 0 & 1 & c_{1} \\ 1 & 1 & 0 & 0 & d_{1} \\ 0 & 0 & 1 & 1 & d_{2} \\ 1 & 0 & 1 & 0 & c_{2} \\ 1 & 0 & 0 & 1 & r_{2} \end{array}\right] $$ Row-reducing the system gives $$ \DeclareMathOperator{rref}{rref}\rref A= \left[\begin{array}{rrrr|r} 1 & 0 & 0 & 0 & -\frac{1}{2} \, c_{1} + d_{1} + \frac{1}{2} \, d_{2} - \frac{1}{2} \, r_{1} \\ 0 & 1 & 0 & 0 & \frac{1}{2} \, c_{1} - \frac{1}{2} \, d_{2} + \frac{1}{2} \, r_{1} \\ 0 & 0 & 1 & 0 & -\frac{1}{2} \, c_{1} + \frac{1}{2} \, d_{2} + \frac{1}{2} \, r_{1} \\ 0 & 0 & 0 & 1 & \frac{1}{2} \, c_{1} + \frac{1}{2} \, d_{2} - \frac{1}{2} \, r_{1} \\ 0 & 0 & 0 & 0 & c_{1} + c_{2} - d_{1} - d_{2} \\ 0 & 0 & 0 & 0 & -d_{1} - d_{2} + r_{1} + r_{2} \end{array}\right] $$ This implies that your system is solvable if and only if \begin{align*} c_1+c_2-d_1-d_2 &= 0 \\ -d_1-d_2+r_1+r_2 &= 0 \end{align*} If these conditions are satisfied, then your system is solved by \begin{align*} w &=-\frac{1}{2} \, c_{1} + d_{1} + \frac{1}{2} \, d_{2} - \frac{1}{2} \, r_{1} \\ x &= \frac{1}{2} \, c_{1} - \frac{1}{2} \, d_{2} + \frac{1}{2} \, r_{1}\\ y &= -\frac{1}{2} \, c_{1} + \frac{1}{2} \, d_{2} + \frac{1}{2} \, r_{1}\\ z &=\frac{1}{2} \, c_{1} + \frac{1}{2} \, d_{2} - \frac{1}{2} \, r_{1} \end{align*}

Answer 3

Start with the linear system $$ \begin{align} \mathbf{A} x &= b \\ \left[ \begin{array}{cccc} 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ \end{array} \right] % \left[ \begin{array}{c} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{array} \right] % &= % \left[ \begin{array}{c} b_{1} \\ b_{2} \\ b_{3} \\ b_{4} \\ b_{5} \\ b_{6} \end{array} \right] % \end{align} $$ We see that $$ \mathbf{A} \in \mathbb{R}^{6\times 4}_{4}, \quad b \in \mathbb{R}^{6}, \quad x \in \mathbb{R}^{4}; $$ that is $\mathbf{A}$ has $m=6$ rows, $n=4$ columns, and has rank $\rho=4$. The nullspace vectors reveal $$ \mathcal{N}\left(\mathbf{A}^{*}\right) = \text{span} \left\{ \left[ \begin{array}{r} 1 \\ 0 \\ -1 \\ -1 \\ 0 \\ 1 \end{array} \right] , \left[ \begin{array}{r} 0 \\ 1 \\ -1 \\ -1 \\ 1 \\ 0 \end{array} \right] % \right\} $$

Let's look at this problem using the method of least squares. As long as the data vector $b$ is not in the nullspace, there will be a least squares solution. The normal equations offer easy resolution: $$ \begin{align} \mathbf{A}^{*}\mathbf{A} x &= \mathbf{A}^{*} b \\[5pt] % \left[ \begin{array}{cccc} 3 & 1 & 1 & 1 \\ 1 & 3 & 1 & 1 \\ 1 & 1 & 3 & 1 \\ 1 & 1 & 1 & 3 \\ \end{array} \right] % \left[ \begin{array}{c} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{array} \right] % &= % \left[ \begin{array}{c} b_1 + b_2 + b_3 \\ b_1 + b_4 + b_5 \\ b_2 + b_4 + b_6 \\ b_3 + b_5 + b_6 \end{array} \right]. % \end{align} $$ The least squares solution is $$ \begin{align} x_{LS} &= \left( \mathbf{A}^{*}\mathbf{A} \right)^{-1} \mathbf{A}^{*} b \\[5pt] % &= % \frac{1}{12} \left[ \begin{array}{rrrrr} 5 & -1 & -1 & -1 \\ -1 & 5 & -1 & -1 \\ -1 & -1 & 5 & -1 \\ -1 & -1 & -1 & 5 \\ \end{array} \right] % \left[ \begin{array}{c} b_1 + b_2 + b_3 \\ b_1 + b_4 + b_5 \\ b_2 + b_4 + b_6 \\ b_3 + b_5 + b_6 \end{array} \right]\\[5pt] % &= % \frac{1}{6} \left[ \begin{array}{rcrcrcrcrcrc} 2 b_1 & + & 2 b_2 & + & 2 b_3 & - & b_4 & - & b_5 & - & b_6 \\ 2 b_1 & - & b_2 & - & b_3 & + & 2 b_4 & + & 2 b_5 & - & b_6 \\ -b_1 & + & 2 b_2 & - & b_3 & + & 2 b_4 & - & b_5 & + & 2 b_6 \\ -b_1 & - & b_2 & + & 2 b_3 & - & b_4 & + & 2 b_5 & + & 2 b_6 \end{array} \right] % \end{align} $$ Because the problem has full column rank $m=\rho=4$, $\mathcal{N}\left( \mathbf{A}\right) = \left\{ \mathbf{0} \right\}$ the solution is unique.

Is this the direct solution where $\mathbf{A}x - b = 0$? The residual error vector shows the constraints required for a direct solution. $$ r(x) = \mathbf{A}x - b = % \frac{1}{6} % \left[ \begin{array}{rcrcrcrcrcrc} -2 b_{1} & + & b_{2} & + & b_{3} & + & b_{4} & + & b_{5} & - & 2 b_{6} \\ b_{1} & - & 2 b_{2} & + & b_{3} & + & b_{4} & - & 2 b_{5} & + & b_{6} \\ b_{1} & + & b_{2} & - & 2 b_{3} & - & 2 b_{4} & + & b_{5} & + & b_{6} \\ b_{1} & + & b_{2} & - & 2 b_{3} & - & 2 b_{4} & + & b_{5} & + & b_{6} \\ b_{1} & - & 2 b_{2} & + & b_{3} & + & b_{4} & - & 2 b_{5} & + & b_{6} \\ -2 b_{1} & + & b_{2} & + & b_{3} & + & b_{4} & + & b_{5} & - & 2 b_{6} \end{array} \right] $$