Integer Linear DependenceΒΆ

The elements v1,...,vN of a module M over a ring R are said to be linearly dependent over R if there exist c1,...,cN in R, not all 0, such that c1 v1 + ... cN vNn = 0. If such ci’s exist, they form what is called a linear dependence relation over R for the vi’s.

The package IntegerLinearDependence provides functions for testing whether some elements of a module over the integers are linearly dependent over the integers, and to find the linear dependence relations, if any.

Consider the domain of two by two square matrices with integer entries.

M := SQMATRIX(2,INT)
  SquareMatrix(2,Integer)
                    Type: Domain

Now create three such matrices.

m1: M := squareMatrix matrix [ [1, 2], [0, -1] ]
   +1   2 +
   |      |
   +0  - 1+
                    Type: SquareMatrix(2,Integer)

m2: M := squareMatrix matrix [ [2, 3], [1, -2] ]
  +2   3 +
  |      |
  +1  - 2+
                    Type: SquareMatrix(2,Integer)

m3: M := squareMatrix matrix [ [3, 4], [2, -3] ]
  +3   4 +
  |      |
  +2  - 3+
                    Type: SquareMatrix(2,Integer)

This tells you whether m1, m2 and m3 are linearly dependent over the integers.

linearlyDependentOverZ? vector [m1, m2, m3]
  true
                    Type: Boolean

Since they are linearly dependent, you can ask for the dependence relation.

c := linearDependenceOverZ vector [m1, m2, m3]
  [1,- 2,1]
                    Type: Union(Vector Integer,...)

This means that the following linear combination should be 0.

c.1 * m1 + c.2 * m2 + c.3 * m3
  +0  0+
  |    |
  +0  0+
                    Type: SquareMatrix(2,Integer)

When a given set of elements are linearly dependent over R, this also means that at least one of them can be rewritten as a linear combination of the others with coefficients in the quotient field of R.

To express a given element in terms of other elements, use the operation solveLinearlyOverQ.

solveLinearlyOverQ(vector [m1, m3], m2)
   1 1
  [-,-]
   2 2
                    Type: Union(Vector Fraction Integer,...)

See Also:

  • )show IntegerLinearDependence

Table Of Contents

This Page