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.

@ThePirateBay Sorry about that, I didn't realize the commands available — Kaito Kid, Nov 25 '17 at 18:07
See this answer for a detailed description of how to read a kernel basis from a RREF matrix. Note that the matrix in your question isn’t in RREF yet. — amd, Nov 25 '17 at 18:13

score 1 · Answer 1 · answered Nov 25 '17 at 18:07

1

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?

answered Nov 25 '17 at 18:07

Siong Thye Goh

149,520
20
88
149

It's that easy? I guess all the googling i had done had me reach ridiculously more advanced topics, because it was pages and pages of math that I couldn't figure out how to use... – Kaito Kid Nov 25 '17 at 18:49
i can't do advanced maths, so I guess it has to be easy =). Do check that they are indeed a basis if you just started the topic to build your foundation. – Siong Thye Goh Nov 25 '17 at 18:52

score 1 · Accepted Answer · answered Nov 29 '17 at 19:46

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]

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

2 Answers2