If $Y = X\beta$ are a system of linear equations and that $X$ is NOT full rank. Is this system under or over determined?

Question

Suppose I have a system of linear equations, $Y = X\beta$, where $Y$ is a $n$ by $1$ matrix, $X$ an $n$ by $n$ matrix, and $\beta$ a $n$ by $1$ matrix. Suppose that I know what $Y$ and $X$ are, and that I want to solve for $\beta$. This decomposes into a set of system of equations.

Now, suppose that $X$ is not full rank, that is, at least one of the columns is a linear combination of the other. In this case, would this be an overdetermined or underdetermined system, or could it be either depending on the structure of $X$?

Additionally, due to $X$ being not full rank, I would not be able to do any inversions, so how exactly can I find the solution to $\beta$? Thank you!

Answer 1

This would be an underdetermined system meaning that the image of $X$ is not the full vector space containing $Y$. This means that you cannot necessarily solve your linear equation -- you can only do it when $Y$ is in the image of $X$!

Answer 2

Just don't talk about over or under determined linear systems of equations- it isn't a helpful concept.

The most common definition of over/under determined is that a linear system of equations is over determined if it has more equations than variables and under determined if it has fewer equations than variables.

In general, a system of equations may have 0, 1, or infinitely many solutions. An under determined system may only have 0 or infinitely many solutions. A system with as many equations as variables may have 0, 1, or infinitely many solutions. An over determined system may also have 0, 1, or infinitely many solutions.

Thus under the above definition of over/under determined you can't conclude anything about how many solutions a system of equations might have.

You could also try to define that a linear system of equations is under determined if it has multiple solutions, but then you couldn't conclude anything about the number of variables and equations in an under determined system.

Overall, the concept of an under/over determined linear system of equations isn't terribly useful. You're much better off focusing on the concept of rank, because knowing the rank of your matrix makes possible some conclusions about the number of solutions.

Answer 3

The usual case is you have $n$ unknowns and $m$ equations, or short $$ A x = y $$ with $A \in \mathbb{F}^{m \times n}$, $x \in \mathbb{F}^n$ and $y \in \mathbb{F}^m$. You do your Gauss elimination and count the non-zero rows of the result and end up with $r = \DeclareMathOperator{rank}{rank}\rank A$ non-zero rows, where $r \in \{ 0, \dotsc, n \}$.

An undetermined system in my understanding (which might be wrong :-) is a system with more than one solution, which is the case for linear systems with infinite many solutions. This requires $r < n$ and no inconsistent equations (which would enforce no solution)-

An overdetermined system in my understanding is a system which got more equations than variables, so just $m > n$. Which says nothing about what $r$ might be behind those equations.

The last time I heard of an overdetermined system, it was a about a measurement of some physical quantity (e.g. the intensity $I$ of an X-ray beam after it passed through some tree). Each measurement would result in one equation. Actually there would be a need for more than $n$ equations and thus more than $n$ measurements, because those measurement have errors attached. These errors would in general prevent having an invertible matrix after just $n$ measurements or just return no precise enough solution.

But here taking $m > n$ would result in a better approximative solution of equation $(*)$ via $$ A^T A x = A^T y \iff \\ x = (A^T A)^{-1} A^T y $$ where it can be shown that this solution minimizes the error in the $\lVert.\rVert_2$ norm (least squares method).

In your case the system is not overdetermined because $m = n$, but it might be underdetermined (as $r < n$) or it has no solution at all (if there are inconsistent equations).

Answer 4

your system can not be overdetermined system, but it can be underdetermined or not; and it would have not solution iff $Y$ is not in image of $X$ and it have infenitely of solution iff $Y$ is not in the image of $X$, so the solvabilite of $Y=X\beta$ depending on the $Y$.