CoCoA » CoCoALib

Written LinKerByGauss for matrices with entries in a field.

The code uses RankAndGauss(M, ncols) which computes a simple Gaussian reduction (modifying M) only on the first ncols columns. The code was originally written by J Abbott inside LinSolveByGauss.

We can use this function in other functions: I have already modified LinSolveByGauss.
Probably can be easily called by InverseByGauss, RankByGauss, ...

Added LinKer to CoCoA-5 and test.

Added test for CoCoAlib (added into ex-matrix3, written for brother function LinSolve)

Added documentation for CoCoALib and CoCoA-5

Renzo does not like the current interface where the elements of the kernel appear as columns rather than rows. He suggests transposing the result.

In C4 the result was a list of lists; if you applied Mat to the result produced by C4 then you'd get the transpose of the result produced by C5.

In other words LinKer solves M*transposed(x) = 0 for the matrix x.

Think about it. Make a considered decision. Implement & document!

I think that solutions (and kernel) X should be written so that
AX = b and that is what we have chosen for CoCoA-5.

One thing we could add is a couple of functions Rows and Columns which take a matrix and return a list of list. We already have List as in CoCoA-4, but maybe Rows and Columns would be better names?

In summary: the result as it was in CoCoA-4 is currently given by List(Transposed(X)).
Should I add it to the manual?

Non sono d'accordo. Se si guarda la risposta, non si può proprio capire che le soluzioni sono le colonne.
Infatti quello che si vede sono le righe e sembra una risposta sbagliata. Non ha senso anticipare quello che farà l'utente.
Se ha voglia di verificare e se conosce l'algebra lineare, sa che deve fare moltiplicare la matrice di partenza con la trasposta dela matrice delle soluzioni.
Se non lo sa... deve studiare.

Seconda osservazione. LinSolve fornisce UNA SOLA soluzione. Allora il nome non va bene, è ingannevole.
Bisogna chiamare la funzione OneSolution o qualcosa del genere.

Both ways make sense, then I think we should follow the usual rule: "do what other systems do" (and then find a good name for the other choice)

So I'll make a search and list here what others do.

LinSolve (work in progress..)

• Matlab "X = linsolve(A,B) solves the linear system A*X = B (...) The number of rows of A must equal the number of rows of B. If A is m-by-n and B is m-by-k, then X is n-by-k." (infinite solutions???)

• Maple (vertical) vector (infinite solutions???) http://www.maplesoft.com/support/help/Maple/view.aspx?path=Linsolve

• Mathematica (horizontal) vector. "LinearSolve gives one of the possible solutions to this underdetermined set of equations"

• Macaulay2 A, a matrix m by n, b, of size m by r --> x, of size n by r, such that Ax=b
  (one solution) http://www.math.uiuc.edu/Macaulay2/doc/Macaulay2-1.4/share/doc/Macaulay2/Macaulay2Doc/html/_solve.html

LinKer (work in progress..)

• Mathematica list of (horizontal) vectors (function is called "NullSpace")

• Macaulay2 kernel(matrix) --> module (matrix is seen as a homomorphism)

For aesthetics: now changes sign to the LinKer matrix (so that the entries corresponding to the "pivots" are "1" instead of "-1"). Slightly less efficient (changing signs), but more "natural".
Changing tests accordingly.

Add also the syntax LinKer(L) where L is a list of linear polynomials.

What is the status of this issue? Surely more than 30% complete?

Florian suggests that the name LinKerZZ is superfluous, and that LinKer should automatically call LinKerZZ if the matrix is over ZZ.

This seems to be a reasonable suggestion to me. So far we have blurred the distinction between matrices of integers and matrices of rationals: i.e. by default a matrix is constructed over the rationals even if all the entries are integers; one must say explicitly if the matrix is to be over ZZ.

The current impl does allow a matrix over QQ to passed to LinKerZZ; internally LinKerZZ simply clears denoms in each row, then calls the fn which does the actual work (on a vector<vector<BigInt>>).

Possible "ambiguity": a user could be surprised by an automatic choice of LinKer function: let M1 and M2 be two matrices with the same entries (which "happen to be" integers). Let's assume that M1 is over ZZ and M2 is over QQ. So the two matrices look almost identical, yet computing the kernel with LinKer would produce two essentially different results. Mmmmm :-/

John Abbott wrote:

Florian suggests that the name LinKerZZ is superfluous, and that LinKer should automatically call LinKerZZ if the matrix is over ZZ.

This seems to be a reasonable suggestion to me. So far we have blurred the distinction between matrices of integers and matrices of rationals: i.e. by default a matrix is constructed over the rationals even if all the entries are integers; one must say explicitly if the matrix is to be over ZZ.

I see this point of view, but I like to have LinKerZZ because the meaning (and the timings, I suppose) is more explicit.

Maybe could have both:
LinKerZZ(M) defined as a shortcut of LinKer(mat(ZZ,M)) (currently working only for fields)

Or instead we say that LinKer only works on a field, and we make very explicit functions for other cases (syz, I suppose..)
So, instead of NYI, LinKer(mat(ZZ,M)) would give ERR::NotField, suggesting LinKerZZ(M).

The current impl does allow a matrix over QQ to passed to LinKerZZ; internally LinKerZZ simply clears denoms in each row, then calls the fn which does the actual work (on a vector<vector<BigInt>>).

Possible "ambiguity": a user could be surprised by an automatic choice of LinKer function: let M1 and M2 be two matrices with the same entries (which "happen to be" integers). Let's assume that M1 is over ZZ and M2 is over QQ. So the two matrices look almost identical, yet computing the kernel with LinKer would produce two essentially different results. Mmmmm :-/

The fn LinKerZZ is available in my copy of CoCoA-5, but there is no doc.
The doc for CoCoALib seems explicit.

Still need to answer the qn in comment 16: should LinKerZZ really have a separate name?

NOTE: LinKerZZ is made available in BuiltinOneLiners.C

This was originally in issue #122; moving it to here.

What is the difference between LinKer and LinKerBasis?
Is LinKerBasis essentially the same as GetCols(LinKer(..))?

Regarding LinKerZZ, I am now inclined ti think that the name LinKerZZBasis might be clearer...
though one could argue that LinKer anyway produces a basis for the kernel (so there is no point in saying so explicitly in the name).

The source of LinKerBasis looks a bit dodgy.
Given a matrix it does what is expected; but it also works for a list of linear forms. Anna thinks she wrote the code, but does not recall why now.
Anyway, that feature is undocumented, and the impl is "unsafe" because it does not check its args properly.

So what is the correct way to offer a fn to find the "kernel" of a list of polys (or linear forms)?

HINT: LinKerBasis is defined in mat.cpkg around line 600

Why such a long discussion and no resolution?
Can we finish this quickly? Or should we postpone?