# Given a matrix, how to build an equation or inequality using variables that gives unique solution?

I want to solve a system of equations of the form $$Ax = b$$ where $A$ is a $6\times 15$ matrix, $x$ is $15\times 1$, and $b$ is $6\times 1$. In the absence of other constraints, this system of equations does not have a unique solution.

Suppose that I have the following composite matrix, $C = [A\,|\,b]$: $$\left[ \begin{array}{ccccccccccccccc|l} 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 2A& 0& 0& e_{1}^{2} - A^2\\ 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 2B& 0& e_{2}^{2} - B^2\\ 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 2C& e_{3}^{2} - C^2\\ 1& 1& 0& 1& 1& 0& -2& 0& 0& -2& 0& 0& 0& 0& 0& P^2\\ 1& 0& 1& 1& 0& 1& 0& -2& 0& 0& -2& 0& 0& 0& 0& Q^2\\ 0& 1& 1& 0& 1& 1& 0& 0& -2& 0& 0& -2& 0& 0& 0& R^2 \end{array} \right]$$

Can I build an equation or inequality using terms $A, B, C, P, Q, R, e_1, e_2, e_3$ That gives me only one solution? e.g. $A \neq B$; $P+Q+R = C$ and $e_1, e_2, e_3$ are not significant.

Moreover, can I say something like "If $A = B = C$, then the solution for space is between $-2$ and $5$ etc.?

I have used Gauss-Jordan Elimination. I have only used the coefficients of terms ($2$ for $2A,2B,2C$ and $1$ for all the elemenst of $b$). The result was the following:

$x_1 = 2x_8 + 2x_{11} + 2x_{15}$

$x_2 = 1 - x_5 - 2x_{14}$

$x_3 = 1 - x_6 - 2x_{15}$

$x_4 = 1 - 2x_8 - 2x_{11} - 2x_{13} - 2x_{15}$

$x_7 = 1/2 - x_10 - x_{13} - x_{14}$

$x_9 = 1/2 - x_{12} - x_{14} - x_{15}$

$x_5, x_6, x_8, x_10, x_{11}, x_{12}, x_{13}, x_{14}, x_{15}$ - free

But still, my question remains.

The matrix that represents the row operations that brings A to row echelon form is: $$E = \begin{bmatrix} 1&0&0&0&0&0\\ 0&1&0&0&0&0\\ 0&0&1&0&0&0\\ -1&-1&0&1&0&0\\ -1&0&-1&0&1&0\\ 0&-1&-1&0&0&1\\ \end{bmatrix}$$

Multiplying on the left by $E$ brings $A$ to row echelon form. That is, $ref(A) = EA$. I get $$EA= \begin{array}{ccccccccccccccc} x_1&x_2&x_3&x_4&x_5&x_6&x_7&x_8&x_9&x_{10}&x_{11}&x_{12}&x_{13}&x_{14}&x_{15}\\ \hline 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 2A& 0& 0\\ 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 2B& 0\\ 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 2C\\ 0& 0& 0& 0& 0& 0&-2& 0& 0&-2& 0& 0& -2A& -2B& 0\\ 0& 0& 0& 0& 0& 0& 0&-2& 0& 0&-2& 0& -2A& 0& -2C\\ 0& 0& 0& 0& 0& 0& 0& 0&-2& 0& 0&-2& 0& -2B& -2C \end{array}$$

And performing the exact same row operations on $b$ I get,

$$Eb = \begin{bmatrix} e_{1}^{2} - A^2\\ e_{2}^{2} - B^2\\ e_{3}^{2} - C^2\\ A^2+B^2+P^2-e_1^2-e_2^2\\ A^2+C^2+Q^2-e_1^2-e_3^2\\ R^2+B^2+C^2-e_1^2-e_3^2 \end{bmatrix}$$

So, $x_1, x_2, x_3, x_7, x_8\,\text{and} \, x_9$ are the basic variables, and $x_4, x_5, x_6, x_{10}, x_{11}, x_{12}, x_{13}, x_{14}, x_{15}$ are free variables. Let's write equations for each of the basic variables in terms of the free variables... \begin{align} x_1 &= -x_4 -2Ax_{13} + e_{1}^{2} - A^2\\ x_2 &= -x_5 -2Bx_{14} + e_{2}^{2} - B^2\\ x_3 &= -x_6 -2Cx_{15} + e_{3}^{2} - C^2\\ -2x_7 &= 2x_{10}+ 2Ax_{13} + 2Bx_{14} + A^2+B^2+P^2-e_1^2-e_2^2\\ -2x_8 &= 2x_{11}+ 2Ax_{13} + 2Cx_{15} + A^2+C^2+Q^2-e_1^2-e_3^2\\ -2x_9 &= 2x_{12}+ 2Bx_{14} + 2Cx_{15} + R^2+B^2+C^2-e_1^2-e_3^2 \end{align}

Now, you can choose whatever value seems convenient for each of the free variables.

• Thank you for your time. this is about my research and you just made a great contribution. Thank you again and again Mar 31, 2014 at 8:06

You can use the method of linear least squares to find the solution to $\text{min}_x ||Ax-b||_2$ where $||\cdot ||_2$ represent the vector 2-norm. This will give a solution to the equation $Ax=b$ if one exists, and it will still give a "closest fit" solution even when an actual solution does not exist. The solution is only unique when $A$ is full rank. To enforce a kind of uniqueness you can restrict $x$ such that $x$ has smallest norm and satisfies the minimization problem. I forget off the top of my head but I believe using the pseudo inverse from the singular value decomposition will automatically give the $x$ of smallest 2-norm.

• Simple linear regression is not really applicable here. It is usually applicable when there are many more equations than unknowns. The OP has presented the opposite....there are many more unknowns than equations. The matrix, A in the present probelm has full row rank and there are nine (!) free variables. Thus, there are infinitely many solutions to Ax= b for any b. Mar 24, 2014 at 3:38
• I'm not sure why you think it's not applicable, and I already addressed how to deal with infinitely many solutions.
– R R
Mar 24, 2014 at 5:00
• Perhaps, I am not understanding something. Can you could show your solution using a least squares approach? Mar 24, 2014 at 16:41