combinat::independentSetsOfVectorSpace

combinat::independentSetsOfVectorSpace represents the combinatorial class of the independent sets of a finite dimensional vector space over a finite field.

combinat::independentSetsOfVectorSpace::count(finite field K, nonnegative integer n, nonnegative integer k)

Returns the number of independent sets of size k in a K-vector space of dimension n.

combinat::independentSetsOfVectorSpace::generator(finite field K, nonnegative integer n, nonnegative integer k)

Returns a generator for the independent sets of size k in a K-vector space of dimension n.

Returns a generator for all the vectors in the linear span of S, starting from zero. The list should be non-empty (otherwise the system cannot guess in which vector space zero belongs to).

Let be the finite field of size , and be the canonical -vector space of dimension . This space has independent set of size , non-zero vectors, bases, and no independent set of size or more:

Z2 := Dom::IntegerMod(2):

n := 2:

combinat::independentSetsOfVectorSpace::count(Z2, n, k) $ k = 0..3

Here is the first basis of :

g := combinat::independentSetsOfVectorSpace::generator(Z2, n, n):

M := g()

For the sake of readability in the following examples, we define the following pretty-printing function:

printMatrix := M -> output::asciiArt::fromArray(expr(M), Packed):

printMatrix(M)

Now, here are all the non zero vectors of :

map(combinat::independentSetsOfVectorSpace(Z2, n, 1), printMatrix)

0 1 1

[1, 0, 1]

and all the bases of :

map(combinat::independentSetsOfVectorSpace(Z2, n, 2), printMatrix)

01 01 10 11 10 11

[10, 11, 01, 01, 11, 10]

To conclude, here are all the bases of :

map(combinat::independentSetsOfVectorSpace(Z2, 3, 3), printMatrix)

-- 001 001 001 001 010 010 011 011 010 010 011 011 001 001 001 001 010 010 011 011 010 010 011

| 010, 010, 011, 011, 001, 001, 001, 001, 011, 011, 010, 010, 010, 010, 011, 011, 001, 001, 001, 001, 011, 011, 010,

-- 100 101 100 101 100 101 100 101 100 101 100 101 110 111 111 110 110 111 111 110 110 111 111

011 001 001 001 001 010 010 011 011 010 010 011 011 001 001 001 001 010 010 011 011 010 010

010, 100, 100, 101, 101, 100, 101, 100, 101, 100, 101, 100, 101, 110, 110, 111, 111, 110, 111, 111, 110, 110, 111,

110 010 011 010 011 001 001 001 001 011 011 010 010 010 011 010 011 001 001 001 001 011 011

011 011 001 001 001 001 010 010 011 011 010 010 011 011 001 001 001 001 010 010 011 011 010

111, 110, 100, 100, 101, 101, 100, 101, 100, 101, 100, 101, 100, 101, 110, 110, 111, 111, 110, 111, 111, 110, 110,

010 010 110 111 111 110 101 100 101 100 111 110 110 111 100 101 101 100 111 110 110 111 101

010 011 011 100 100 101 101 100 100 101 101 100 100 101 101 110 110 111 111 110 110 111 111

111, 111, 110, 001, 001, 001, 001, 010, 011, 010, 011, 010, 011, 010, 011, 001, 001, 001, 001, 010, 011, 010, 011,

100 101 100 010 011 010 011 001 001 001 001 011 010 011 010 010 011 010 011 001 001 001 001

110 110 111 111 100 100 101 101 100 100 101 101 100 100 101 101 110 110 111 111 110 110 111

010, 011, 010, 011, 001, 001, 001, 001, 010, 011, 010, 011, 010, 011, 010, 011, 001, 001, 001, 001, 010, 011, 010,

011 010 011 010 110 111 111 110 101 101 100 100 111 110 110 111 100 101 101 100 111 111 110

111 110 110 111 111 100 100 101 101 100 100 101 101 100 100 101 101 110 110 111 111 110 110

011, 010, 011, 010, 011, 101, 101, 100, 100, 110, 111, 111, 110, 110, 111, 111, 110, 111, 111, 110, 110, 100, 101,

110 101 100 100 101 010 011 010 011 001 001 001 001 011 010 011 010 010 011 010 011 001 001

111 111 110 110 111 111 100 100 101 101 100 100 101 101 100 100 101 101 110 110 111 111 110

101, 100, 100, 101, 101, 100, 101, 101, 100, 100, 110, 111, 111, 110, 110, 111, 111, 110, 111, 111, 110, 110, 100,

001 001 011 010 011 010 110 111 111 110 101 101 100 100 111 110 110 111 100 101 101 100 111

110 111 111 110 110 111 111 --

101, 101, 100, 100, 101, 101, 100 |

111 110 110 101 100 100 101 --