# Is there a way to solve a linear system without using Gaussian elimination?

Is there some way to get the solutions to a matrix without using Gaussian elimination?

In other words, if we have a matrix $A$, we can multiply it by a change-of-basis matrix $P$, to get $PA=B$. Suppose that I don't know the solutions to $A$. I imagine somehow that I can change the basis of $A$ to get a matrix $B$ where I can read off the solutions. Is something like this possible? I'm mainly wondering if there is some way to solve $A$ without Gaussian elimination.

• Gaussian elimination is exactly equivalent to successively multiplying a matrix with so-called "Gauss transforms" that gradually transform it into a triangular matrix. Look up $\mathbf L\mathbf U$ decomposition, and see Golub and Van Loan, for instance. – J. M. is a poor mathematician Oct 12 '16 at 15:02
• @J.M.:Thanks - I just forgot this a long time ago... That should do the trick, plus it's very fast. – Matt Groff Oct 12 '16 at 15:09
• @J.M.: one problem I have is that I'm trying to do the calculations modulo a composite number. Do you think it will still work? – Matt Groff Oct 12 '16 at 15:12
• Solutions to a matrix what? – Rodrigo de Azevedo Oct 12 '16 at 15:12
• @RodrigodeAzevedo: If we have a system of equations, $a_{1,1} x_1 + a_{1,2}x_2=b_1,a_{2,1}x_1+b_{2,2}=x_2$, then I want to get $x_1$ and $x_2$ without using Gaussian elimination, because it doesn't always work modulo a composite. I'm working in a restricted setting, but I know that I can use matrix operations like matrix multiplication, addition, and subtraction to get the results. – Matt Groff Oct 12 '16 at 15:17

Suppose we have a linear system in $\mathrm x \in \mathbb R^n$

$$\mathrm A \mathrm x = \mathrm b$$

where $\mathrm A \in \mathbb R^{m \times n}$ and $\mathrm b \in \mathbb R^m$ are given. We build the objective function

$$f (\mathrm x) := \frac 12 \| \mathrm A \mathrm x - \mathrm b \|_2^2$$

$$\nabla f (\mathrm x) = \mathrm A^{\top} (\mathrm A \mathrm x - \mathrm b)$$

which vanishes at the solution to the famous "normal equations"

$$\mathrm A^{\top} \mathrm A \mathrm x = \mathrm A^{\top} \mathrm b$$

which is the least-squares solution. Doing continuous-time gradient descent,

$$\dot{\mathrm x} = -\nabla f (\mathrm x)$$

we obtain the ODE

$$\dot{\mathrm x} + \mathrm A^{\top} \mathrm A \mathrm x = \mathrm A^{\top} \mathrm b$$

We can now use numerical methods for ODEs to find the least-squares solution. If the original linear system, $\mathrm A \mathrm x = \mathrm b$, is consistent, then the least-squares solution is also a solution to $\mathrm A \mathrm x = \mathrm b$.

• +1, and I will probably accept this answer - it will just take me some time to review it... I was wondering, are there books or topics I could research that cover these ideas more thoroughly? Also, I know that the linear systems I use this for are consistent, but I'm not sure they're consistent modulo a composite $Q$. Maybe I will save that for, unfortunately, another question... – Matt Groff Oct 12 '16 at 15:56
• @MattGroff If you're interested in "continuous-time linear algebra", take a look at Uwe Helmke & John B. Moore's Optimization and Dynamical Systems. Section 1.6 (on page 38) is on least-squares gradient flows. – Rodrigo de Azevedo Oct 12 '16 at 16:12
• I see them referring to J.M.'s reference, Golub and Van Loan. I think I will look into these topics, which will take a little while... Thanks for all your help. – Matt Groff Oct 12 '16 at 16:19

Given $\mathrm A \in \mathbb R^{m \times n}$, we can use Gram-Schmidt to compute the QR decomposition $\mathrm A = \mathrm Q \mathrm R$, where $\mathrm Q \in \mathbb R^{m \times m}$ is orthogonal and $\mathrm R \in \mathbb R^{m \times n}$ is upper triangular. Hence, the linear system

$$\mathrm A \mathrm x = \mathrm b$$

becomes $\mathrm Q \mathrm R \mathrm x = \mathrm b$. Since $\mathrm Q$ is orthogonal, i.e., $\mathrm Q^{\top} \mathrm Q = \mathrm I_m$, we have the upper triangular system

$$\mathrm R \mathrm x = \mathrm Q^{\top}\mathrm b$$

which can be solved via back substitution.

As a joke, some say that the people who study numerical linear algebra all they do is solving Ax=b. And numerical analysts also make fun of people that think gauss elimination is the way to go. Some of the most prominent methods for linear systems are projective methods, in particular Krylov subspace methods. Take a look at the text Numerical Methods in Matrix Computations by Ake Bjorck for an extensive review of a large number of methods to solve linear systems.