# Road map: Matrix normal forms & ring traits

We will use the following definition (taken from Storjohann, "Algorithms for Matrix normal forms").


(Later in the thesis, he also defines "Smith form", which is what one would expect with diagonal entries not unique.)

Claus & Tommy agree that

> **We want to use these definitions.**

(We will ignore the "minimal" versions for now.)

## Normal form methods

### What we have currently:

I am neglecting all the `*_with_transformation` versions.

| Function | Output |
|----------|--------|
| `echelon_form(A::MatElem{<:FieldElem}; reduced::Bool = true)` | An echelon form of `A`, reduced or not.
| `hermite_form(A::MatElem{<:RingElem}; reduced::true, modulus)` | A "Hermite normal form" of `A`, reduced or not.
| `howell_form(A::MatElem{<:RingElem}; reduced::Bool = true)` | A "Howell normal form" of `A`, reduced or not.

Note that the `reduced` keyword arguments do not make sense anymore with *the* definition.

### What we want:

Ideally, we end up with the following (`new` only added to distinguish from the old ones) methods, which are implemented generically using the new ring traits/discussed below:

| Function | Output |
|----------|--------|
| `new_echelon_form(A::MatElem{<:RingElem})` | An echelon normal form.
| `new_hermite_form(A::MatElem{<:RingElem})` | A Hermite normal form.
| `new_howell_form(A::MatElem{<:RingElem})` | A Howell normal form.
| `new_weak_howell_form(A::MatElem{<:RingElem})` | A weak Howell normal form.

Alternatively, add the `weak` as a keyword argument.

For backwards compatibility, for the user-facing `echelon_form/hermite_form/howell_form` methods we have to keep and honor the `reduced` flag (as good as we can).

Assume we have the `new` functions in place and they do exactly what the definition say. Then the proposal would be to have:

echelon_form(A::MatElem{<:FieldElem}; reduced = true) = !reduce ? new_echelon_form(A) : new_hermite_form(A)

We have to do this shenanigan, since currently the `echelon_form(A)` is always reduced for matrices over fields and we do not want to break this.

In general we will have:

echelon_form(A::MatElem{<:RingElem}; reduced = false) = !reduced ? new_echelon_form(A) : new_hermite_Form(A)

hermite_form(A::MatElem{<:RingElem}; reduced = false) = !reduced ?
new_echelon_form(A) : new_hermite_form(A)

In addition, we remove the `reduced` from the documentation and let the methods cross-reference each other.

## Ring traits

We need a system to let the system know which algorithmic properties a ring has.

Just collecting some random ideas and remarks here:

- To get a echelon form over a ring, one needs a K-Hermite ring (https://en.wikipedia.org/wiki/Hermite_ring.). This are exactly the rings, where one can transform a 2x1 matrix into upper triangular form.
- Bézout domains/PIDs are K-Hermite
- PIRs are not necessarily K-Hermite
- Algorithmically, the K-Hermite property is (almost) the `_gcdxx` property. The `_gcdxx` property always corresponds to a unimodular transformation.
- Thus, for the echelon form and Hermite form, the only question which traits/properties is whether a ring supports (a) _gcdxx (b) "uniqueness"

### Euclidean rings?

- Euclidean rings are K-Hermite (even in the non-domain case)
- `divrem` and (`euclid`?) note: `divrem` can be non-unique
- we can derive `gcd`, `gcdx` and `_gcdxx` from `divrem` using the extended Euclidean algorithm.
- `canonical_unit`?

### Principal ideal rings?
- we can have this trait, but to get something useful out of this for matrix normal forms, `_gcdxx` needs to be implemented. Needs `canonical_unit`?

### Principal ideal domains?
- for matrix normal forms, only finitely generated ideals are considered, but then one should better look at Bézout domains

### Bezout domain
- domains where finitely generated ideals are principal
- algorithmically these are the rings that admit `gcdx`, which can be used to derive `_gcdxx`

### Fields

- clear.