I am studying linear alegbra and came across over-determined system(https://en.wikipedia.org/wiki/Overdetermined_system) By plotting it makes sense that it may not have solution in most cases. But intuitively I can't understand it.
It seems to me as if there is more information and lesser unknowns. Then should there be a problem to find the solution.
On
It seems to me as if there are more information and lesser unknowns. Then should there be a problem to find the solution.
In general it is the opposite. Suppose you have the linear equation system
$x+y=15$
$x-y=5$
$2y=x$
This is an overdetermind equation system. If a solution exist, then you need only two of the three equations to solve the system. You can use the first two equations.
$x=15-y$
Inserting the expression for x into the second equation.
$(15-y)-y=5$
$15-2y=5$
$10=2y$
$y=5$
And from the equtions 1 or 2 your get $x=10$.
Firnally you have to prove if the third equation holds with these values.
$2\cdot 5=10$
This is true.
If you would have 3 equations and 3 variables then it is in general more time consuming to find a solution.
Let $$ A x = b $$ the system, with $A \in \mathbb{R}^{m \times n}, x \in \mathbb{R}^n, b \in \mathbb{R}^m$. This is equivalent to $m$ equations in $n$ dimensions $$ \alpha_i \cdot x = \beta_i $$ which for $\alpha_i \ne 0$ can be interpreted as the equation of an affine hyper plane (a plane with dimension $n-1$, not necessarily through the origin) with normal vector $\alpha_i$ and (signed) distance $d = \beta_i / \lVert \alpha_i \rVert$ to the origin.
The solution to the system must lie in the intersection of all the $m$ hyperplanes.
For $n=2$ the hyperplanes are one-dimensional, thus lines.
And the images illustrate nicely the more random lines you add, the less likely it gets that there is a common intersection point to all lines.