1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.