A Standard Form in (some) Free Fields: How to construct Minimal Linear Representations
Konrad Schrempf

Research ArticleOpen Access

[1]Konrad Schrempf
[1]University of Vienna, Faculty for Mathematics,
  Oskar-Morgenstern-Platz 1, 1090 Wien, Austria.
  E-mail: math@versibilitas.at,
  ORCID 0000-0001-8509-009X
A Standard Form in Free Fields





A Standard Form in (some) Free Fields:

  How to construct Minimal Linear Representations
    Konrad Schrempf
  [Contact: math@versibilitas.at (Konrad Schrempf),
    <https://orcid.org/0000-0001-8509-009X>,
    Universität Wien, Fakultät für Mathematik,
    Oskar-Morgenstern-Platz 1, 1090 Wien, Austria.
    ]
  https://orcid.org/0000-0001-8509-009X
  
    < g r a p h i c s >

  
    Jan 2018
===================================================================================================================================================================================================================================================================================================




We describe a standard form for the elements in
the universal field of fractions of free associative
algebras (over a commutative field).
It is a special version of the normal form
provided by Cohn and Reutenauer
and enables the use of linear algebra techniques for the
construction of minimal linear representations (in standard form)
for the sum and the product of two elements (given in standard form).
This completes “minimal” arithmetic in free fields
since “minimal” constructions for the inverse
are already known.
The applications are wide: linear algebra (over the
free field), rational identities, computing the
left gcd of two non-commutative polynomials, etc.


A Standard Form in (some) Free Fields:

  How to construct Minimal Linear Representations
    Konrad Schrempf
  [Contact: math@versibilitas.at (Konrad Schrempf),
    <https://orcid.org/0000-0001-8509-009X>,
    Universität Wien, Fakultät für Mathematik,
    Oskar-Morgenstern-Platz 1, 1090 Wien, Austria.
    ]
  https://orcid.org/0000-0001-8509-009X
  
    < g r a p h i c s >

  
    Jan 2018
===================================================================================================================================================================================================================================================================================================



 
 
  Open Mathematics
DOI
  1
  ..
  ..
  ..

  2017
  1
Keywords and 2020 Mathematics Subject Classification.
Free associative algebra,
minimal linear representation, admissible linear system,
left greatest common divisor, non-commutative polynomials;
Primary 16K40, 16Z05; Secondary 16G99, 16S85, 15A22








§ INTRODUCTION


While the embedding of the integers into the field of
rational numbers is easy, that of non-commutative rings
(into skew fields) is not that straight forward even in special
cases <cit.>
. After Ore's construction it took almost forty years
and many contributors to develop a more general theory
<cit.>
. The embedding of the free associative algebra
(over a commutative field) into a ring of quotients
(non-commutative localization) is even classified as
“ugly” <cit.>
.

On the other hand there are many parallels between the
ring of integers and the free associative algebra,
for example, both have a distributive factor lattice
(DFL) <cit.>
 or
<cit.>
. And, starting from the normal form (minimal linear representation)
of Cohn and Reutenauer
<cit.>
 of an element in the universal field of fractions
(of the free associative algebra),
we will formulate a standard form which can
be seen as a “generalized” fraction.
As a reminiscence to the work with “classical”
fractions (we learn at school) we call them
briefly “free fractions” 
<cit.>
.

For an introduction to free fields we recommend
<cit.>
 and with respect to linear representations
in particular <cit.>
. For details we refer to 
<cit.>
 or 
<cit.>
.
Since this work is only one part in a series,
further information and references can be found
in <cit.>
 (linear word problem, minimal inverse),
<cit.>
 (polynomial factorization) and
<cit.>
 (general factorization theory).

The main idea of the standard form is simple:
instead of viewing the system matrix of a linear representation
as a single “block” we transform it into a
block upper triangular form with smaller diagonal blocks.
If these pivot blocks are small enough (called “refined”),
linear
techniques can be used to eliminate all superfluous block rows
or columns, that is, solving “local” word problems,
in the “sum” or the “product” of two linear
representations, eventually yielding a minimal
linear representation.
This can be accomplished with complexity (dn^5)
for an alphabet with d letters and a linear representation
of dimension n with pivot blocks of size √(n).
For the refinement of pivot blocks we need to solve
—at least in general— systems of polynomial equations.
However linear techniques can be used in some cases
to “break” big pivot blocks into smaller ones
(see Remark <ref>).

Since almost all here is rather elementary it should be noted
that it needs some effort to dig deep enough into the theory
in the background (in particular that of Cohn) to really
understand what is going on. Despite of the main results
(mentioned in the following) there is only one non-trivial
observation (formulated in Theorem <ref>):
A given refined linear representation 
is minimal if none of the linear systems of equations
for block row or column minimization has a solution.
(In the general non-refined case nothing can be said about minimality if there
is no more “linear” minimization step possible.)

In other words: while the normal form 
<cit.>
 “linearizes” the word problem in free fields 
<cit.>
, the standard form
“linearizes” (the minimization of) the sum and the
product (of two elements).


Section <ref> provides the basic setup
and Section <ref> summarizes several (different)
constructions of linear representations for the rational
operations (sum, product and inverse).
In a first reading only the first two propositions are
important.
In Section <ref> we develop the notation
to be able to formulate a standard form
in Definition <ref>.
The main result is then Theorem <ref>
(or Algorithm <ref>)
for the minimization in Section <ref>.
And finally, in Section <ref>,
some applications are mentioned.
Example <ref> can also serve as an
introduction for the work (by hand)
with linear representations.

The intention of this paper is to be independent
of the other three papers in this series (about
the free field) as far as possible and leave it
to the reader, for example,
to interpret a standard form of the
inverse of a polynomial as its factorization
(into irreducible elements).
Although the idea for minimizing “polynomial” linear representations
is similar to that in Section <ref>,
<cit.>
 is only a very special case of Algorithm <ref>
and the “refinement” in the former case is trivial.

Beside the algebraic approach presented here
there are analytical methods for solving the word problem
(or testing rational identities like in Example <ref>)
in polynomial time by plugging in “sufficiently large” matrices
<cit.>
. Closely related to linear representations
are realizations which can be
“cut down” by plugging in operators
<cit.>
 or “reduced” by plugging in matrices
<cit.>
.
Yet another point of view is from invariant subspaces
<cit.>
.

Once the rich structure of Cohn and Reutenauer's
normal form becomes “visible”, a lot can
be done, transforming the rather abstract free field
into an applied.
One can use non-commutative “rational functions” just like
rational numbers respectively “free fractions” just like
“classical” fractions …





§ PRELIMINARIES


We represent elements (in free fields) by
admissible linear systems (Definition <ref>),
which are just a special form of linear representations
(Definition <ref>). Rational operations
(scalar multiplication, addition, multiplication, inverse) can be
easily formulated in terms of linear representations
(Proposition <ref>).




The set of the natural numbers is denoted by = { 1,2,…}.
Zero entries in matrices are usually replaced by (lower) dots
to emphasize the structure of the non-zero entries
unless they result from transformations where there
were possibly non-zero entries before.
We denote by I_n the identity matrix
and _n the permutation matrix that reverses the order
of rows/columns (of size n)
respectively I and  if the size is clear from the context.


Let K be a commutative field,
K its algebraic closure and
X = { x_1, x_2, …, x_d} be a finite (non-empty) alphabet.
KX denotes the free associative
algebra (or free K-algebra)
and F = KX its universal field of
fractions (or “free field”) 
<cit.>
. An element in KX is called (non-commutative or nc)
polynomial.
In our examples the alphabet is usually X={x,y,z}.
Including the algebra of nc rational series
we have the following chain of inclusions:

K⊊KX
  ⊊K^rat⟨⟨X⟩⟩⊊KX =: F.

The free monoid X^* generated by X
is the set of all finite words
x_i_1 x_i_2⋯ x_i_n with i_k ∈{ 1,2,…, d }.
An element of the alphabet is called letter,
one of the free monoid word.
The multiplication on X^* is the concatenation
of words, that is,
(x_i_1⋯ x_i_m)· (x_j_1⋯ x_j_n)
= x_i_1⋯ x_i_m x_j_1⋯ x_j_n,
with neutral element 1, the empty word.
For detailed introductions see
<cit.>
 or
<cit.>
.


Given a matrix A ∈KX^n × n, the inner rank
of A is the smallest number m∈
such that there exists a factorization
A = T U with T ∈KX^n × m and
U ∈KX^m × n.
The matrix A is called full if m = n,
non-full otherwise.
It is called hollow if it contains a zero submatrix of size
k × l with k+l>n.



Two matrices A and B over KX (of the same size)
are called associated over a subring R⊆KX 
if there exist
invertible matrices P,Q over R such that
A = P B Q. A and B (not necessarily of the same size)
are called stably associated
if A⊕ I_p and B⊕ I_q are associated for some unit
matrices I_p and I_q.
Here by C ⊕ D we denote the diagonal sum
[[ C .; . D ]].



A linear square matrix over KX
which is not full is associated over K to a linear
hollow matrix.





Let f ∈F.
A linear representation of f is a triple π_f = (u,A,v) with
u ∈K^1 × n, full
A = A_0 ⊗ 1 + A_1 ⊗ x_1 + …
+ A_d ⊗ x_d, that is, A is invertible over F,
∀ ℓ  A_ℓ∈K^n× n,
v ∈K^n× 1 
and f = u A v.
The dimension of π_f is (u,A,v) = n.
It is called minimal if A has the smallest possible dimension
among all linear representations of f.
The “empty” representation π = (,,) is
the minimal one of 0 ∈F with π = 0.
Let f ∈F and π be a minimal
linear representation of f.
Then the rank of f is
defined as f = π.




Cohn and Reutenauer define linear representations
slightly more general, namely f = c + u A v with
possibly non-zero c ∈K and call it
pure when c=0. Two linear representations are called
equivalent if they represent the same element
<cit.>
.
Two (pure) linear representations (u,A,v) and (ũ,Ã,ṽ)
of dimension n are called isomorphic if there exist invertible matrices
P,Q ∈K^n × n
such that u = ũQ, A = P Ã Q and v=Pṽ
<cit.>
.



If π' = (u',A',v') and π”=(u”,A”,v”) are equivalent
(pure) linear representations, of which the first is minimal,
then the second is isomorphic to a representation π = (u,A,v)
which has the block decomposition

u =
[  . u'  * ],  A =
[  *  *  *;  . A'  *;  .  .  * ]
  and  v = 
[  *; v';  . ].




In principle, given π” of dimension n,
one can look for invertible matrices P,Q
such that Pπ”Q = (u”Q, PA”Q, Pv”)
has the form of π to minimize π”.
However, for an alphabet with d letters and
a lower left block of zeros of size k × (n-k) we
would get (d+1)k(n-k) +k polynomial equations
with at most quadratic terms and two equations of
degree n (to ensure invertibility of the transformation matrices)
in 2n^2 commuting unknowns. This is already
rather challenging for n=5. The goal is therefore
to use linear techniques as far as possible.





Let π=(u,A,v) be a linear representation of f ∈F
of dimension n.
The families ( s_1, s_2, …, s_n )⊆F
with s_i = (A v)_i
and ( t_1, t_2, …, t_n )⊆F
with t_j = (u A)_j
are called left family and right family respectively.
L(π) = { s_1, s_2, …, s_n } and
R(π) = { t_1, t_2, …, t_n }
denote their linear spans (over K).





A representation π=(u,A,v) of an element f ∈F
is minimal if and only if both, the left family
and the right family are K-linearly independent.
In this case, L(π) and R(π) depend only on f.



An element f ∈F is called of type (1,*)
(respectively (0,*)) if 1 ∈ R(f), that is, 1 ∈ R(π)
for some minimal linear representation π of f,
(respectively 1 ∉ R(f)).
It is called of type (*,1) (respectively (*,0))
if 1 ∈ L(f) (respectively 1 ∉ L(f)).
Both subtypes can be combined.



The following definition is a special case
of Cohn's more general admissible systems
<cit.>
 and the slightly more general linear representations
<cit.>
.



A linear representation A = (u,A,v) of f ∈F
is called admissible linear system (ALS) for f
if u=e_1=[1,0,…,0].
The element f is then the first component
of the (unique) solution vector s = A v.
An ALS is also written as A s = v,
or if v = [0,…,0,λ] as (1,A,λ).
Given a linear representation A = (u,A,v)
of dimension n of f ∈F
and invertible matrices P,Q ∈K^n× n,
the transformed PAQ = (uQ, PAQ, Pv) is
again a linear representation (of f).
If A is an ALS,
the transformation (P,Q) is called
admissible if the first row of Q is e_1 = [1,0,…,0].



The left family (A v)_i (respectively the right family (u A)_j)
and the solution vector s of As = v (respectively t of u = tA)
are used synonymously.


Transformations can be done by elementary row- and column operations,
explained in detail in
<cit.>
. For further remarks and connections to the related concepts
of linearization and realization see
<cit.>
. 

For elements in the free associative algebra KX
a special form (with an upper unitriangular system matrix) can be used.
It plays a crucial role in the factorization of polynomials
because it allows to formulate a minimal polynomial multiplication
(Proposition <ref>) and upper unitriangular
transformation matrices (invertible by definition) suffice to find
all possible factors (up to trivial units).
For details we refer to 
<cit.>
.


While it was intended in 
<cit.>
 to derive a “better” standard form including knowledge about
the factorization it turned out later that this is not that easy in the
general case because of the necessity to distinguish several cases in
the multiplication 
<cit.>
. The term “pre-standard ALS” (for polynomials) is now replaced
by polynomial ALS (which is just a special form of a refined ALS,
Section <ref>). And a minimal polynomial ALS
is already in standard form.
Especially to avoid confusion with special transformation matrices
for the factorization everything is put into a uniform context
in <cit.>
. For an overview see also 
<cit.>
.
There are only some minor changes in the formulation of results and proofs
necessary, for example to construct the product in
<cit.>
 using λ_2/λA_1 and
λ/λ_2A_2.



An ALS A = (u,A,v) of dimension n
with system matrix A = (a_ij)
for a non-zero polynomial 0 ≠ p ∈KX 
is called
polynomial, if


  (1) v = [0,…,0,λ] for some λ∈K and

  (2) a_ii=1 for i=1,2,…, n and a_ij=0 for i>j,
  that is, A is upper triangular.

An admissible transformation (P,Q) for an ALS A
is called polynomial if it has the form

(P,Q) = (
[         1     α_1,2         …   α_1,n-1     α_1,n;                   ⋱         ⋱         ⋮         ⋮;                             1 α_n-2,n-1   α_n-2,n;                                       1   α_n-1,n;                                                 1 ],
[       1       0       0       …       0;               1   β_2,3       …   β_2,n;                       1       ⋱       ⋮;                               ⋱ β_n-1,n;                                       1;         ]
).

If additionally α_1,n = α_2,n = … = α_n-1,n = 0
then (P,Q) is called polynomial factorization transformation.




Let M = M_1 ⊗ x_1 + … + M_d ⊗ x_d
with M_i ∈K^n × n for some n∈.
An element in F is called regular
if it has a linear representation (u,A,v) with A = I - M,
that is, A_0 = I in Definition <ref>,
or equivalently, if A_0 is regular (invertible).





§ RATIONAL OPERATIONS


Usually we want to construct minimal admissible linear
systems (out of minimal ones), that is,
perform “minimal” rational operations.
Minimal scalar multiplication is trivial.
In some special cases minimal multiplication
or even minimal addition (if two elements are disjoint
<cit.>
)
can be formulated (Proposition <ref> or
<cit.>
 and 
<cit.>
). For the minimal inverse we have to distinguish four
cases, which are summarized in Theorem <ref>.
In general we have to minimize admissible linear systems.
This will be the main goal of the following sections.


Let k ∈ and f= x_i_1 x_i_2⋯ x_i_k be a monomial in
KX⊆KX.
Then

A = (
[ 1 . ⋯ . ],
[      1 -x_i_1;             1 -x_i_2;                    ⋱      ⋱;                           1 -x_i_k;                                  1 ],
[ .; .; ⋮; .; 1 ]
)

is a minimal polynomial ALS of dimension (A) = k+1.



Let 0≠ f,g ∈F be given by the
admissible linear systems A_f = (u_f, A_f, v_f)
and A_g = (u_g, A_g, v_g) respectively
and let 0≠μ∈K.
Then admissible linear systems for the rational operations
can be obtained as follows:

The scalar multiplication
μ f is given by

μA_f =
( u_f, A_f, μv_f ).

The sum f + g is given by

A_f + A_g =
(
[ u_f   . ],
[         A_f -A_f u_fu_g;           .         A_g ], 
[ v_f; v_g ]
).

The product fg is given by

A_f ·A_g =
(
[ u_f   . ],
[      A_f -v_f u_g;        .      A_g ],
[   .; v_g ]
).

And the inverse f is given by

A_f=
(
[ 1 . ],
[ -v_f  A_f;    .  u_f ],
[ .; 1 ]
).



Since we need alternative constructions
(to that in Proposition <ref>)
for the product we state them here
in Propositions <ref> and <ref>.
Before, we need some technical results from
<cit.>
 and
<cit.>
. However these are rearranged such that similarities become
more obvious and the flexibility in applications is increased.
In particular one can proof Lemma <ref> by applying
Lemma <ref>,
see
<cit.>
.


Let A = (u,A,v) be an ALS
of dimension n ≥ 1 with K-linearly independent
left family s = A v and
B = B_0 ⊗ 1 + B_1 ⊗ x_1 + … + B_d ⊗ x_d
with B_ℓ∈K^m× n, such that
B s = 0. Then there exists a (unique) T ∈K^m × n
such that B = TA.





Let A = (u,A,v) be a minimal ALS
with A =n ≥ 2 and 1∈ L(A). Then there
exists an admissible transformation (P,Q) such that
the last row of PAQ is [0,…,0,1]
and Pv = [0,…,0,λ]
for some λ∈K.




Let A = (u,A,v) be a minimal ALS
with A = n ≥ 2 and 1∈ R(A). Then there
exists an admissible transformation (P,Q) such that
the first column of PAQ is [1,0,…,0]
and Pv = [0,…,0,λ]
for some λ∈K.



If g is of type (*,1) then, by Lemma <ref>,
each minimal ALS for g can be transformed into one
with the last row of the form [0,…,0,1].
If g is of type (1,*) then, by Lemma <ref>,
each minimal ALS for g can be transformed into one
with the first column of the form [1,0,…,0].
This can be done by linear techniques,
see the remark before
<cit.>
.





Since p ∈KX is of type (1,1),
both constructions
can be used for the minimal polynomial multiplication
(Proposition <ref>).
The alternative proof in 
<cit.>
 relies in particular on Lemma <ref>.
One could call the multiplication from Proposition <ref>
type (*,*). For a discussion of minimality of
different types of multiplication we refer to
<cit.>
.



Let f,g∈F∖K be given by the
admissible linear systems
A_f = (u_f, A_f, v_f) = (1,A_f,λ_f) of dimension n_f
of the form

A_f = (
[ 1 . . ],
[  a b'  b; a'  B b”;  .  .  1 ],
[   .;   .; λ_f ]
)

and A_g = (u_g, A_g, v_g) = (1,A_g,λ_g)
of dimension n_g respectively.
Then an ALS for fg of dimension n = n_f + n_g - 1 is given by

A = (
[ 1 . . ],
[          a         b'  λ_f b u_g;         a'          B λ_f b” u_g;          .          .        A_g ],
[   .;   .; v_g ]
).





Let f,g∈F∖K be given by the
admissible linear systems A_f = (u_f, A_f, v_f) = (1, A_f, λ_f) 
of dimension n_f and
A_g = (u_g, A_g, v_g) = (1, A_g, λ_g)
of dimension n_g of the form

A_g = (
[ 1 . . ],
[  1 b'  b;  .  B b”;  . c'  c ],
[   .;   .; λ_g ]
)

respectively.
Then an ALS for fg of dimension n = n_f + n_g -1 is given by

A = (
[ u_f   .   . ],
[          A_f e_n_f λ_f b'  e_n_f λ_f b;            .            B           b”;            .           c'            c ],
[   .;   .; λ_g ]
).





Notice that the transformation in the following lemma is not
necessarily admissible. However, except for n=2 (which can be
treated by permuting the last two elements in the left family),
it can be chosen such that it is admissible.
The proof is similar to that of 
<cit.>
.




Let A = (u,A,v) be an ALS of dimension n≥ 2
with v = [0,…,0,λ] and
K-linearly dependent left family s=A v.
Let m ∈{ 2, 3, …, n } be the minimal index
such that the left subfamily s = (A v)_i=m^n
is K-linearly independent.
Let A = (a_ij) and assume that a_ii=1 for 1 ≤ i ≤ m
and a_ij=0 for j < i ≤ m (upper triangular m × m block)
and a_ij=0 for j ≤ m < i (lower left zero block of size (n-m) × m).
Then there exists matrices T,U ∈K^1 × (n+1-m)
such that

U + (a_m-1,j)_j=m^n - T(a_ij)_i,j=m^n  =
[ 0 … 0 ]
  and  T(v_i)_i=m^n = 0.





Let p ∈KX∖K and
g ∈F∖K
be given by the minimal admissible linear systems
A_p = (u_p, A_p, v_p) and A_g = (u_g, A_g, v_g)
of dimension n_p and n_g respectively
with 1 ∈ R(g).
Then the left family of the ALS A = (u,A,v)
for pg of dimension n = n_p + n_g -1 from
Proposition <ref> is K-linearly independent.




Let 0 p,q ∈KX be given by the
minimal polynomial admissible linear systems
A_p = (1, A_p, λ_p) and
A_q = (1, A_q, λ_q) of dimension n_p,n_q ≥ 2 respectively.
Then the ALS A from Proposition <ref> for pq
is minimal of dimension n = n_p + n_q - 1.




Let f ∈F∖K be given by
the minimal admissible linear system A = (u, A, v)
of dimension n.
Then a minimal ALS for f is given
in the following way:

f of type (1,1) yields f of type (0,0) with (A') = n-1:

A'=(1, 
[ -λb”   -B;  -λb - b' ],
1 )   for  A = (1, 
[  1 b'  b;  .  B b”;  .  .  1 ],
λ).

f of type (1,0) yields f of type (1,0) with (A') = n:

A' = (1,
[        1  - 1/λ c - 1/λ c';        .      -b”       -B;        .       -b      -b' ],
1 )
  for  A = (1,
[  1 b'  b;  .  B b”;  . c'  c ],
λ).

f of type (0,1) yields f of type (0,1) with (A') = n:

A' = ( 1,
[ -λb”   -B  -a';  -λb  -b'   -a;    .    .    1 ],
1 )
  for  A = (1,
[  a b'  b; a'  B b”;  .  .  1 ],
λ).

f of type (0,0) yields f of type (1,1) with (A') = n+1:

A' = (1,
[  v -A;  .  u ],
1 ).

(Recall that the permutation matrix  reverses the order of rows/columns.)



Let p ∈KX with p = n ≥ 2.
Then (p) = n-1.



Let 0 ≠ f ∈F.
Then f ∈K if and only if (f) = (f) = 1.




Notice that n≥ 2 for type (1,1), (1,0) and (0,1).
The block B is always square of size n-2.
For n=2 the system matrix of A is


  * [[ 1 b; . 1 ]]
  for type (1,1),

  * [[ 1 b; . c ]]
  for type (1,0) and

  * [[ a b; . 1 ]]
  for type (0,1).







§ A STANDARD FORM


After providing a “language” to be able to formulate
“operations” on the system matrix of an admissible linear
system we can define a standard form (Definition <ref>).
A standard ALS will be minimal and (has) refined (pivot blocks).
In the following section we will minimize a refined ALS.
This is somewhat technical to describe but simple (we
need to solve linear systems of equations).
At the end of this section we will illustrate how to
refine pivot blocks. To the contrary this is easy
to describe but in general very difficult to accomplish
(we need to solve polynomial systems of equations).
Since the latter is closely related to factorization we
refer to 
<cit.>
 and
<cit.>
 for further information.



Let A = (u,A,v) be an admissible linear system
and denote A = (A_ij)_i,j=1^m the block decomposition
(with square diagonal blocks A_ii) with maximal m
such that A_ij=0 for i > j.
The diagonal blocks A_ii are called pivot blocks,
the number m is denoted by (A) = (A).
The dimension (or size)
of a pivot block A_ii for i ∈{ 1, 2, …, m }
is _i (A).
For i<1 or i>m let _i(A) = 0.
A (admissible) transformation (P,Q) is called
(admissible) block transformation (for A)
if P_ij = Q_ij = 0 for i > j
(with respect to the block structure of A).



Let A = (u,A,v) be an ALS with m pivot blocks of size
n_i = _i(A).
We denote by 
n_i:j = _i:j(A) = n_i + n_i+1 + … + n_j
the sum of the sizes of the pivot blocks A_ii to A_jj
(with the convention n_i:j = 0 for j < i).
For a given system the identity matrix of size n_i:j
is denoted by I_i:j.
If (P,Q) is an admissible transformation for A
then (PAQ)_ij denotes the (to the block decomposition of A
corresponding) block (i,j) of size n_i × n_j in PAQ,
(Pv)_i that of size n_i × 1 in Pv and
(uQ)_j that of size 1 × n_j in uQ.





Components in the left family s = A v are (as usual)
denoted by s_i. The j-th component for 1 ≤ j ≤_i(A)
of the i-th block for 1 ≤ i ≤(A) is
denoted by s_i(j).
A subfamily of s with respect to the pivot block k
is denoted by s_k,
s_i:j = (s_i, s_i+1, …, s_j).
Analogous is used for the right family t =u A.





A “grouping” of pivot blocks { i, i+1, …, j } 
of the system matrix is denoted by A_i:j,i:j.
If it is clear from the context where the block ends (respectively starts)
we write A_i:,i: (respectively A_:j,:j),
in particular with respect to a given pivot block.
For example A_1:,1:, A_k,k and A_:m,:m.



Let A = (u,A,v) be an ALS with m = (A)
pivot blocks of size n_i = _i(A).
An admissible transformation (P,Q) of the form
( I_1:k-1⊕T̅⊕ I_k+1:m, I_1:k-1⊕U̅⊕ I_k+1:m)
with T̅,U̅∈K^n_k × n_k is called
admissible for pivot block k or (admissible)
k-th pivot block transformation.





Let A = (u,A,v) be an ALS with m = (A)
pivot blocks of size n_i = _i(A).
A pivot block A_kk (for 1 ≤ k ≤ m)
is called refined
if there does not exist an admissible pivot block transformation
(P,Q)_k such that (PAQ)_kk has a lower left
block of zeros of size i × (n_k -i)
for an i ∈{1, 2, …, n_k-1}.
The admissible linear system A is called refined
if all pivot blocks are refined.




That the “form” of a refined ALS is not unique,
it will be illustrated in the following example.
Moreover, a refined ALS is not necessarily refined over
K: Let

A = (
[ 1 . ],
[  1  x; 2x  1 ],
[ .; 1 ]
).

Adding √(2)-times row 1 to row 2 and
subtracting √(2)-times column 2 of column 1
yields

[ 1 -√(2) x         x;         0 1 + √(2)x ]
s =
[ .; 1 ].

See also 
<cit.>
.



Let f = (y - x) be given by the minimal ALS

A_f = (
[ 1 . ],
[  1 -y; -x  1 ],
[ .; 1 ]
).

For f +3z we have the (minimal) ALS

A = (
[ 1 . . . ],
[  1 -y -1  .; -x  1  x  .;  .  .  1 -z;  .  .  .  1 ],
[ .; 1; .; 3 ]
).

Since 1 ∈ R(A) and A is constructed by
the addition in Proposition <ref>, it can
easily be transformed —in a controlled way— into
another ALS with refined pivot block structure.
Firstly we add column 3 to column 1,

A' = (
[ 1 . . . ],
[  0 -y -1  .;  0  1  x  .;  1  .  1 -z;  .  .  .  1 ],
[ .; 1; .; 3 ]
),

and then we exchange rows 1 and 3:

A” = (
[ 1 . . . ],
[  1  .  1 -z;  .  1  x  .;  . -y -1  .;  .  .  .  1 ],
[ .; 1; .; 3 ]
).






Let A = (u,A,v) be an ALS of dimension n
with m = (A) ≥ 2 pivot blocks of size n_i = _i(A).
For 1 ≤ k ≤ m the block decomposition
with respect to the pivot block k is the system

A^[k] = (
[ u_1:    .    . ],
[ A_1:,1:  A_1:,k A_1:,:m;       .   A_k,k  A_k,:m;       .       . A_:m,:m ],
[ v_1:;  v_k; v_:3 ]
)

with (square) diagonal blocks A_1:,1:, A_k,k and A_:m,:m
of size n_1:k-1, n_k respectively n_k+1:m.
(k is used here to emphasize that k is a block index.)
By A^[-k] we denote the ALS A^[k]
without block row/column k of dimension n-n_k
(not necessarily equivalent to A^[k]):

A^[-k] = (
[ u_1   . ],
[ A_1:,1: A_1:,:m;       . A_:m,:m ],
[ v_1:; v_:3 ]
).

An admissible transformation
(P,Q)_k = (P(T̅,T), Q(U̅,U))_k
of the form

    (P,Q)_k = (
    [ I_1:k-1       .       .;       .      T̅       T;       .       . I_k+1:m ],
    [ I_1:k-1       .       .;       .      U̅       U;       .       . I_k+1:m ])

is called k-th block row transformation
for A^[k],
one of the form (P(T̅,T),Q(U̅,U))^k,

    (P,Q)^k = (
    [ I_1:k-1       T       .;       .      T̅       .;       .       . I_k+1:m ],
    [ I_1:k-1       U       .;       .      U̅       .;       .       . I_k+1:m ])

is called k-th block column transformation
for A^[k].
For T̅=U̅ = I_n_k we write also
P(T) respectively Q(U) and call the block transformation
particular.




A minimal and refined
ALS A = (u,A,v) = (1,A,λ),
that is, v = [0,…, 0, λ], is called
standard.



For a polynomial p given by a standard ALS
A (of dimension n ≥ 2) the minimal inverse
of A (of dimension n-1) is refined if and
only if A is obtained by the minimal polynomial
multiplication of its irreducible factors q_i in
p = q_1 q_2 ⋯ q_m.
For a detailed discussion about the factorization of polynomials
(in free associative algebras) we refer to
<cit.>
.
One of the simplest non-trivial examples is

p = x(1-yx) = x-xyx = (1-xy)x.

With respect of the general factorization theory 
it is open to show that the free field
is a “similarity unique factorization domain”
<cit.>
.




[Factorization versus Refinement]
Later, in Example <ref> (Hua's identity),
we will need to refine a pivot block. Although
the necessary transformations there are obvious,
the procedure should be illustrated in a systematic way.
But first we have a look on how this 2× 2
block appears, namely by inverting the element given by the
ALS

A = (
[ 1 . . ],
[ x 0 1; . 1 y; . x 1 ],
[  0;  .; -1 ]
).

If we exchange columns 2 and 3 it is immediate that this is
the “product” of the admissible linear systems

A_1 = (
[ 1 ],
[ x ],
[ -1 ]
)  and  A_2 = (
[ 1 . ],
[ y 1; 1 x ],
[  .; -1 ]
).

Applying the minimal inverse on

A' = (
[ 1 . . ],
[ x 1 0; . y 1; . 1 x ],
[  0;  .; -1 ]
),

we get a refined (and minimal) ALS, namely

A” = (
[ 1 . . . ],
[ -1 -x -1  .;  . -1 -y  .;  .  . -1 -x;  .  .  .  1 ],
[ .; .; .; 1 ]
).

The factorization here is really simple.



[Pivot Block Refinement]
Now we focus on the refinement of the second pivot block in
the ALS

A = (
[ 1 . . . ],
[ 1 1 x .; . y 1 .; . 1 0 x; . . . 1 ],
[ .; .; .; 1 ]
).

(This is the ALS (<ref>) with the first three rows
scaled by -1.)
We are looking for an admissible transformation (P,Q) of the form

(P,Q) = (
[     1     .     .     .;     . α_2,2 α_2,3     .;     . α_3,2 α_3,3     .;     .     .     .     1 ],
[     1     .     .     .;     . β_2,2 β_2,3     .;     . β_3,2 β_3,3     .;     .     .     .     1 ]
).

In particular these matrices P and Q have to be
invertible, that is, we need the conditions
(P) ≠ 0 and (Q) ≠ 0.
To create a lower left 1 × 1 block of zeros in
(PAQ)_2,2 we need to solve the following polynomial
system of equations (with commuting unknowns α_ij
and β_ij):

    α_2,2α_3,3 - α_2,3α_3,2   = 1, 
    β_2,2β_3,3 - β_2,3β_3,2   = 1, 
    α_3,2β_3,2 + α_3,3β_2,2   = 0
        for 1, and
    α_3,2β_2,2   = 0
        for y.

We obtain the last two equations by multiplication
of the transformation blocks with the corresponding
coefficient matrices of the pivot blocks
(irrelevant equations are marked with “*” on the right hand side)

    [ α_2,2 α_2,3; α_3,2 α_3,3 ][ . 1; 1 . ][ β_2,2 β_2,3; β_3,2 β_3,3 ]   =
    [ * *; 0 * ]  for 1, and
    [ α_2,2 α_2,3; α_3,2 α_3,3 ][ 1 .; . . ][ β_2,2 β_2,3; β_3,2 β_3,3 ]   =
    [ * *; 0 * ]  for y.

To solve this system of polynomial equations,
Gröbner–Shirshov bases 
<cit.>
 can be used.
For detailed discussions we refer to
<cit.>
 or
<cit.>
. The basic idea comes from
<cit.>
 and is also used in 
<cit.>
 and 
<cit.>
.
For further remarks on the refinement of pivot blocks
see also 
<cit.>
.






§ MINIMIZING A REFINED ALS


First of all we derive the left respectively right
block minimization equations.
For that we consider an admissible linear system
A = (u,A,v) of dimension n with m = (A) ≥ 2
pivot blocks of size n_i = _i(A).
For 1 ≤ k < m we transform this system using the block row
transformation
(P,Q) = (P(T̅,T), Q(U̅,U))_k,
namely

    PAQ    = 
    [ I_1:k-1       .       .;       .      T̅       T;       .       . I_k+1:m ][ A_1:,1:  A_1:,k A_1:,:m;       .   A_k,k  A_k,:m;       .       . A_:m,:m ][ I_1:k-1       .       .;       .      U̅       U;       .       . I_k+1:m ]
       =
    [               A_1:,1:                A_1:,k               A_1:,:m;                     .              T̅ A_k,k T̅ A_k,:m + T A_:m,:m;                     .                     .               A_:m,:m ][ I_1:k-1       .       .;       .      U̅       U;       .       . I_k+1:m ]
       =
    [                            A_1:,1:                           A_1:,kU̅                 A_1:,k U + A_1:,:m;                                  .                         T̅ A_k,kU̅ T̅ A_k,k U + T̅ A_k,:m + T A_:m,:m;                                  .                                  .                            A_:m,:m ]  and
    
    Pv    = 
    [ I_1:k-1       .       .;       .      T̅       T;       .       . I_k+1:m ][ v_1:;  v_k; v_:m ]
    =
    [            v_1:; T̅ v_k + T v_:m;            v_:m ].

Now we can read off a 
sufficient condition for
(Q s)_k = 0^n_k × 1, namely
the existence of matrices T,U ∈K^n_k × n_k+1:m and
invertible matrices T̅,U̅∈K^n_k × n_k
such that

T̅ A_k,k U + T̅ A_k,:m + T A_:m,:m = 0^n_k ×n_k+1:m
  and  T̅ v_k + T v_:m = 0^n_k ×1.

Since T̅ is invertible (as a diagonal block of an
invertible matrix P), this condition is equivalent to the
existence of matrices T',U ∈K^n_k × n_k+1:m
such that

    A_k,k U + A_k,:m + T̅ T_=: T' A_:m,:m
      = 0^n_k × n_k+1:m  and  
    v_k + T̅ T_=: T' v_:m = 0^n_k × 1.

Applying the block column transformation
(P,Q) = (P(T̅,T), Q(U̅,U))^k,
we obtain

    PAQ    = 
    [ I_1:k-1       T       .;       .      T̅       .;       .       . I_k+1:m ][ A_1:,1:  A_1:,k A_1:,:m;       .   A_k,k  A_k,:m;       .       . A_:m,:m ][ I_1:k-1       U       .;       .      U̅       .;       .       . I_k+1:m ]
       =
    [            A_1:,1:    A_1:,k +T A_k,k A_1:,:m + T A_k,:m;                  .           T̅ A_k,k          T̅ A_k,:m;                  .                  .            A_:m,:m ][ I_1:k-1       U       .;       .      U̅       .;       .       . I_k+1:m ]
       =
    [                          A_1:,1: A_1:,1: U + A_1:,kU̅ + T A_k,kU̅               A_1:,:m + T A_k,:m;                                .                       T̅ A_k,kU̅                        T̅ A_k,:m;                                .                                .                          A_:m,:m ]

and therefore 
a sufficient condition for (t P)_k = 0^1 × n_k,
namely the existence of matrices T,U' ∈K^n_1:k-1× n_k
such that

    A_1:,1:U U̅_=:U' + A_1:,k + T A_k,k
      = 0^n_1:k-1× n_k.




A variant of the linear system of equations (<ref>)
also appears in 
<cit.>
 and
<cit.>
 (linear word problem).



[Extended ALS]
In some cases it is necessary to use an extended ALS
to be able to apply all necessary left minimization steps,
for example, for f f if f is of type (1,1).
Let A = (u,A,v) = (1,A,λ) be an ALS with
m = (A) ≥ 2 pivot blocks and k=1.
The “extended” block decomposition is then
(the block row A_1:,1: vanishes)

A^[k] = (
|
[ 1 . . ],
.
|
[       1   A_0,k       .;       .   A_k,k  A_k,:m;       .       . A_:m,:m ],
[    .;    .; v_:m ]
.
)

with A_0,k = [-1,0,…, 0].
The first row in A^[1] is only changed indirectly
(via admissible column operations) and stays scalar.
Therefore it can be removed easily (if necessary).
This is illustrated in Example <ref>.



Given an admissible linear system A,
by
Ã = A^[+0] we denote the
(to A equivalent) extended ALS.
Conversely,
0pt[0pt][0pt]
Ã^[-0] = (A^[+0])^[-0]=A.
The additional row and column is indexed by 0.
If Ã is transformed admissibly,
Ã^[-0] is an ALS.





Let A = (u,A,v) be an ALS of dimension n with
m = (A) ≥ 2 pivot blocks of size n_i = _i(A).
For k ∈{ 1,2,…, m-1 } the equations (<ref>),

A_k,k U + A_k,:m + T A_:m,:m = 0^n_k ×n_k+1:m
  and  v_k + T v_:m = 0^n_k ×1

with respect to the block decomposition A^[k]
and the particular block row transformation
(P(T), Q(U))_k
are called left block minimization equations.
They are denoted by
ℒ_k = ℒ_k(A).
A solution by the block row pair (T,U) is denoted by
ℒ_k(T,U) = 0.
For k ∈{ 2,3,…, m } the equations (<ref>),

A_1:,1: U + A_1:,k + T A_k,k = 0^n_1:k-1 ×n_k

with respect to the block decomposition A^[k]
and the particular block column transformation
(P(T), Q(U))^k
are called right block minimization equations.
They are denoted by
ℛ_k = ℛ_k(A).
A solution by the block column pair (T,U) is denoted by
ℛ_k(T,U) = 0.


In the following example we have a close look
on the role of the factorization and how to avoid
the use of possibly non-linear techniques.
All the steps are explained in detail and correspond
(with exception of the solution of the linear
systems of equations) to that in the following
algorithm.


For f = x (1-xy) and g = x we consider
h = fg = (1-yx) given by the (non-minimal) ALS
(constructed by Proposition <ref>)

A = (u,A,v) = (
[ 1 . . . ],
[  x  1  .  .;  .  y -1  .;  . -1  x -x;  .  .  .  1 ],
[ .; .; .; 1 ]
),

whose pivot blocks are refined.
Here there exists an admissible transformation
(with T=0, U=1 and invertible blocks
T̅,U̅∈K^3 × 3)

(P,Q) = (
[ 1 0 0 .; 0 1 0 .; 1 0 1 T; . . . 1 ],
[  1  0  0  .;  0  1  0  .; -1  0  1  U;  .  .  .  1 ]
),

that yields the ALS

PAQ = A' = (
[ 1 . . . ],
[  x  1  .  .;  1  y -1 -1;  0  0  x  0;  .  .  .  1 ],
[ .; .; .; 1 ]
)

in which one can eliminate row 3 and column 3
(and —after an appropriate row operation— also
the last row and column).

However, minimization can be accomplished much easier:
Firstly we observe that the left subfamily s_2:3
(of A) is
K-linearly independent.
Also the right subfamily
t_1:2 is K-linearly independent.
For the left family with respect to the first pivot block
we consider the extended ALS
(see also Remark <ref>)

|
[  1 -1  .  .  .;  .  x  1  .  .;  .  .  y -1  .;  .  . -1  x -x;  .  .  .  .  1 ]
s =
[ .; .; .; .; 1 ]
.

of A, where the upper row and the left column are indexed by zero.
Now we add row 3 to row 1,
subtract column 1 from column 3 and
add column 1 to column 4
(this transformation can be found by solving a linear system of equations):

|
[  1 -1  .  1 -1;  .  x  0  0  0;  .  .  y -1  .;  .  . -1  x -x;  .  .  .  .  1 ]
s =
[ .; 0; .; .; 1 ].
.

Now we can remove row 1 and column 1:

    |
    [  1  .  1 -1;  .  y -1  .;  . -1  x -x;  .  .  .  1 ]
    s =
    [ .; .; .; 1 ].
    .

Before we do the last (right) minimization step,
we transform the extended ALS back into a “normal”
by exchanging columns 1 and 2, scaling the (new)
column 1 by -1 and subtract it from column 3:

|
[  1 -1  .  0;  .  1  y -1;  . -x -1  0;  .  .  .  1 ]
s =
[ .; .; .; 1 ].
.

(If necessary right minimization steps can be performed
until one reaches a pivot block with corresponding
non-zero entry in row 0.)
Now we can remove row 0 and column 0 again.
The last step to a minimal ALS for
fg = (1-yx) is trivial:

[  1  y  0; -x -1  0;  .  .  1 ]
s =
[ 1; .; 1 ].

After removing the last row and column
we exchange the two rows to get a
standard ALS.


Now at least one question should have appeared:
How can one prove —for a given block index k—
the K-linear independence of the left
(respectively right) subfamily
s_k:m (respectively t_1:k)
in general, assuming that
s_k+1:m (respectively t_1:k-1)
is K-linearly independent?
For an answer some preparation is necessary.



Let f ∈F given by the linear representation
π_f = (u,A,v) of dimension n.
Then f=0 if and only if there exist invertible matrices
P,Q ∈K^n × n such that

P π_f Q= (
[ ũ_1   0 ],
[ Ã_1,1     0; Ã_2,1 Ã_2,2 ],
[   0; ṽ_2 ]
)

for square matrices Ã_1,1 and Ã_2,2.





Let A=(u,A,v) = (1,A,λ) be an ALS of dimension n
with m = (A) ≥ 2 pivot blocks of size n_i = _i(A).
Let k ∈{ 1, 2, …, m-1 } such that
the left subfamily
s_k+1:m with respect to the block decomposition
A^[k] 
is K-linearly independent while
s_k:m is K-linearly dependent.
Then there exists a block row transformation
(P,Q) = ( P(T̅, T), Q(U̅, U) )_k,
such that Ã = P A Q has the form

    [ A_1:,1: Ã_1:,k' Ã_1:,k” Ã_1:,:m;       . Ã_k',k'       0       0;       . Ã_k”,k' Ã_k”,k” Ã_k”,:m;       .       .       . A_:m,:m ][ s̃_1:;     0; s̃_k”;  s_:m ]
    =
    [    .;    .;    .; v_:m ]

If the pivot block A_k,k is refined, then
there exists a particular block row transformation
(P,Q) = (P(T), Q(U))_k,
such that the left block minimization equations

A_k,k U + A_k,:m + T A_:m,:m = 0^n_k ×n_k+1:m
  and  v_k + T v_:m = 0^n_k ×1

are fulfilled.




We refer to the block decomposition

A^[k] = (
[ u_1:    .    . ],
[ A_1:,1:  A_1:,k A_1:,:m;       .   A_k,k  A_k,:m;       .       . A_:m,:m ],
[    .;    .; v_:m ]
).

Due to the K-linear independence of the
left subfamily s_k+1:m there exists an
invertible matrix Q̃ with blocks
U̅^∘∈K^n_k × n_k
and U^∘∈K^n_k × n_k+1:m,
such that (Q̃ s)_n_1:k-1+1 = 0,
that is, the first component in s_k can be eliminated.
Let

A' = 
[   A_k,k  A_k,:m;       . A_:m,:m ]
[    U̅^∘     U^∘;       . I_k+1:m ]
  and  v' =
[    .; v_:m ].

Then A'=(u',A',v') is an ALS for 0 ∈F
and we can apply Lemma <ref> to get a transformation

(P',Q') = (
[      T̅       T;  T_:m,k T_:m,:m ],
[     U̅'      U';  U_:m,k U_:m,:m ]
)

such that P'A' Q' has the respective upper right block of zeros
and —without loss of generality— P'v' = v'.
Clearly we can choose U_:m,:m = I_k+1:m.
And since s_:m is K-linearly independent,
the block of zeros in

    P' A'    =
    [      T̅       T;  T_:m,k T_:m,:m ][  A'_k,k A'_k,:m;       . A_:m,:m ]
       =
    [                        T̅ A'_k,k           T̅ A'_k,:m + T A_:m,:m;                    T_:m,k A'_k,k T_:m,k A'_k,:m + T_:m,:m A_:m,:m ]

is independent of T_:m,k and T_:m,:m,
thus we can choose T_:m,k=0 and T_:m,:m=I_k+1:m.
Now it is obvious that the columns in the lower left block of

    P'A'Q'    =
    [              T̅ A'_k,k T̅ A'_k,:m + T A_:m,:m;                      .                A_:m,:m ][    U̅'     U'; U_:m,k      I ]
       =
    [ T̅ A'_k,kU̅' + (T̅ A'_k,:m + T A_:m,:m) U_:m,k          T̅ A'_k,k U' + T̅ A'_k,:m + T A_:m,:m;                                 A_:m,:m U_:m,k                                        A_:m,:m ]

are linear combinations of the columns of A_:m,:m
and therefore we can assume that U_:m,k=0.
Now let U̅= U̅^∘U̅' and U = U̅^∘ U' + U^∘.
Then PAQ has 
the desired form (<ref>)
for the (for k>1 admissible) block row transformation

(P,Q) = (
[ I_1:k-1       .       .;       .      T̅       T;       .       . I_k+1:m ],
[ I_1:k-1       .       .;       .      U̅       U;       .       . I_k+1:m ]
).

For the second part we first have to show that each
component in s_k can be eliminated by a linear
combination of components of s_k+1:m, that is, n_k”=0.
We assume to the contrary that n_k” > 0.
But then —by (<ref>)—
T̅ A_k,kU̅ would have
an upper right block of zeros of size (n_k - n_k”) × n_k”
and therefore (after an appropriate permutation) a lower left,
contradicting the assumption on a refined pivot block.
Hence there exists a matrix
U ∈K^n_k × n_k+1:m such that
s_k - U [s_k+1, …, s_m] = 0.
By assumption v_k = 0.
Now we can apply —as in Lemma <ref>—
Lemma <ref> with the ALS
(1,A_:m,:m,λ) and B = -A_k,k U - A_k,:m
(and s_:m).
Thus there exists a matrix T ∈K^n_k × n_k+1:m
fulfilling A_k,k U + A_k,:m + T A_:m,:m = 0.
Since the last column of T is zero, we have also T v_:m = 0.
With T̅ = U̅ = I_1:n_k the transformation (P,Q)
is the appropriate particular block row transformation.



For the proof of the second part of the theorem
one can use alternatively Lemma <ref>
which is more powerful but with respect to the use of
linear techniques not that obvious.





Notice that the left subfamily (s̃_k”, s_:m)
is not necessarily K-linearly independent.
If necessary, one can apply the theorem again
after removing block row and column k'.






For k=1, if necessary, one must use an extended ALS,
see Remark <ref>.




Assuming K-linear independence of the
left subfamily s_k+1:m and a refined
pivot block A_k,k, the second part of the previous
theorem means nothing less than the possibility
to check K-linear (in-)dependence
of the left subfamily s_k:m by
linear techniques!



Let A=(u,A,v) = (1,A,λ) be an ALS of dimension n
with m = (A) ≥ 2 pivot blocks of size n_i = _i(A).
Let k ∈{ 2, 3, …, m } such that
the right subfamily t_1:k-1
with respect to the block decomposition A^[k]
is K-linearly independent while
t_1:k is K-linearly dependent.
Then there exists a block column transformation
(P,Q) = ( P(T̅, T), Q(U̅, U))^k,
such that Ã = P A Q has the form

    [ u_1   .   .   . ]
    =
    [   t_1 t̃_2'     0  t̃_3 ][   A_1,1  Ã_1,2'       0   Ã_1,3;       . Ã_2',2'       0  Ã_2',3;       . Ã_2”,2' Ã_2”,2”  Ã_2”,3;       .       .       .   A_3,3 ].

If the pivot block A_k,k is refined, then there exists a particular
block column transformation (P,Q) = ( P(T), Q(U))^k,
such that the right block minimization equations

A_1:,1: U + A_1:,k + T A_k,k = 0^n_1:k-1 ×n_k

are fulfilled.


If one uses alternating left and right block
minimization steps for the minimization,
that is, applying Theorems <ref> and <ref>,
one has to take care that the K-linear independence
of the respective other subfamily is guaranteed.
This is illustrated in the following example.


Let A = (u,A,v) = (1,A,λ) be an ALS with
m=5 pivot blocks.
For k'=2 we assume that the left subfamily
s_k+1:m is K-linearly independent
and we assume further that there exists a particular
block row transformation (P,Q),
such that the left block minimization equations are
fulfilled, that is, PAQ has the form

[ A_1,1 A_1,2 Ã_1,3 Ã_1,4 Ã_1,5;     . A_2,2     0     0     0;     .     . A_3,3 A_3,4 A_3,5;     .     .     . A_4,4 A_4,5;     .     .     .     . A_5,5 ]
[ s̃_1;    0;  s_3;  s_4;  s_5 ]
=
[   .;   0;   .;   .; v_5 ].

If the right subfamily t_1:3 is K-linearly
independent, this is not necessarily the case for
the right subfamily t'_1:3 of the
smaller ALS
0pt[0pt][0pt]A' = ( P A Q)^[-k'].
That is, one has to apply Theorem <ref> on
A' with k=3 to check that “again”.





The admissible linear system A
represents f=0 if and only if s_1 = (A v)_1 = 0.
Since all systems are equivalent to A,
this case is recognized for k'=1 because
by Theorem <ref> there is an admissible
transformation such that the first left block minimization equation
is fulfilled.
Now assume f ≠ 0.
We have to show that both the left family s' and
the right family t' of A' = (u',A',v') are
K-linearly independent respectively.
Let m' = (A') and for k ∈{ 1, 2, …, m' }
denote by

s'_(k) = (s'_m'+1-k, s'_m'+2-k, …, s'_m')
  and  t'_(k) = (t'_1, t'_2, …, t'_k)

the left and the right subfamily respectively.
By assumption s'_(1) and t'_(1) are K-linearly
independent respectively.
The loop starts with k=2.
Only if both s'_(k) and t'_(k)
are K-linearly independent respectively,
k is incremented.
Otherwise a left (Theorem <ref>) or a right
(Theorem <ref>) minimization step
was successful and the dimension of the current ALS is
strictly smaller than that of the previous.
Hence, since k is bounded from below,
the algorithm stops in a finite number of steps.
(How row 0 and column 0 are
removed from the extended ALS in line 14
is illustrated in Example <ref>.)
All transformations are such that A' is a refined
ALS (and therefore in standard form).
For (A')=1 a priori only the left (or the right)
family is K-linearly independent (by assumption).
But if that were not the case for the respective other family,
then the assumption on refined pivot blocks would be contradicted
by Theorem <ref> (respectively Theorem <ref>)




Concerning details with respect to the complexity
of such an algorithm we refer to 
<cit.>
.
Let d be the number of letters in our alphabet X.
For m = n pivot blocks 
and k < n we have 2(k-1) unknowns.
By Gaussian elimination one
gets complexity (dn^3)
for solving a linear system for a minimization step,
see <cit.>
.
To build such a system and working on a
linear matrix pencil
[[ 0 u; v A ]]
with d+1 square
coefficient matrices of size n+1
(transformations, etc.)
has complexity (dn^2).
So we get overall (minimization) complexity
(d n^4).
The algorithm of Cardon and Crochemore <cit.>
 has complexity (d n^3)
but works only for regular elements, that is,
rational formal power series.
For _i(A) ≈√(n) we get
complexity (d n^5) and for the
word problem 
<cit.>
 with m=2 we get complexity
(d n^6).





It is clear that one can adapt the algorithm slightly if
the input ALS is constructed by Proposition <ref>
out of two minimal admissible linear systems (for the sum and
the product) in standard form.





The solution of the word problem for two elements
given by minimal admissible linear systems is
independent of their refinement.
If Algorithm <ref> is applied to
an ALS of which it is not known if it is refined,
in some cases it is possible to check if the
ALS A' is minimal, for example if
(A') = (A').
If the pivot blocks are bigger but the right upper
structure is “finer” one can instead —for f ≠ 0—
try to minimize the inverse (A').
In concrete situations there might be other
possibilities to reach minimality.



Apart from minimization, this algorithm can be used to check if
f is a left factor of an element fg which is relevant for
the minimal factor multiplication 
<cit.>
. And one can check if two elements are disjoint
which is important for the primary decomposition
<cit.>
.


Another aspect of Algorithm <ref> (respectively
Theorem <ref> and <ref>) becomes visible
immediately with Proposition <ref> and
Remark <ref>.
The importance of the following theorem becomes clear
if one needs to check K-linear (in-)dependence
of an arbitrary family (f_1, f_2, …, f_n) 
over the free field and it is not possible (anymore)
to take a representation as formal power series
(with coefficients over K).




A refined admissible linear system A=(1,A,λ)
for an element in the free field F
with m=(A) ≥ 2 pivot blocks and λ≠ 0
is minimal if and only if
neither the left block minimization equations
ℒ_k(A) for k ∈{ 1, 2, …, m-1 }
nor the right block minimization equations
ℛ^k(A) for k ∈{ 2,3, …, m }
admit a solution.



From the existence of a solution non-minimality follows immediately
since in this case —after the appropriate transformation—
rows and columns can be removed.
And for non-minimality Proposition <ref>
implies that either the left or the right family is K-linearly
dependent.
Without loss of generality assume that it is the left
s = (s_1, s_2, …, s_m)
with minimal k ∈{ 1, 2, …, m-1 } such that
the left subfamily (s_k+1, …, s_m)
is K-linearly independent.
Since the pivot blocks are refined, Theorem <ref>
implies the existence of a particular block row transformation
(P,Q)_k and therefore a solution of the k-th left
block minimization equations.




§ APPLICATIONS


Since the focus of this work is mainly minimization
and one dedicated to “minimal” rational operations
—collecting all techniques for practical application—
is already available
<cit.>
, only two applications are illustrated in the following
examples. For other applications see also
Remark <ref>.

[Hua's Identity
<cit.>
]
We have:

    x - (x + (y - x)) = xyx.




Minimal admissible linear systems for y and x are

[ y ]
s =
[ 1 ]
  and  [  1 -x;  .  1 ]
s =
[ .; 1 ]

respectively.
The ALS for the difference y -x,

[  y -y  .;  .  1 -x;  .  .  1 ]
s = 
[  1;  .; -1 ],   s =
[ y- x;   -x;   -1 ],   t = 
[    y   -1 y- x ]

is minimal because the left family s is K-linearly
independent and the right family t is K-linearly
independent (Proposition <ref>).
Clearly we have 1∈ R(y -x).
Thus, by Lemma <ref>,
there exists an admissible transformation

(P,Q) = (
[ . 1 .; 1 . 1; . . 1 ],
[ 1 . .; 1 1 .; . . 1 ]
),

that yields the ALS

[  1  1 -x;  . -y  1;  .  .  1 ]
s =
[  .;  .; -1 ].

Now we can apply the inverse of type (1,1):

[  1  y; -x -1 ]
s =
[ .; 1 ],
  s = 
[   (y-x); -(1-xy) ].

This system represents a regular element
(y - x) = (1-yx) y,
and therefore can be transformed into a regular ALS
(Definition <ref>)
by scaling row 2 by -1.
Then we add x “from the left”:

[  x -x  .;  .  1  y;  .  x  1 ]
s = 
[  1;  .; -1 ],   s =
[ x+ (y-x);    (y-x);  -(1-xy) ].

This system is minimal and —after adding row 3 to row 1
(to eliminate the non-zero entry in the right hand side)—
we apply the (minimal) inverse of type (0,0):

    [ -1 -1 -x  .;  . -y -1  .;  . -1  0 -x;  .  .  .  1 ]
    s =
    [ .; .; .; 1 ].

Now we multiply row 1 and the columns 2 and 3 by -1
and exchange column 2 and 3 to get the following system:

[  1 -x -1  .;  .  1  y  .;  .  .  1 -x;  .  .  .  1 ]
s =
[ .; .; .; 1 ],   s = 
[ x - xyx;     -yx;       x;       1 ].

The next step would be a scaling by -1 and
the addition of x (by Proposition <ref>).
With two minimization steps we would reach again minimality.
Alternatively we can add a linear term to a polynomial
(in a polynomial ALS)
—depending on the entry v_n in the right hand side—
directly in the upper right entry of the
system matrix:

[  1 -x -1  x;  .  1  y  .;  .  .  1 -x;  .  .  .  1 ]
s =
[ .; .; .; 1 ],   s = 
[ - xyx;   -yx;     x;     1 ].




The transformation of the ALS (<ref>)
is a simple case of the refinement
of a pivot block and is discussed in detail
in Section <ref>.
Hua's identity is also an example in
<cit.>
. It is worth to compare both approaches.



[Left GCD]

Given two polynomials p,q ∈KX∖K,
one can compute the left (respectively right)
greatest common divisor of p and q
by minimizing an admissible linear system for p q (respectively p q).
This is now illustrated in the following example.
Let p = yx(1-yx)z = yxz - yxyxz and
q = y(1-xy)y = y^2 - yxy^2.
We want to find h = (p,q).
An ALS for p q (constructed out of minimal admissible linear systems
for p and q by Proposition <ref>) is

[  z  1  .  .  .  .  .  .  .;  .  x -1  .  .  .  .  .  .;  . -1  y -1  .  .  .  .  .;  .  .  .  x -1  .  .  .  .;  .  .  .  .  y -y  .  .  .;  .  .  .  .  .  1 -x  1  .;  .  .  .  .  .  .  1 -y  .;  .  .  .  .  .  .  .  1  y;  .  .  .  .  .  .  .  .  1 ]
s =
[ .; .; .; .; .; .; .; .; 1 ].

Clearly, this system is refined.
How to refine an ALS is discussed in Section <ref>.
Note, that there is a close 
connection to the factorization of p, for details see
<cit.>
.
As a first step we add column 5 to column 6 and
row 6 to row 4,

[  z  1  .  .  .  0  .  .  .;  .  x -1  .  .  0  .  .  .;  . -1  y -1  .  0  .  .  .;  .  .  .  x -1  0 -x  1  .;  .  .  .  .  y  0  0  0  0;  .  .  .  .  .  1 -x  1  .;  .  .  .  .  .  .  1 -y  .;  .  .  .  .  .  .  .  1  y;  .  .  .  .  .  .  .  .  1 ]
s =
[ .; .; .; .; .; .; .; .; 1 ],

remove rows and columns 5 and 6,

    [  z  1  .  .  .  .  .;  .  x -1  .  .  .  .;  . -1  y -1  .  .  .;  .  .  .  x -x  1  .;  .  .  .  .  1 -y  .;  .  .  .  .  .  1  y;  .  .  .  .  .  .  1 ]
    s =
    [ .; .; .; .; .; .; 1 ]

and remember the first (left) divisor h_1 = y
we have eliminated. (In the next step with a bigger block
one can see immediately how to “read” a divisor
directly from the ALS.)
Now there are two ways to proceed:
If it is not possible to create a zero block in “L”-form
(like before), one can try to change the upper pivot block
structure to create a “double-L” zero block.
Here, this is possible by subtracting column 4 from column 2
and adding row 2 to row 4.
(For details on similarity unique factorization
in this context
see <cit.>
.)
Afterwards we apply the (admissible) transformation

(P,Q) = 
(
[ 1 . . . . . .; . 1 . . . 1 .; . . 1 . 1 . .; . . . 1 . . .; . . . . 1 . .; . . . . . 1 .; . . . . . . 1 ],
[ 1 . . . . . .; . 1 . . . . .; . . 1 . . 1 .; . . . 1 1 . .; . . . . 1 . .; . . . . . 1 .; . . . . . . 1 ]
)

to get the ALS

    [  z  1  .  .  0  0  .;  .  x -1  .  0  0  y;  .  .  y -1  0  0  0;  .  . -1  x  0  0  0;  .  .  .  .  1 -y  .;  .  .  .  .  .  1  y;  .  .  .  .  .  .  1 ]
    s =
    [ .; .; .; .; .; .; 1 ].

How to get this transformation (P,Q) is described in principle
in Section <ref>.
One can look directly for a “double-L” block transformation.
In the third pivot block of (<ref>) one can see
immediately that a further (common) left factor is h_2 = 1-xy
because the second equation reads x s_2 - h_2 = 0.
We have eliminated (1-xy) (1-xy).
Recall that a minimal ALS for h_2 is

[  1 -x  1;  .  1 -y;  .  .  1 ]
s =
[  .;  .; -1 ],

hence (h_2) = 3 and (by Theorem <ref>)
(h_2) = 2. Or, more general, for a (left)
factor h_i with (h_i) = n_i ≥ 2 we can
construct (by Proposition <ref>)
an ALS of dimension 2(n_i-1). 
After removing rows and columns { 3,4,5,6 }
in the ALS (<ref>), we obtain
for p q the (in this case minimal) ALS

    [ z 1 .; . x y; . . 1 ]
    s =
    [ .; .; 1 ].

Hence h = h_1 h_2 = y(1-xy) = (p,q).
The second possibility —starting from ALS (<ref>)—
is to do a right minimization step with respect to
column 5, then one left with respect to rows 2 and 3 and
finally a right (minimization step).
Again one obtains the ALS (<ref>)
(up to admissible scaling of rows and columns)
where the right factor y of q remains.
Therefore (p,q) = y - yxy.
For further details concerning the minimal polynomial
multiplication (Proposition <ref>)
we refer to 
<cit.>
.



It can happen that —after there is no more “L”-minimization step
possible— the ALS is not minimal,
that is, an additional “single” left or right minimization step
can be carried out. More details on that are part of the
general factorization theory 
<cit.>
.
Here it suffices to take a closer look at the ALS (<ref>):
both right factors of p (here xz) respectively q (here y)
can still be “read” directly.
(This would not be possible any more if one left or right step
would be carried out.)



For a refined ALS for p, an ALS of dimension n
for p q with “factors” of rank √(n) and an alphabet
with d letters, the complexity for computing the left (or right)
gcd is roughly (dn^5).
Although in general refinement is difficult because of the necessity
to solve systems of polynomial equations (over a not necessarily
algebraically closed field), especially for polynomials
linear techniques are very useful for the factorization
(and therefore for the refinement of the inverse).
As an example we take the polynomial p = (1-xy)(2+yx)(3-yz)(2-zy)(1-xz)(3+zx)x
of rank n=14 which has already 64 terms. To get the first left
(irreducible) factor (of rank 3) we just need to create an upper right
block of zeros (in the system matrix) of size 2 × 11
which can be accomplished
by either using the columns 2–3 and rows 4–13
or column 2 and rows 3–13 (for elimination)
<cit.>
.
Both cases result in a linear system of equations
because column and row transformations do not “overlap”.
Solving one of these 2(n-2) systems has (at most) complexity
(d n^6), hence in total we have (d n^7).
Checking irreducibility of polynomials (using Gröbner bases)
works practically up to rank 12 
<cit.>
.





§ EPILOGUE


This work is the last in a series for the development of
tools for the work with linear representations (for elements
in the free field) especially for the implementation in
computer algebra systems.
A “practical” guide giving an overview
and an introduction is
<cit.>
 (in German, with remarks on the implementation) and 
<cit.>
.

The main idea is as simple as in the usage of “classical”
fractions (for elements in the field of rational numbers):
calculating, factorizing and minimizing
(or cancelling), for example

    2/3·3/4
      = 6/12 = 2· 3/2· 2 · 3
      = 1/2  or
       1/2 + 3/2
      = 4/2
      = 2· 2/2 = 2.

At some point one stops this loop and uses the fraction
(with coprime numerator and denominator). 
Clearly, one could simplify things by remembering the
factorization of the numerator (for the product)
and the denominator (for the sum and the product).
In our case of the free field, linear representations
(or admissible linear systems) are just “free fractions”
…

However, to understand how the transition from using
nc rational expressions (to represent elements in the
free field) to (minimal) admissible linear systems
in standard form affects the capabilities of
thinking about (free) nc algebra, one needs to go to the
meta level
<cit.>
.




§ ACKNOWLEDGEMENT


I am very grateful to Wolfgang Tutschke and
Thomas Hirschler for encouraging me in
following my mathematical way in a difficult time.
And I thank the anonymous referees for the constructive remarks,
in particular to stress the various connections to related
areas and improve the exposition.
The open access funding is provided by University of Vienna.


unsrt
tocsectionBibliography
alpha


