2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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*}

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The maximal rank of the augmented matrix is $5$; we need that the augmented matrix has rank $4$ too. $\endgroup$ – egreg Jul 15 '16 at 14:51
  • $\begingroup$ @egreg: I completely messed up with rows and columns… Thanks for pointing the error. I've fixed the answer. $\endgroup$ – Bernard Jul 15 '16 at 15:07
1
$\begingroup$

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] $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.