# Linear combination of elements of sets- finding "basis" and implementation in Python/SAGE

I actually have a question concerning both linear algebra and SAGE (or just Python) implementation.

Consider for example set with $6$ elements $a,b,c,d,e,f$ and I know some relations that hold between them, for example,

$$a+b+c=0,\quad a+d-e=0,\quad a+b+d=0$$

If element is not in the list of relations it is consider as an element of the basis (since it is independent), so $f$ is in the basis. We also get from here $c=d$, $a=-b-c$, $e=-b$. So our basis is $b,c,f$.

I would like to know how do I implement this. I considered representing elements of the set as elements of standard basis and i considered matrix which represent these linear combination: $$\begin{bmatrix} 1 & 1 & 1 & 0 & 0 & 0 \\ 1&0&0&1&-1&0\\1&1&0&1&0&0 \end{bmatrix}$$ Then I took its right kernel and got this basis matrix: $$\begin{bmatrix} 1 & 0 & -1 & -1 & 0 & 0 \\ 0&1&-1&-1&-1&0\\0&0&0&0&0&1 \end{bmatrix}$$

From here it is not hard to see that i can take $\{a,b,f\}$ but how to get representation of other elements using basis elements? I think I am missing something, and I think my main problem is that I don't know pseudocode which could work here?

The right kernel matrix is the right thing to look at. Pivots tell you which independent variables to select; other columns express the other variables as linear combinations of the independent ones.

Below we illustrate this with SageMath.

Input the matrix.

sage: m = matrix(ZZ, [[1, 1, 1, 0,  0, 0],
....:                 [1, 0, 0, 1, -1, 0],
....:                 [1, 1, 0, 1,  0, 0]])
....:
sage: m
[ 1  1  1  0  0  0]
[ 1  0  0  1 -1  0]
[ 1  1  0  1  0  0]


Compute the right kernel and its matrix.

sage: m.right_kernel()
Free module of degree 6 and rank 3 over Integer Ring
Echelon basis matrix:
[ 1  0 -1 -1  0  0]
[ 0  1 -1 -1 -1  0]
[ 0  0  0  0  0  1]
sage: k = m.right_kernel().matrix()
sage: k
[ 1  0 -1 -1  0  0]
[ 0  1 -1 -1 -1  0]
[ 0  0  0  0  0  1]


The first, second and last columns say $a$, $b$, $f$ are the independent variables.

The third, fourth and fifth columns say $c = (-1)a + (-1)b$, $d = (-1)a + (-1)b$, $e = (-1)b$.

To get these equations in Sage, name the variables.

sage: vars = SR.var('a b c d e f')
sage: vars
(a, b, c, d, e, f)


Detect the pivots and deduce the nonpivots.

sage: pivots = k.pivots()
sage: pivots
(0, 1, 5)
sage: nonpivots = [j for j in range(k.ncols()) if j not in pivots]
sage: nonpivots
[2, 3, 4]


Deduce the independent variables.

sage: indeps = vector([vars[j] for j in pivots])
sage: indeps
(a, b, f)


Finally, get the relations.

sage: relations = [vars[j] == k.column(j) * indeps for j in nonpivots]
sage: relations
[c == -a - b, d == -a - b, e == -b]