0

The is an example:

x1 + x2 - x4 = 0
x1 + x3 - x5 = 0

The solutions are: (1,0,0,1,1), (0,1,1,0,0), (0,0,0,1,1). We know that there are 3 such solution, because there are 2 LI equations where there should be 5, and 5-2 = 3. We can find them by hand.

But how does a computer find these 3 solutions algorithmically? Or more generally:

How does a computer find all linearly independent solution of Ax = 0 ? Assuming there's always at least one solution.

Thank you.

Quickmath
  • 3
  • Well, there’s always at least one solution to a homogeneous system of linear equations: 0. – amd Dec 12 '19 at 07:33

1 Answers1

1

The one that is taught most often in linear algebra classes is the process of Gaussian Elimation.

It works by converting the system of equations into matrix form and then by performing a series of elementary row operations. It can be done by hand and a variant of it is useful for finding matrix inverses if they exist.

Matt Werenski
  • 2,426
  • You don't have to convert the system into the matrix form. The Gaussian elimination can be done in the equation form also. – A.Γ. Dec 12 '19 at 06:37
  • Once you have the RREF, this describes a purely mechanical way to extract a kernel basis from it. For large systems of equations, other methods (such as computing the SVD) that are more efficient and numerically stable than Gaussian elimination are used. – amd Dec 12 '19 at 07:29
  • How can you perform Gaussian Elimination on the sample equations above to get the 3 solutions? In matrix form the equation would be: [[1 1 0 -1 0], [1 0 1 0 -1] ...] * x = [0,0,0,0,0] – Quickmath Dec 12 '19 at 07:55