# Solving an $n\times m$ linear system exactly

Consider a system $Ax=b$ in which $A$ is an $n\times m$ matrix and $n < m$. Also the $rank(A)=n-1$. It is worthy to be noted that entries of matrix $A$ are partly rational. I need to solve this system exactly to find a feasible solution or proving that the system is inconsistent.

1. What is the running time of Gauss-Jordan method to solve this system?
2. Does there exist any method better than Gauss-Jordan to decide consistency or inconsistency of this system?
-
What is the significance of having entries that are 'partly rational'? What does this mean? If some entries are not 'partly rational', what are they then? – copper.hat Jul 23 '12 at 19:06
Some entries are integer ranged between 0,-1,1 and the other entries are rational. – Star Jul 23 '12 at 19:14

In comments you have confirmed that all elements everywhere are rational numbers, possibly integers. As a result, there is no need to approximate anything. For each row $i,$ multiply through by the least common multiple of all the denominators in that row, including $b_i.$ Now all numbers are integers. Do Gauss elimination over the integers. This means the following: suppose you have an entry $a$ as the first entry in a row, and you plan to pivot there, eliminating every other nonzero entry in the same column as that $a.$ For any row beginning with some $c$ in the same column, multiply that row through by $a/g,$ where $g = \gcd(a,c).$ Now subtract off the proper multiple of the row with $a,$ you now have a row with a $0$ where there was previously a $c.$ Repeat until a decision has been made about feasibility.

It is not necessary to approximate anything.

-

It is unlikely that you can solve such a system exactly. An $n \times m$ system with $n < m$ means that you have fewer equations than you have unknowns. There are two possibilities: either the columns of $A$ are not all linearly independent, and the resulting rank of $A$ equals the row dimension, in which case you just delete the dependent columns; or you must use some sort of optimization routine to minimize a squared-error. See, for example, my response here: http://math.stackexchange.com/a/173259/31475

Edit: I overlooked your comment regarding rank.

Since $\rm{rank}(A) = n-1$, then you definitely have more "unknowns" in $x$ than you have equations. The rationality of entries of $A$ likely has no effect; only in the instance that you expect $x \in \Bbb Q^m$ would you be able to possibly exactly solve such a system (and even then, not guaranteed).

In any case, running time for Gauss-Jordan is, if my memory serves, $\mathcal{O}\left(n^3\right)$.

-
n is max{n,m}. Right? – Star Jul 23 '12 at 19:17
$n$ is row dimension, because typically the algorithms operate row-wise. Either way, it is irrelevant for $n,m$ of approximately equal order of magnitude, because $m = n+k$, so $n^2m = n^2(n+k)=n^3+kn^2 \approx \mathcal{O}(n^3)$. – Arkamis Jul 23 '12 at 19:20
In my problem $m=O(n^2)$. So, the running time should be $O(n^4)$? – Star Jul 23 '12 at 19:32
I would be hesitant to claim that generally, but in a particular situation, basically. – Arkamis Jul 23 '12 at 19:37

You have an underdetermined system. Unless you have exact values for the entries of your matrix (and are using some kind of exact arithmetic package) solving the system by Gaussian elimination is unwise as it will be numerically unstable. The standard approach is to apply a rank-revealing QR decomposition with pivoting to $A^T$. You then have the system

$$R^T Q^T x = b$$ which you can solve by first finding $Q^Tx$ using forward substitution (this will fail if your system has no solution) and then multiplying by $Q$.

The above has time complexity $O(n^2m)$, I believe.

-
Thanks for your comment. What do you mean by exact values of entries? Is this typo? [and then multiplying by Q]. Shouldn't be $\tr(A)$. Any reference paper or lecture note would be appreciated. – Star Jul 23 '12 at 19:21
If you have exact values for all entries of $A$ and $b$, then it doesn't matter much which algorithm you use: you can use Gaussian elimination using exact arithmetic at each step to get the exact solution (if it exists). But if your entries have some numerical error (for example, if they're represented using finite-precision floating point) then it becomes important to use a numerically stable algorithm or you can get wildly wrong solutions. – user7530 Jul 23 '12 at 22:07
If you have $Q^Tx$, you recover $x$ by multiplying by $Q$: $QQ^Tx = Ix = x$. The transpose is not a typo: by taking the QR decomposition of $A^T$ you get an upper-triangle "skinny" matrix which is much sparser than the matrix you get when you use $A$ and allows you to use forward substitution. For more details see any good textbook on numerical linear algebra, for instance section 5.7.2 of Matrix Computations by Golub and Van Loan. – user7530 Jul 23 '12 at 22:11