Overdetermined linear system

linear algebrasystems of equations

What should be the conditions on coefficients $a_i$ and $b_i$ such that the following overdetermined linear system of equations has unique solution.
$$a_i x+y=b_i$$
where $i=1,2,3…,n$.

The system represents $n$ straight lines and it is possible to make them ins
tersect at one point, hence sytem must have a unique solution for some $a_i,b_i$.

Best Answer

The system is over-determined for $n>2$ but here is a general method. We can write the augmented matrix for the system $A\begin{bmatrix}x\\y\end{bmatrix}=B$ as under:

$\begin{bmatrix}a_1&1&\Big|&b_1\\a_2&1&\Big|&b_2\\\vdots&\vdots&\Big|&\vdots\\a_n&1&\Big|&b_n\end{bmatrix}$

For a unique solution to exist, we should have $2$ linearly-independent equations to solve for the $2$ unknowns. In other words, the rank of the coefficient and augmented matrices should be $2$. Recall that no more than $2$ vectors in $\Bbb R^2$ can be linearly independent, so the rank of the coefficient matrix $A, \text{rank}(A)\le2$. For $\text{rank}(A)=2$, we need to ensure at-least two $a_i$ are distinct. Say we have distinct $a_1\ne0,a_2\ne a_1$.

The point of intersection of $a_1x+y=b_1,a_2x+y=b_2$ is given by $(X,Y)=\displaystyle\Big(\frac{b_1-b_2}{a_1-a_2},\frac{a_1b_2-a_2b_1}{a_1-a_2}\Big)$.

$\displaystyle R_i\to R_i-\frac{a_i}{a_1}\cdot R_1,\ i>1$

$\displaystyle R_j\to R_j-\frac{1-\frac{a_i}{a_1}}{1-\frac{a_2}{a_1}}\cdot R_2,\ j>2$

$\sim\begin{bmatrix}a_1&1&\Big|&b_1\\0&1-\frac{a_2}{a_1}&\Big|&b_2-\frac{a_2}{a_1}\cdot b_1\\0&0&\Big|&b'_3\\\vdots&\vdots&\Big|&\vdots\\0&0&\Big|&b'_n\end{bmatrix}$

$\displaystyle b'_i=b_i-\frac{a_i}{a_1}\cdot b_1-\frac{1-\frac{a_i}{a_1}}{1-\frac{a_2}{a_1}}\cdot\Big[b_2-\frac{a_2}{a_1}\cdot b_1\Big] \forall i>2$

For the rank of the augmented matrix to be $0$, we require $b'_i=0$

$\displaystyle\therefore b_i=\frac{(a_i-a_2)b_1+(a_1-a_i)b_2}{a_1-a_2}=\Big[\frac{b_1-b_2}{a_1-a_2}\Big]\cdot a_i+\Big(\frac{a_1b_2-a_2b_1}{a_1-a_2}\Big),\ \forall i>2$

Therefore, if:

  • There are two lines $L_i,L_j$ not parallel to each other $(a_i\ne a_j)$ intersecting at $(X,Y)$;

  • $\displaystyle b_k=\Big[\frac{b_i-b_j}{a_i-a_j}\Big]\cdot a_k+\Big(\frac{a_ib_j-a_jb_i}{a_i-a_j}\Big)=Xa_k+Y,\ \forall k\ne i,j$; that is, $(X,Y)$ lies on all the remaining lines;

Then, the straight lines $L_i:= a_ix+y=b_i,i\in\{1,2,...,n\}$ intersect at the point $\displaystyle(X,Y)=\Big(\frac{b_i-b_j}{a_i-a_j},\frac{a_ib_j-a_jb_i}{a_i-a_j}\Big)$ uniquely.

Related Question