Find the basis of the solution set (with infinite solutions) of a linear system

Question

I have this linear system:

[e1 = x1+x5, x1 = s1+x2+x4, x2 = s2+x3, e2+x3 = x7+s3, x7+x4 = x6, x5+x6 = s4+s5]

And an additional (temporary) condition, which is that all e and s are equal to zero. I can simplify the system to this:

[0 = x1+x5, x1 = x2+x4, x2 = x3, x3 = x7, x7+x4 = x6, x5+x6 = 0]

Skipping a few steps, I get this matrix through gaussian elimination

$$\begin{bmatrix}-1&0&0&0&-1&0&0&0\\0&-1&0&-1&-1&0&0&0\\0&0&-1&-1&-1&0&0&0\\0&0&0&-1&-1&0&-1&0\\0&0&0&0&-1&-1&0&0\\0&0&0&0&0&0&0&0\end{bmatrix}$$

And I have the following solution for the linear system:

\begin{align}x_1&=x_6 \\ x_2&=x_7 \\ x_3&=x_7 \\ x_4&=-x_7+x_6 \\ x_5&=-x_6 \\ x_6&=x_6 \\ x_7&=x_7 \end{align}

There are still two free variables, since I did not have enough equations to get a single solution. This means that there are infinite solutions (another way to know this was to see the empty line in the matrix).

I have to find a basis and the Kernel for the set of solutions (which is infinite), and I have no idea how to go from here.

I think I know how to find the Kernel after I have the basis, so it is not the focus of this question.

Technically, I use Maple for formatting and quick calculations, but I'm trying to figure out how to do it by hand, so for me to accept an answer, it will have to contain more than just a Maple command that would do what I want, but if there is such a command, it would be appreciated as an extra.

Answer 1

restart;

with(LinearAlgebra):

eqs:=[e1 = x1+x5, x1 = s1+x2+x4, x2 = s2+x3,
      e2+x3 = x7+s3, x7+x4 = x6, x5+x6 = s4+s5]:

vars:=[x1,x2,x3,x4,x5,x6,x7]:

A,B:=GenerateMatrix(eval(eqs,[e1=0,e2=0,s1=0,s2=0,s3=0,s4=0,s5=0]),
                    vars);

           [-1     0     0     0    -1     0     0]  [0]
           [                                      ]  [ ]
           [ 1    -1     0    -1     0     0     0]  [0]
           [                                      ]  [ ]
           [ 0     1    -1     0     0     0     0]  [0]
   A, B := [                                      ], [ ]
           [ 0     0     1     0     0     0    -1]  [0]
           [                                      ]  [ ]
           [ 0     0     0     1     0    -1     1]  [0]
           [                                      ]  [ ]
           [ 0     0     0     0     1     1     0]  [0]

S:=NullSpace(A); # the Kernel

                         [ 0]  [ 1]
                         [  ]  [  ]
                         [ 1]  [ 0]
                         [  ]  [  ]
                         [ 1]  [ 0]
                         [  ]  [  ]
                   S := {[-1], [ 1]}
                         [  ]  [  ]
                         [ 0]  [-1]
                         [  ]  [  ]
                         [ 0]  [ 1]
                         [  ]  [  ]
                         [ 1]  [ 0]

T:=eliminate(Equate(p1*S[1] + p2*S[2], <vars>), [p1,p2])[1];

                   T := {p1 = x7, p2 = x6}

<vars> = eval(p1,T).S[1] + eval(p2,T).S[2];

              [x1]   /     [ 0]\   /     [ 1]\
              [  ]   |     [  ]|   |     [  ]|
              [x2]   |     [ 1]|   |     [ 0]|
              [  ]   |     [  ]|   |     [  ]|
              [x3]   |     [ 1]|   |     [ 0]|
              [  ]   |     [  ]|   |     [  ]|
              [x4] = |x7 . [-1]| + |x6 . [ 1]|
              [  ]   |     [  ]|   |     [  ]|
              [x5]   |     [ 0]|   |     [-1]|
              [  ]   |     [  ]|   |     [  ]|
              [x6]   |     [ 0]|   |     [ 1]|
              [  ]   |     [  ]|   |     [  ]|
              [x7]   \     [ 1]/   \     [ 0]/

I'm not sure what other bits you'd want. If doing it "by hand" would you compute the RREF and then backsubstitute?

LinearSolve(A,B,free=x);

                      [   x[6]    ]
                      [           ]
                      [   x[7]    ]
                      [           ]
                      [   x[7]    ]
                      [           ]
                      [x[6] - x[7]]
                      [           ]
                      [   -x[6]   ]
                      [           ]
                      [   x[6]    ]
                      [           ]
                      [   x[7]    ]

rref:=<ReducedRowEchelonForm(A),<0|0|0|0|0|0|0>>;

             [1    0    0    0    0    -1     0]
             [                                 ]
             [0    1    0    0    0     0    -1]
             [                                 ]
             [0    0    1    0    0     0    -1]
             [                                 ]
     rref := [0    0    0    1    0    -1     1]
             [                                 ]
             [0    0    0    0    1     1     0]
             [                                 ]
             [0    0    0    0    0     0     0]
             [                                 ]
             [0    0    0    0    0     0     0]

BackwardSubstitute(rref,<B,0>,free=x);

                    [     x[2, 1]     ]
                    [                 ]
                    [     x[1, 1]     ]
                    [                 ]
                    [     x[1, 1]     ]
                    [                 ]
                    [x[2, 1] - x[1, 1]]
                    [                 ]
                    [    -x[2, 1]     ]
                    [                 ]
                    [     x[2, 1]     ]
                    [                 ]
                    [     x[1, 1]     ]

An alternate for that eliminate call:

p1*S[1] + p2*S[2];

                        [   p2   ]
                        [        ]
                        [   p1   ]
                        [        ]
                        [   p1   ]
                        [        ]
                        [-p1 + p2]
                        [        ]
                        [  -p2   ]
                        [        ]
                        [   p2   ]
                        [        ]
                        [   p1   ]

Equate( [p1,p2],
        eval( [p1,p2],
              solve( Equate( p1*S[1] + p2*S[2],
                             <x1,x2,x3,x4,x5,x6,x7> ) ) ) );

                   [p1 = x7, p2 = x6]

Answer 2

This is what you obtain so far, \begin{align}x_1&=x_6 \\ x_2&=x_7 \\ x_3&=x_7 \\ x_4&=-x_7+x_6 \\ x_5&=-x_6 \\ x_6&=x_6 \\ x_7&=x_7 \end{align}

We just have to rewrite them in vector form:

$$\begin{bmatrix}x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \\ x_7 \end{bmatrix}=x_6\begin{bmatrix} 1\\ 0\\ 0 \\ 1 \\ -1 \\ 1 \\ 0 \end{bmatrix} + x_7\begin{bmatrix} 0\\ 1\\ 1 \\ -1 \\ 0 \\ 0 \\ 1 \end{bmatrix}$$

Can you read off the basis now?