3
$\begingroup$

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?
  • 0
    Some entries are integer ranged between 0,-1,1 and the other entries are rational.2012-07-23

3 Answers 3

2

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.

1

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: https://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)$.

  • 0
    I would be hesitant to claim that generally, but in a particular situation, basically.2012-07-23
1

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.

  • 0
    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.2012-07-23