A Factorization Theory for some Free Fields
Konrad Schrempf
math.RA 16K40, 16Z05 (Primary) 16G99, 16S10 (Secondary)


Density-aware Dynamic Mobile Networks:
Opportunities and Challenges
    
Ertan Onur, 
Shahram Mollahasani,
Alperen Eroğlu and Nina Razi Moftakhar


Corresponding author: E. Onur (email: eronur@metu.edu.tr).
    December 30, 2023
==========================================================================================================================================




Although in general there is no meaningful
concept of factorization in fields,
that in free associative algebras
(over a commutative field)
can be extended to their respective free field
(universal field of fractions) on the level of
minimal linear representations.
We establish a factorization theory by
providing an alternative definition of
left (and right) divisibility based
on the rank of an element and
show that it coincides with the “classical”
left (and right) divisibility for non-commutative
polynomials.
Additionally we present an approach to factorize elements,
in particular rational formal power series,
into their (generalized) atoms.
The problem is reduced to solving a system of
polynomial equations with commuting unknowns.


 Primary 16K40, 16Z05; Secondary 16G99, 16S10

Keywords:
Free associative algebra,
factorization of non-commutative polynomials,
minimal linear representation, universal field of fractions,
admissible linear system, non-commutative formal power series


Keywords and 2020 Mathematics Subject Classification.
Free associative algebra,
factorization of non-commutative polynomials,
minimal linear representation, universal field of fractions,
admissible linear system, non-commutative formal power series;
Primary 16K40, 16Z05; Secondary 16G99, 16S10




§ INTRODUCTION



§ INTRODUCTION



From an algebraic point of view fields are usually
not very interesting (with respect to factorization)
due to the lack of “structure”,
for example, they do not have non-zero non-units.
However here, the field
—the universal field of fractions (“free field”)
of the free associative algebra (over a commutative
ground field)— is non-commutative
and infinite dimensional over its center
(at least if we exclude the one-variable case).
A brief introduction can be found in
<cit.>
, for details we refer to
<cit.>
, where also historical information is provided:
“Until 1970 the only purely algebraic methods of embedding rings in
fields were based on Ore's method 
<cit.>
.”


The main idea is to view all elements in terms of their
normal form (minimal linear representation)
<cit.>
. Given an element, the dimension of a minimal
linear representation defines its rank
<cit.>
, for example,
the rank of a word/monomial of length n is n+1.
Since multiplication (of two elements) can be formulated
in terms of linear representations, we establish a
concept to “reverse” this step, that is, given an element
(by a minimal linear representation) to find left
(and right) divisors subject to conditions on the ranks
of the involved elements.

In <cit.>
 we showed that in the free associative algebra
there is a rather natural correspondence between
a factorization of an element and (upper right) blocks of zeros
in (a special form of) its minimal linear representations.
One does not have to take care about the ranks.
In general a minimal multiplication, that is,
a multiplication on the level of minimal linear representations
is much more subtle.
Now, how do we have to define divisibility
in terms of the rank
such that it is equivalent to that in the free associative algebra?

Joining factorization theory in the non-commutative
setting —for an overview see
<cit.>
—
and the theory of embedding “non-commutative” rings
into a (skew) field
—to be more precise: embedding free ideal rings (firs)
into their respective universal field of fractions,
see <cit.>
—
even for the “simplest” case of the free associative algebra
results in a very rich structure,
maybe not only for a “free factorization theory”.
Somewhat paradoxical is the fact that the inverse
plays a crucial role. Since each non-zero element
(in the free field) is invertible, we can use both,
its rank and that of its inverse, for example,
the inverse of a polynomial of rank n≥ 2 has rank n-1.
A corollary to the minimal inverse (Theorem <ref>)
is used to identify trivial units, that is, units from the
(commutative) ground field. We do not even have to exclude the
(commutative) one-variable case.

Factorization (of rational functions) in the latter
(on the level of realizations)
is well established in control theory
<cit.>
. Factorization in the non-commutative setting
is discussed in 
<cit.>
 and
<cit.>
.

After fixing the basic notation and stating the basic definitions
in Section <ref>, we develop the main (technical) tools
in Section <ref>. In a first reading only
Proposition <ref> (rational operations) and
Theorem <ref> (minimal inverse) are important.
The main part is Section <ref>
where the factorization theory is developed,
starting with Definition <ref>
and culminating (but not ending) in Theorem <ref>.
Finally, in Section <ref>, minimal multiplication
(Theorem <ref>) and
factorization (Theorem <ref>)
is discussed.


This exposition is not meant to serve as an introduction,
neither to free fields nor to non-commutative factorization (in free
associative algebras). Instead, depending on the background,
the example in <cit.>
, the connection to formal power series
<cit.>
 or the polynomial factorization
 <cit.>
 might be helpful. One way to get acquainted with free fields
is to use them (“almost” like the rational numbers) and explore
the rich theory in parallel. The step from inverting a non-zero
number, say in s = v/a or as = v with unique solution s,
to inverting “full” matrices (Definition <ref>)
is non-trivial but similar:
As=v with unique solution vector s (we are usually
interested in its first component s_1).





§ PRELIMINARIES


We represent elements (in free fields) by
admissible linear systems (Definition <ref>),
which are just a special form of linear representations
(Definition <ref>) and “general” admissible systems
<cit.>
. 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,…},
that including zero by _0.
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.
The transpose of a vector v is denoted by v,
the unit (column) vector with a one at position n (and size depending on
the context) by e_n = [0,…,0_n-1,1,0…,0].


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.>
,
<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
  ⊊KX
  ⊊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.
The length of a word w=x_i_1 x_i_2⋯ x_i_m is m,
denoted by w = m or ℓ(w) = m.
For detailed introductions see
<cit.>
 or
<cit.>
.


For an overview about the many connections to formal language
theory, automata, nc rational series and recognizability
we recommend <cit.>
. Recognizable series are defined via “regular”
linear representations
<cit.>
, a special case of those introduced later
in Definition <ref>.
A summary is available in 
<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.



Every full matrix (over the free associative algebra) is invertible
over the free field
<cit.>
.




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';  . ].





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.



A linear representation A = (u,A,v) of f ∈F
is called admissible linear system (ALS) for f,
written also as A s = v,
if u=e_1=[1,0,…,0].
The element f is then the first component
of the (unique) solution vector s.
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.>
.


The following definition is slightly adapted to avoid confusion with
other transformation matrices for the factorization,
formulated independent of a given admissible linear system.



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.

A polynomial ALS is also written as A = (1,A,λ)
with 1,λ∈K.
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 R be a ring. 
Two right ideals a,b⊆ R are called
similar, written as a∼b,
if R/a≅ R/b as right R-modules.
Two elements p,q∈ R are called similar if
their right ideals pR and qR are similar,
that is, pR ∼ qR.
See also 
<cit.>
.




Let R be a domain and H = R^∙ = R ∖{ 0 }.
An element p left divides q,
written as p  q, if q ∈ pH = { ph | h ∈ H }.
Two elements p,q are called left coprime
if for all h such that h p and h q
implies h ∈ H^× = { f ∈ H | f  is invertible},
that is, h is an element of the group of units.
Right division p  q and the notion of
right coprime is defined in a similar way.
Two elements are called coprime
if they are left and right coprime.



Let R be a domain and H = R^∙.
An element p∈ H ∖ H^×, that is,
a non-zero non-unit (in R), is called an atom
(or irreducible)
if p = q_1 q_2 with q_1,q_2 ∈ H implies that
either q_1 ∈ H^× or q_2 ∈ H^×.
The set of atoms in R is denoted by
(R).
The (cancellative) monoid H is called atomic
if every non-unit can be written as a finite product of atoms of H.
The domain R is called atomic if the monoid R^∙ is atomic.




A domain R is called similarity factorial
(or a similarity-UFD) if
R is atomic and it satisfies the property that
if p_1 p_2 ⋯ p_m = q_1 q_2 ⋯ q_n for atoms
(irreducible elements)
p_i,q_j ∈ R,
then m=n and there exists a permutation σ∈𝔖_m
such that p_i is similar to q_σ(i) for all i∈ 1,2, …, m.



The free associative algebra R = KX
is a similarity (unique) factorization domain.





§ 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 addition
can be formulated (Proposition <ref>).
For minimal multiplication we refer to Section <ref>.
For the minimal inverse we have to distinguish four
cases, which are summarized in Theorem <ref>.
In general however, it is necessary to minimize a given
system. For a polynomial ALS this is discussed in
<cit.>
, for the general case we refer to
<cit.>
.


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 ]
).





Two elements f,g ∈F are called
disjoint if (f+g) = (f) + (g).



Two polynomials are never disjoint.
This can be easily seen in the construction
(of an ALS) for the sum (of the polynomials).
See also <cit.>
.


For disjoint elements the formulation of a minimal addition
(Proposition <ref>) is immediate.
Testing if two elements are disjoint in F is difficult
because it relies on techniques for minimizing linear representations
<cit.>
.
However, since minimality of a linear representation
is equivalent to K-linear independence of
its left and right family respectively (Proposition <ref>),
two elements f,g are disjoint if
L(f) ∩ L(g) = { 0 } and R(f) ∩ R(g) = { 0 }.


For f = x + ( (1-x) + x)
a minimal ALS
—constructed by Proposition <ref>— is

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




Let f,g ∈F be disjoint and
given by the minimal
admissible linear systems A_f = (u_f, A_f, v_f)
and A_g = (u_g, A_g, v_g) of dimension n_f and n_g
respectively.
Then the system

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

of dimension n_f+n_g
(from Proposition <ref>)
for f+g is minimal.


Like in the polynomial case, factorization and minimal
multiplication are tight together as opposite points of view.
Further assumptions that guarantee minimality are developed
in Section <ref>.
They eventually enter in Theorem <ref>.
We will need alternative constructions
(to that in Proposition <ref>)
for the product
several times, so we state them already here
in Propositions <ref> and <ref>.
These constructions are used in particular in Theorem <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 we prove Lemma <ref> by applying
Lemma <ref>.



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 an ALS 
of dimension n ≥ 1 with K-linearly independent
right family t = u A and
B = B_0 ⊗ 1 + B_1 ⊗ x_1 + … + B_d ⊗ x_d
with B_ℓ∈K^n× m, such that
t B = 0. Then there exists a (unique) U ∈K^n × m
such that B = AU.





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.



Without loss of generality, assume that v = [0,…,0,1] and
the left family s = A v is (s_1, s_2, …, s_n-1, 1).
Otherwise it can be brought to this form by some admissible transformation
(P^∘, Q^∘).
Now let A̅ denote the upper left (n-1)× (n-1) block of A,
let s̅ = (s_1, …, s_n-1) and write As = v as

[ A̅  b;  c  d ]
[ s̅;  1 ]
=
[ 0; 1 ].

Now let B = [ c, d-1] and apply Lemma <ref>
to get the matrix T = [T̅, τ ] ∈K^1 × n
such that B = TA. Thus we get the transformation

(P,Q) = (
[ I_n-1     .;   -T̅    -τ ]
P^∘,
Q^∘).





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 a 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 a 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>).
One could call the multiplication from Proposition <ref>
type (*,*). A necessary condition for minimality however
is, that the left factor is of type (*,0) and
the right factor is of type (0,*),
thus we will use this construction later as type (0,0).
Section <ref> is dedicated to a sufficient condition.
See also Figure <ref>, page fig:ft.minmul.



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 ]).




Construct the ALS A'=(u',A',v') of dimension n_f+n_g
for the product fg
using Proposition <ref>. Add λ_f-times
column n_f to column (n_f+1) (in the system matrix A').
Remove column n_f from A' and v' and row n_f
from A' and u' to get the ALS (<ref>)
of dimension n_f+n_g-1.



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 ]).




Construct the ALS A'=(u',A',v') of dimension n_f+n_g
for the product fg
using Proposition <ref>. Add λ_f-times
row (n_f+1) to row n_f (in the system matrix A').
Remove row (n_f+1) from A' and v' and column (n_f+1)
from A' and u' to get the ALS (<ref>)
of dimension n_f+n_g-1.



Recall that, if f (respectively g) is given by a minimal ALS,
it can be transformed appropriately by Lemma <ref>
(respectively Lemma <ref>)
into the form (<ref>) (respectively (<ref>)).


Lemma <ref> is a slightly more general version of
<cit.>
. 
The proof of (the following) Proposition <ref>
becomes simple
by the help of the two lemmas <ref>
and <ref> which are extracted of the original
proof (of the minimal polynomial multiplication).
They are useful later,
especially in Lemma <ref>.


Note 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.





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.




By assumption, the left subfamily (s_m-1, s_m, …, s_n)
is K-linearly dependent.
Thus there are κ_m, …, κ_n ∈K such that
s_m-1 = κ_m s_m + κ_m+1 s_m+1 + … + κ_n s_n.
Let U = [κ_m, κ_m+1, …, κ_n ].
Then s_m-1 - U s = 0.
By assumption v_m-1=0.
Now we can apply Lemma <ref> with
B = U + [ a_m-1,m, a_m-1,m+1, …, a_m-1,n]
(and s).
Hence, there exists a matrix
T∈K^1 × (n+1-m)
such that

U + 
[ a_m-1,m       … a_m-1,n ]
- T
[ a_m,m     … a_m,n;     ⋮     ⋱     ⋮; a_n,m     … a_n,n ]
=
[ 0 … 0 ]

holds. Recall that the last column of T is zero,
whence 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.



Without loss of generality assume v = [0,…,0,1],
A_p in polynomial form
(by <cit.>
 every polynomial admits a linear representation
with upper unitriangular system matrix)
and A_g with first
column [1,0,…,0].
Let s_p = (s^p_1, …, s^p_n_p) and
s_g = (s^g_1, …, s^g_n_g) be the respective
left family of A_p and A_g.
We have to show that the left family

s = (s_1, s_2, …, s_n)
  = (s^p_1 g, …, s^p_n_p-1g, g, s^g_2, …, s^g_n_g).

of A is K-linearly independent.
Assume to the contrary that there is an index 1 < m ≤ n_p
such that (s_m-1, s_m, …, s_n) is K-linearly dependent
while (s_m,…,s_n) is K-linearly independent.
Then, by Lemma <ref>,
there exist matrices T,U ∈K^1 × (n-m+1)
as blocks in (invertible) matrices P,Q ∈K^n × n,

P = 
[   I_m-2       .       .;       .       1       T;       .       . I_n-m+1 ]
  and  Q =
[   I_m-2       .       .;       .       1       U;       .       . I_n-m+1 ],

that yield equation s_m-1=0 (in row m-1) in PAQ.
(This “potential” transformation (P,Q) is not
necessarily admissible. But this is not an issue here,
since we are only checking linear independence
of the left family.)
Let P̃ (respectively Q̃) be the upper left part
of P (respectively Q) of size n_g × n_g.
Then the equation in row m-1 in P̃A_p Q̃
is s^p_m-1 = α∈K, contradicting K-linear
independence of the left family of A_p since
s^p_n_p = λ∈K.



Nothing can be said about minimality of A since
the right family t = u A could be K-linearly
dependent. As an example take p=xy and g = y + z.
An ALS for pg = x + xyz constructed by Proposition <ref> is

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

The right family is t = [1, x, xy, x, x+xyz].



Let f ∈F∖K
and q ∈KX∖K
be given by the minimal admissible linear systems
A_f = (u_f, A_f, v_f) and A_q = (u_q, A_q, v_q)
of dimension n_f and n_q respectively
with 1 ∈ L(f).
Then the right family of the ALS A = (u,A,v)
for fq of dimension n = n_f + n_q -1 from
Proposition <ref> is K-linearly independent.



Let 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.



The left family of A is K-linearly independent by
Lemma <ref> and its right family is K-linearly
independent by Lemma <ref>.
Whence A is minimal (by Proposition <ref>)
and by construction in polynomial form.




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 0 ≠ f ∈F.
Then f ∈K if and only if (f) = (f) = 1.



This simple consequence of Theorem <ref> makes it possible
to distinguish between trivial units (non-zero scalar elements)
and non-trivial units, that is, elements in F∖K.
The main idea in the factorization theory
in Section <ref> is to allow only (the insertion of) trivial
units (in factorizations). It is used explicitly in Lemma <ref>
and implicitly in Theorem <ref>.



Note 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).








§ FACTORIZATION THEORY


To compensate the lack of non-zero non-units in 
F = KX,
that is, F∖{ 0} = F^∙ = F^×
  = { f ∈F| f  is invertible},
we will view the elements in terms of their minimal
linear representations. Recall that the dimension of a minimal one
of f ∈F defines the rank of f.

Firstly, in Definition <ref>,
we define factors based on the rank.
Although this definition would suffice to define divisibility
for polynomials, it is too rigid in general.
Since this is far from obvious it is explained in detail
in an example before Definition <ref>
(left and right divisibility).
Secondly, some preparation is necessary to be able to exclude the
insertion of non-trivial units. This is the essence of Lemma <ref>.
Finally, Theorem <ref> yields, as the main result,
the equivalence of the “classical” divisibility (in free associative algebras)
and the new one (for the free field) for polynomials.


For a factorization of a (non-zero) polynomial p = q_1 q_2 ⋯ q_m
into atoms q_i we would like to have a factorization of its
inverse p = (q_1 q_2 ⋯ q_m) = q_m⋯ q_2 q_1
into atoms q_i.
For two polynomials p,q we have
—due to the minimal polynomial multiplication—
(p)+(q) = (pq)+1.
Recalling Definition <ref> we
have p  h if h = pq
for some q ∈KX.
The minimal inverse type (1,1) yields

(q) + (p) = (q)-1 + (p)-1 = (qp),

or q “left divides” h
for h = pq.
See Proposition <ref>, Theorem <ref>
and Lemma <ref>.
To avoid inserting non-trivial units from F∖K,
we have to bound the sum of the ranks of the two factors:
(p x) + (x q) = (pq) + 2.



Let h ∈ = F^∙ be given.
An element f∈ is called
left factor of h if

    (f) +  (f h)    ≤(h) + 1
        and
    (h f) + (f)    ≤(h) + 1.

An element g∈ is called
right factor of h if

    (h g) + (g)    ≤(h) + 1
        and
     (g) + (g h)    ≤(h) + 1.

Scalars and scalar multiples of h are called trivial factors.
Non-trivial left/right factors are called proper.
Left and right factors are also called outer
to distinguish them from (general) factors of a factorization.



Straight away we have that f is a left factor
of h if and only if g =f h is a right factor of h.
And f is a left factor of h if and only if
f is a right factor of h.


For two polynomials p and q the previous definition
tells us that p (respectively q) is a left (respectively right)
factor of pq.
However, in general f is not
a left factor of h = f g. As an example take f = (xyz) and
g= x. Then

    (f) + (g)
         = (z y x) + (x) 
       = 3 + 2 
       > (z y) + 1.

While here it is easy to see that f and g have a
non-trivial left divisor in KX
(in the sense of Definition <ref>),
this can be much more delicate in general,
illustrated in Example <ref>.
This example will also show that the definition
of outer factors is rather restrictive
and not applicable directly. Later left and
right divisors will be defined more generally
in such a way that outer factors can be
“split off” in at least one possible sequence
(see Definition <ref>).
Although we will see later that this is a generalization of the factorization
in the free associative algebra, it is much more difficult
to apply for two reasons: One has to test all
possible “sequences” of factorizations to get the atoms
(up to “similarity”).
And the invertibility
of the transformation matrices —to admissibly transform the
ALS in such a way that the factors can be “extracted”—
has to be ensured by including
a condition for non-vanishing determinant. The latter might
restrict practical applications to rank ≤ 6, similar to the
test if a matrix is full 
<cit.>
. Section <ref> provides further details.
Experiments show that testing (ir)reducibility of
polynomials (using polynomial admissible linear systems)
works practically for rank ≤ 12,
in some cases up to rank ≤ 17
<cit.>
.



Let f = f_1 f_2 f_3, with f_1 = (xy), f_2 = 1-xz and f_3 = (yz),
be given by the minimal ALS

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

Then it is immediate (after recalling the construction
of an ALS for the product from Proposition <ref>)
that f_3 is a right factor of f
by duplicating s_3, that is, inserting a “dummy” row
(between row 2 and 3):

[  y -1  z  0  .;  .  x -1  0  .;  0  0  1 -1  0;  .  .  0  z -1;  .  .  0  .  y ]
s' =
[ .; .; 0; .; 1 ],
  s' =
[ s_1; s_2; s_3; s_3; s_4 ].

Thus, if a minimal ALS A = (u,A,v) for f
is not of the form
(<ref>), we need to find an
admissible transformation (P,Q) such that
the (transformed) system matrix PAQ has
a lower left zero block of size 2 × 2
and an upper right zero block of size 2 × 1
and only the last component of the right hand side
Pv is non-zero,
to detect the right factor f_3.
Similarly, subtracting row 3 from 1 and adding column 2 to 4
in (<ref>) yields

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

Compare with Figure <ref>, page fig:ft.minmul,
k=2 in type (*,1).
By duplicating t_2, that is, inserting a “dummy” column
(between column 2 and 3) one can see that f_1=(xy) is
a left factor of f = (xy) (1-xz) (yz):

[ 1 . 0 . . ]
=
[ t_1 t_2 t_2 t_3 t_4 ]
[  y -1  0  .  .;  .  x -1  0  0;  0  0  1 -1  x;  .  .  0  z -1;  .  .  0  .  y ].

However, f_1 (respectively f_2) is not a left
(respectively right) factor of f_1 f_2
while y is a left factor of f_1 f_2 and x is a
left factor of x f_2. We now take a closer look on that
phenomenon. A minimal ALS for f' = f_1 f_2 is given by

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

The reason is that the rank does not increase
(when f_2 is multiplied by x and y from the left),
because 1 ∈ R(x f_2):

[ 1 . . ]
=
t
[  x -x -1;  .  1  z;  .  .  1 ],
  t = 
[    x    1 x- z ].

By adding column 2 to column 1 and switching the first two rows
(this results in switching the first two columns in t)
we get [1, 0, 0] as the first column in the system matrix
(for the existence of these transformations see Lemma <ref>):

[ 1 . . ]
=
t
[  1  1  z;  0 -x -1;  .  .  1 ],
  t = 
[    1    x x- z ].

After multiplying x f_2 from the left by y, we have
1 ∉R(f'). Hence a further multiplication by (for example)
z from the left increases the rank: 

[  z -1  .  .;  .  y -1  z;  .  .  x -1;  .  .  .  1 ]
s =
[ .; .; .; 1 ],
  s =
[ zf';  f';   x;   1 ].

To summarize, there are essentially two different factorizations
(on the level of outer factors in Definition <ref>)
of f = (xy) (1-xz) (yz), namely

f = ( y( x(1-xz) ) ) (yz)= (xy)( ( (1-xz) z) y).




Now we come to the main definition which will
generalize that of left and right divisors
in the free associative algebra (Definition <ref>).
To be able to show in Theorem <ref>
that these definitions are indeed
equivalent on KX,
some preparation is necessary.





Let m ≥ 2 and f = f_1 f_2 ⋯ f_m be a product of
m elements f_i ∈F. By 𝒯 = 𝒯(f;f_1,f_2,…,f_m)
we denote the set of “multiplicative” derivation trees 
<cit.>
 (or parse trees), that is,
complete plane binary trees rooted at f with m leaves
f_1,f_2,…,f_m
<cit.>
 (or ordered binary trees).
Now we fix some τ_0 ∈𝒯
and call a subtree τ of τ_0 non-trivial if
it has at least two leaves.
In this case we denote by 
τ(l) (respectively τ(r))
the left (respectively right) subtree of τ
and write f_τ for the product constructed by τ,
that is, f_τ = f_τ(l) f_τ(r)
(illustrated in Figure <ref>).
The height (or length) of a subtree τ
is defined as τ = 0 in the trivial case and
recursively as
τ = 1 + max{τ(l), τ(r) }.



In a complete plane binary tree,
no leaf is left out (that is, even “trivial” leaves or subtrees appear)
and subtrees do not “cross”:
Say m=5 (as in Figure <ref>), f_2 = 1 and f_4 = f_3.
Then f = (f_1 f_2) f_5 is not “complete”,
f = (f_1 f_3) ( (f_2 f_4) f_5 ) is not “plane” (or “ordered”)
and f = (f_1 f_2) (f_3 f_4 f_5) is not “binary”.



Let = F^∙.
An element g∈ left divides f ∈,
written as g  f, if, for some m' < m ∈,
there exist f_1, f_2, …, f_m ∈
and τ_0 ∈𝒯(f;f_1,f_2,…,f_m)
such that g = f_1 f_2 ⋯ f_m' and f = g f_m'+1⋯ f_m
and
f_τ(l) is a left factor of
f_τ=f_τ(l) f_τ(r)
for all non-trivial subtrees τ of τ_0.

Two elements f,g ∈ are called left coprime
(in )
if for all h ∈ such that h f and h g
implies h ∈K^×,
that is, h is an element of the trivial group of units.
Right division f  g and the notion of
right coprime (in ) is defined in a similar way.
Two elements (in ) are called coprime
if they are left and right coprime.
















Let 0≠ p,q ∈F.
Then


  (i) (pq) =  p +  q - 1
  if p,q ∈KX,

  (ii) p = (p) + 1
  if p ∈KX,

  (iii) (p q) ≤(p) +  q -  1
  if 1 ∈ R(q),

  (iv) (p q) ≥(p) +  q -  1
  if p is a left factor of p q,

  (v) (p q) ≤ p + (q) - 1
  if 1 ∈ L(p) and

  (vi) (p q) ≥ p + (q) -  1
  if q is a right factor of p q.





The rank identities (i) and (ii) are immediate consequences
of the minimal polynomial multiplication
(Proposition <ref>)
and the minimal inverse (Theorem <ref>)
respectively.
The inequalities (iv) and (vi) follow directly from
the Definition <ref>.
To prove (iii),
let p and q be given by the minimal
admissible linear systems A'_p = (u'_p, A'_p, v'_p)
and A_q = (u_q, A_q, v_q) of dimension n'_p and n_q
respectively.
The construction of Proposition <ref>
yields an ALS of dimension n' (for p q),
hence 
(p q) ≤ n' = (p) +  q - 1.
The proofs of (v) and (iii) are similar.



Note that (iii) and (v) hold in particular for polynomials.
Further, recall from Example <ref>
that for (iv) to hold in the case of
p,q ∈KX
it is necessary but not sufficient
that p and q are left coprime.



To illustrate the idea of the following lemma we take
p = x y z and an arbitrary f with (f) = 2.
It is easy to see that (p f) ≥(p) - (f) = 2
(with equality for f=yz) because otherwise we could construct
an ALS of dimension (p f) + (f) -1 < (p).
Now say that f=xz. Then (p f) = (x y x) = 3.
However, for another polynomial q we get (f q) = 2 + (q)
thus (p f) + (f q) = 3 + 2 + (q) > 3 + (q) = (pq) + 1.

What is rather simple in a concrete example,
namely to verify that we cannot “insert” non-trivial
units turns out to be very technical since we have
to investigate the left and right families in detail.



Let p∈KX∖K
and f∈F∖K such that
p_i_0 p_i_0+1⋯ p_m f∉K^×
for all factorizations p = p_1 p_2 ⋯ p_m
into atoms and all i_0 ∈{ 1, 2, …, m }.
Then (pf) + (f) > (p) + 1.



For a fixed non-scalar polynomial p we consider
factorizations p=p_1 p_2 ⋯ p_m into m atoms p_j.
For notational simplicity let p_0 = p_m+1 = 1.
Here p_1, p_2, …, p_m always denote atoms.
Let

r = min{ (p_i_0p_i_0+1 ⋯p_m f) |p = p_1 p_2 ⋯p_m  and 
  i_0 ∈{ 1,2, …, m} }

and i_0 and p_1 p_2 ⋯ p_m such that this minimum is attained.
By assumption h = p_i_0 p_i_0+1⋯ p_m f∈F∖K
with (h) = r. Thus f = h p_i_0 p_i_0+1⋯ p_m
with non-scalar h. According to Theorem <ref>
there are four cases:


  * r ≥ 2 and (h) = r-1 for type (1,1),

  * r ≥ 2 and (h) = r for type (1,0),

  * r ≥ 2 and (h) = r for type (0,1) and

  * r ≥ 1 and (h) = r+1 for type (0,0).

Now fix an arbitrary factorization of p (into atoms q_i) and
any 1 < ℓ≤ m and
let p'=q_1 q_2 ⋯ q_ℓ-1 and p”=q_ℓ q_ℓ+1⋯ q_m
with ranks n' and n” respectively.
It is enough to show that

(p' h) + (hp”)
  > (p' p”) + 1
  = (p') + (p”).

We proceed as follows:
Depending on the four cases we construct
—using Proposition <ref> and Proposition <ref>—
admissible linear systems
for p'h and h p” respectively and find an upper bound
for the number of rows/columns that can be removed (due to K-linear
dependent entries in their left and right families).

We start by assuming type (1,1). 
For p'h we construct an ALS A' of dimension n_1 = n' + r-1
with the block decomposition (as linear representation according to
Theorem <ref>)

π' = (
[  0 u'  . ],
[ A'_1,1 A'_1,2 A'_1,3;      . A'_2,2 A'_2,3;      .      . A'_3,3 ],
[  .; v';  0 ]
).

For h p” we construct A” of dimension n_2 = n” + r-2
with the block decomposition

π” = (
[  0 u”  . ],
[ A”_1,1 A”_1,2 A”_1,3;      . A”_2,2 A”_2,3;      .      . A”_3,3 ],
[  .; v”;  0 ]
).

Let k'_t (respectively k'_s) be the size of block A'_1,1
(respectively A'_3,3) in π' and
k”_t (respectively k”_s) be the size of block A”_1,1
(respectively A”_3,3) in π”.
Firstly, we write the left and the right family of h in terms
of their respective family of h:
Let (s^h_1, s^h_2, …, s^h_r) and (t^h_1, t^h_2, …, t^h_r)
be the left and right family respectively of some minimal ALS for h.
Then s_h = (1, s^h_r-1, …, s^h_2) h
and t_h = h (t^h_r-1, …, t^h_2, 1)
are the families of a minimal ALS for h
constructed by Theorem <ref>.
Recall that row/column n' was eliminated in a system of dimension n'+r
to get A' and 
row/column r was eliminated in a system of dimension r-1+n”
to get A”.
Secondly, we take a closer look at the left families of A' and
A”. They are (without loss of generality)

    s'    = (s^p'_1 h, s^p'_2 h, …, s^p'_n'-1 h, s^h_1, s^h_2, …, s^h_r)
        and
    
    s”   = (h p”, s^h_r-1 h p”, …, s^h_2 h p”_r-1,
            s^p”_2, …, s^p”_n”_n”-1)

respectively.
The first observation is that k'_s = 0, that is,
the left family of A' is K-linearly
independent because 1 ∈ R(h) and Lemma <ref>.
The first r-1 and the last n”-1 components of s” are
K-linearly independent. At most r-1 (linear
combinations of) components in s” can be eliminated.
Hence we have k”_s ≤ r-1. However, we claim that

k”_s ≤r-2.

Assume to the contrary that (the rank of p” is large enough and)
k”_s = r-1, that is, the block A”_3,3 has dimension k”_s.
Then all to h corresponding (linear combinations of)
components in s” can
be eliminated by the last n”-1 polynomial entries.
If r=2 then h is a polynomial, so we assume r ≥ 3.
Since the left family (1,s_r-1^h, …, s_2^h)h of h
is K-linear independent and

(hp”) < (s_k^h hp”) < (p”) = n”

for all k ∈{ 2, 3, …, r-1 } it follows that these
s_k^h's are polynomials and therefore h is a polynomial because
it is of type (1,1). Hence h and p” have a non-trivial
(left) greatest common divisor which contradicts the minimality
of r = (h).
Thus k”_s ≤ r-2.
Thirdly, we take a closer look at the right families

    t'    = (t^p'_1, t^p'_2, …, t^p'_n'-1, p' t^h_1_n',
            p' t^h_2, …, p' t^h_r)    and
    
    t”   = (h t^h_r-1, …, h t^h_2, h,
              h t^p”_2, …, h t^p”_n”) 
       = h (t^h_r-1, …, t^h_2, 1_r-1,
              t^p”_2, …, t^p”_n”).

By assumption, the first r-1 and the last n” components in t” are
K-linearly independent.
Since the t^p”_i's are polynomials, we can eliminate
at most k ≤ r-2 polynomial (linear combinations of)
components in t”.
But then the corresponding k (linear combinations of)
components in t' are K-linearly independent of
(t_1^p', …, t_n'-1^p') because they are of the form
p't̃_i^h (see Lemma <ref>
or minimal polynomial multiplication).
By assumption, the first n' and the last r components in
t' are K-linearly independent.
Thus at most r-1-k components can be eliminated.
Hence we have k'_t + k”_t ≤ r-1. However, we claim that

k'_t + k”_t ≤r-2.

Assume to the contrary that k'_t + k”_t = r-1. Than
p't^h_r would also “vanish”, that is,

p'g = p'h + ∑_j=2^r-1 β_j p' t^h_j = ∑_i=1^n'-1 α_i t^p'_i
  = q 

with (q) < (p'). Hence g = κ q_ℓ-1⋯ q_ℓ'
for some ℓ' such that 1 ≤ℓ' < ℓ-1 and κ∈K.
By assumption h is of type (1,1),
but g is of type (0,0) by Theorem <ref>.
Therefore
g = h - h_0 for some (non-zero) h_0 of type (1,1).
But that would contradict K-linear independence
of the right family (t^h_1, t^h_2, …, t^h_r).
Finally, for h of type (1,1), we have

    (p'h) + (h p”)
         = n' + r-1 - (k'_s + k'_t) + n” + r-2 - (k”_s + k”_t) 
       ≥ n' + n” + 2r-3 - (r-2) - (r-2) 
       = n' + n” + 1 > (p'p”) + 1.

If h is of type (0,0), then h is of type
(1,1) and t” is K-linearly independent,
so we can use similar arguments.
If h is of type (1,0) then the systems
A' and A” are of dimensions
n' + r -1 and n”+r-1 respectively.
Their left families are

    s'    = (s^p'_1 h, s^p'_2 h, …, s^p'_n'-1 h, s^h_1, s^h_2, …, s^h_r)
        and
    
    s”   = (h p”, s^h_r h p”, …, s^h_2 h p”_r,
            s^p”_2, …, s^p”_n”_n”-1).

By similar arguments to the case (1,1) —s' is K-linearly
independent— we get k_s”≤ r-1.
The right families are

    t'    = (t^p'_1, t^p'_2, …, t^p'_n'-1, p' t^h_1_n',
           p' t^h_2, …, p' t^h_r_r-1)    and
    
    t”   = h (t^h_r, …, t^h_2, 1_r,
              t^p”_2, …, t^p”_n”).

Since neither h nor h is a polynomial,
at most r-2 components in t' or t” can be eliminated,
that is, k_t' + k_t”≤ r-2.
Therefore, for h of type (1,0), we have

    (p'h) + (h p”)
         = n' + r-1 - (k'_s + k'_t) + n” + r-1 - (k”_s + k”_t) 
       ≥ n' + n” + 2r-2 - (r-1) - (r-2) 
       = n' + n” + 1 > (p'p”) + 1.

If h is of type (0,1), then we have, by Lemma <ref>,
K-linearly independent right family t”.
By similar arguments we have k_t' ≤ r-1 and k_s'+k_s”≤ 2.
Thus, at the end,
we have shown that
(p f) + (f) > (p) + 1.




Let q ∈ H = KX^∙
and p ∈ = F^∙.
Then p  q implies q = ph with p,h ∈ H.



For some m' < m,
let p = f_1 f_2 ⋯ f_m' and q = p f_m'+1⋯ f_m
and τ_0 ∈𝒯(q;f_1,f_2,…,f_m) such that q_τ(l)
is a left factor of q_τ=q_τ(l) q_τ(r)
for all non-trivial subtrees τ of τ_0.
We have to show that q_τ_k∈ H for all
non-trivial subtrees τ_k of τ_0 with root in height k
by induction on k from 0 to (τ_0)-1.
For k=0 we have q_τ_0 = q ∈ H.
Without loss of generality assume that q_τ_k(r)
is a proper right factor of
q_τ_k = q_τ_k(l) q_τ_k(r)
(in this case q_τ_k(l) is a
proper left factor of q_τ_k;
nothing has to be shown for trivial factors), that is

    (q_τ_k q_τ_k(r))
      + (q_τ_k(r))    ≤ 1 + (q_τ_k)   and
    (q_τ_k(r))
      + (q_τ_k(r) q_τ_k)    ≤ 1 + (q_τ_k).

By assumption q_τ_k is a polynomial and thus all factorizations
into atoms have the same length, say ℓ_k
(which depends on τ_k).
We claim that q_τ_k(r) = κ g_ℓ_0⋯ g_ℓ_k
for some factorization q_τ_k = g_1 g_2 ⋯ g_ℓ_k,
some ℓ_0 ∈{ 1, 2, …, ℓ_k } and κ∈K.
Assume the contrary and apply Lemma <ref>
with p=q_τ_k and f = q_τ_k(r) to get the
contradiction

(q_τ_k q_τ_k(r))
  + (q_τ_k(r)) > 1 + (q_τ_k).

Thus q_τ_k(r)∈ H and
q_τ_k(l) = q_τ_k q_τ_k(r)∈ H.
In particular p = f_1 f_2 ⋯ f_m' ∈ H
and h = f_m'+1 f_m'+2⋯ f_m ∈ H.




Let p,q ∈ H = KX^∙.
Then p  q (respectively p  q)
if and only if p  q (respectively p  q)
in F.



Let p  q, that is q ∈ pH = { p h | h ∈ H }.
We show that p is a left factor of q = ph.
By Lemma <ref> (i) we get
(q) = (p) +  (p q) -1
and by (ii) we get
(q) + 1 = (p) +1 + (q p),
thus p is a left factor of ph = q
and therefore (m'=1, m=2 and a derivation tree τ_0
of height 1 in Definition <ref>)
p  q (in F).
Conversely,
we have to show that q ∈ pH.
But this follows directly from 
the assumption p  q
and Lemma <ref>.




Since the left (respectively right) division in KX
is the same as in F we can simplify notation
and use f  g instead of f  g
(respectively f g instead of f  g)
in the following.




Let = F^∙.
An element f∈∖K, that is,
a non-trivial unit (in F), is called (generalized) atom
(or irreducible)
if f = g_1 g_2 with g_1,g_2 ∈ and g_1  f implies that
either g_1 ∈K^× or g_2 ∈K^×.
Like in Definition <ref>,
the set of atoms in F is denoted by
(F).




Even in “simple” cases it is difficult to decide whether
an element is irreducible (in the general sense of Definition <ref>)
based on rational expressions.
As an example take f=1-xy and g=(1-zy). Then f g is
irreducible while  gf is reducible.
One has
to look on their minimal linear representations.
Minimal admissible linear systems for fg and gf are

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

respectively. 



In other words, a generalized atom can be created multiplicatively
out of two atoms. This phenomenon is somewhat curious.
As an example we consider f = f_1 f_2 for
f_1 = 1 - xyz and f_2 = 1- zyz. A minimal
admissible linear system for f is given by

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

Since (f_1) + (f_2) = 7 > 5 = (f) + 1,
neither f_1 nor f_2 is an outer factor (of f).
Indeed, f does not have any (non-trivial) outer factors.



Note the additional condition g_1  f
compared to Definition <ref>.
It is crucial.
Without f = 1-x = x · (x -1) would not
be an atom. (Actually there would not be any atoms
at all.)
However, x  (1-x)
because (x) + (x (1-x) ) = 4 > 3 = 1 + (1-x).



A reducible polynomial has only “polynomial” divisors.
The result of Lemma <ref> is stronger than
the assumptions for the equivalence of divisbility in Theorem <ref>,
in which one divisor is a polynomial.



A polynomial is an atom if and only if it is a generalized atom.



We have to show that
(KX) = (F) ∩KX.
Recall from Lemma <ref> that
for a polynomial p we have
g_1  p implies p = g_1 g_2 with polynomials g_1 and g_2.
Now both implications are immediate.




In the following we use “atom” as the general term
and “polynomial atom” if we want to emphasize that the
atom is an element in the free associative algebra.





§ MINIMAL MULTIPLICATION AND FACTORIZATION


Before we describe the correspondence of zero (lower left and upper right)
blocks in the system matrix of a minimal ALS and a non-trivial factorization,
we describe a construction of a minimal ALS A = (u,A,v) = (1,A,λ),
A = (a_ij),
for the product of
two non-zero elements f,g given by minimal admissible linear systems,
say of dimension n_f and n_g respectively,
if f is a left factor of fg.
According to Theorem <ref>
there are three cases (see also Figure <ref>, page fig:ft.minmul):



type    lower left zeros     “coupling”     upper right zeros 
(1,*)     n_g × (n_f-1) 
            ∃  1 ≤ i < n_f : a_i,n_f∉K
            (n_f-1)× (n_g-1) 

(*,1)     (n_g-1)× n_f 
            ∃  1 ≤ j < n_g : a_n_f,n_f+j∉K
            (n_f-1)× (n_g-1) 

(0,0)     n_g × n_f 
            ∀  i =1,…,n_f: a_i,n_f+1∈K
            n_f × (n_g-1) 



Note that for type (1,*) and (*,1) the “coupling condition”
must hold for each (admissibly) transformed system
because otherwise both types could be “derived” easily from
type (0,0).
To “reverse” the multiplication we need to transform an
ALS accordingly using transformations of the form

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

with entries α_ij, β_ij∈K.
To ensure invertibility we need P ≠ 0 and Q ≠ 0.




The minimal polynomial multiplication (Proposition <ref>)
can be formulated as a corollary to the following theorem.
The difficulty of the proof of the former is hidden
in the definition of outer factors, Definition <ref>.
To test if f is a left factor of fg in general
relies on techniques for minimization of linear representations
which is discussed in 
<cit.>
.



Let f,g∈F∖K be given by the
minimal admissible linear systems
A_f = (u_f, A_f, v_f) and A_g = (u_g, A_g, v_g)
of dimension n_f and n_g respectively.
Let n = n_f + n_g.
If f is a left factor of fg, then a minimal ALS for fg
is given by

A = 

Proposition <ref> with A = n-1
      if 1∈ L(f), 

Proposition <ref> with A = n-1
      if 1∈ R(g), 

Proposition <ref> with A = n
      if 1 ∉R(g) and 1 ∉L(f).





Since f is a left factor of fg, we have
(f) + (g) ≤(fg) + 1, thus

(fg) ≥(f) + (g) - 1 = A ≥(fg)

and hence minimality of A if 1 ∈ R(g) or 1 ∈ L(f),
that is, the first two cases/types (*,1) and (1,*).
For the last case/type (0,0) we distinguish four subcases.
Recall from Theorem <ref> that

(h) = 

(h) - 1     if h is of type (1,1), 

(h)     if h is of type (1,0) or (0,1) and 

(h)+1     if h is of type (0,0).


Since f is a left factor of fg, we have also

(gf) + 1 ≥(g) + (f).

Hence —by the minimal inverse on the right hand side—

(gf) +1 ≥
(g) + (f)     if 1 ∈ R(f) and 1 ∈ L(g), 

(g) + 1 + (f)     if 1 ∈ R(f) and 1 ∉L(g), 

(g) + (f)+1     if 1 ∉R(f) and 1 ∈ L(g) and 

(g) +1 + (f)+1     if 1 ∉R(f) and 1 ∉L(g).


Note that a priori we cannot assume minimality of A for fg,
since this is what we have to prove. Therefore we cannot use the minimal
inverse on the left hand side because we only know that,
for example, 1 ∈ L(g) implies 1 ∈ L(A) by construction.
However, by the minimal inverse, we know
—since g is of type (0,*)— that
g is of type (1,1) or (0,1)
and f is of type (1,1) or (1,0).
Hence we can use one of the first two cases
and get (fg) ≥(f) + (g).



Let A = (a_ij) be the system matrix of the ALS from
Theorem <ref>.
For type (1,*) there exists an i∈{1,2,…, n_f-1 }
such that a_i,n_f is non-scalar.
For type (*,1) there exists an j∈{ n_f+1, n_f+2, …, n }
such that a_n_f, j is non-scalar.
And for type (0,0) the entries a_i,n_f+1 are scalar
for i ∈{ 1, 2, …, n_f }.
We refer to that as coupling conditions.
Note that there is no transformation of the form (<ref>)
respecting the zero blocks yielding a “scalar coupling”
in type (1,*) (respectively type (*,1))
because that would contradict minimality of A_f
(respectively A_g)
which one can see after recalling the
construction of the product in Proposition <ref>.



Let h,f,g ∈F∖K be given by the minimal
admissible linear systems A = (1,A,λ),
A_f = (u_f,A_f,v_f) = (1,A_f,λ_f) and
A_g = (u_g,A_g,v_g) = (1,A_g,λ_g)
of dimension n, n_f and n_g respectively
such that f is a left factor of h = fg.

Type (1,*):
If f is of type (*,1) then there exists an
admissible transformation (P,Q) of the form (<ref>)
such that PAQ = (a_i,j) has


  * a lower left block of zeros of size n_g × (n_f-1),

  * an upper right block of zeros of size (n_f-1) × (n_g-1) and

  * there exists an i ∈{ 1,2,…, n_f-1 } 
  such that a_i,n_f is non-scalar

Type (*,1):
If g is of type (1,*) then there exists an
admissible transformation (P,Q) of the form (<ref>)
such that PAQ = (a_i,j) has


  * a lower left block of zeros of size (n_g-1) × n_f,

  * an upper right block of zeros of size (n_f-1) × (n_g-1) and

  * there exists an j∈{ n_f+1, n_f+2, …, n }
  such that a_n_f, j is non-scalar.

Type (0,0):
If f is of type (*,0) and g is of type (0,*)
then there exists an admissible transformation (P,Q)
of the form (<ref>)
such that PAQ = (a_i,j) has


  * a lower left block of zeros of size n_g × n_f,

  * an upper right block of zeros of size n_f × (n_g-1) and

  * a_i,n_f+1∈K for i ∈{ 1, 2, …, n_f }.




Let A'=(u',A',v') = (1,A',λ')
be the minimal ALS for h=fg constructed by Theorem <ref>
from λ_gλA_f and
λλ_gA_g.
The system matrix A'=(a'_ij) has —by construction—
appropriate (lower left and upper right) blocks of zeros
and —for type (0,0)—
scalar entries a'_i,n_f+1 for i ∈{ 1, 2, …, n_f }.
Since both systems A and A' for h are minimal,
there exists, by Theorem <ref>, an admissible transformation
(P,Q) such that PAQ = A'.
The right hand side Pv = v' does not change, hence
(P,Q) is of the form (<ref>).
The coupling conditions are fulfilled due to the construction
of the minimal multiplication.




To illustrate the importance of the coupling conditions
we consider h = x z y x given by the minimal ALS

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

Multiplication of type (0,1) for n_f = n_g = 2 would
violate the coupling condition, “creating” a non-minimal
ALS for g in h = fg.



Let h = fg ∈F∖K be given
by the minimal admissible linear system A = (u,A,v) = (1,A,λ)
of dimension n ≥ 2 and fix 1 < k ≤ n.
Assume that A has
a lower left block of zeros of size (n-k+1)× (k-1)
and an upper right block of zeros of size (k-1)× (n-k).
For a transformation (P,Q) let a'_ij denote the entries of PAQ.
If for each transformation (P,Q) of the form (<ref>)
respecting these zero blocks there exists an i∈{1,2,…, k-1 }
such that a'_i,k is non-scalar
then f is a left factor of type (*,1) of h
with (f) = k and (g) = n-k+1.



By assumption, A is of the (block) form

[ A_1,1 A_1,2     .;     . A_2,2 A_2,3;     . A_3,2 A_3,3 ]
[ s_1; s_k; s_3 ]
=
[   .;   .; v_3 ]

with square diagonal blocks A_1,1, A_2,2 and A_3,3 of size
k-1, 1 and n-k-1 respectively.
We duplicate the entry s_k in the left family by inserting a “dummy”
row (and column) to get the following ALS of dimension n+1:

[ A_1,1 A_1,2     0     .;     0     1    -1     0;     .     0 A_2,2 A_2,3;     .     0 A_3,2 A_3,3 ]
[ s_1; s_k; s_k; s_3 ]
=
[   .;   .;   .; v_3 ],

that is, “reversing” the construction from Proposition <ref>.
The subsystems of dimension k and n-k+1 are minimal for
f (due to the coupling condition) and g = μ s_k respectively,
otherwise we could construct an ALS for h of dimension n' < n,
contradicting minimality of A.
Clearly, 1 ∈ L(f).
By construction we have (f) + (g) = (h) + 1,
thus we only have to show that
(g) + (f) ≤(h) + 1
for f to be a left factor of h
by distinguishing four cases (like in the minimal multiplication)
and apply the minimal inverse. If h is of type (1,1),
then f is of type (1,1) and g is of type (*,1).
Thus (g)≤(g) and we get
(g) + (f) ≤(g) + (f)-1 = (h)+1.
The other cases are as easy.



Let h = fg ∈F∖K be given
by the minimal admissible linear system A = (u,A,v) = (1,A,λ)
of dimension n ≥ 2 and fix 1 ≤ k < n.
Assume that A has
a lower left block of zeros of size (n-k)× k
and an upper right block of zeros of size (k-1)× (n-k).
For a transformation (P,Q) let a'_ij denote the entries of PAQ.
If for each transformation (P,Q) of the form (<ref>)
respecting these zero blocks there exists an j∈{k+1, k+2, …, n }
such that a'_k,j is non-scalar
then f is a left factor of type (*,1) of h
with (f) = k and (g) = n-k+1.



By assumption, A is of the (block) form

[ u_1   .   . ]
= 
[ t_1 t_k t_3 ] 
[ A_1,1 A_1,2     .; A_2,1 A_2,2 A_2,3;     .     . A_3,3 ]

with square diagonal blocks A_1,1, A_2,2 and A_3,3
of size k-1, 1 and n-k respectively. We duplicate
the entry t_k in the right family by inserting a “dummy” column
(and row) to get the following ALS of dimension n+1:

[ u_1   .   .   . ]
= 
[ t_1 t_k t_k t_3 ] 
[ A_1,1 A_1,2     0     .; A_2,1 A_2,2    -1     0;     0     0     1 A_2,3;     .     .     0 A_3,3 ],

that is, “reversing” the construction from Proposition <ref>.
The subsystems of dimension k and n-k+1 are minimal for
f = μ t_k and g (due to the coupling condition) respectively,
otherwise we could construct an ALS for h
of dimension n' < n, contradicting minimality of A.
Clearly, 1 ∈ R(g). 
Showing that f is a left factor of h=fg is like
in Lemma <ref>.



Let h = fg ∈F∖K be given
by the minimal admissible linear system A = (u,A,v) = (1,A,λ)
of dimension n ≥ 2 and fix 1 ≤ k < n.
If A = (a_ij) has
a lower left block of zeros of size (n-k)× k,
an upper right block of zeros of size k× (n-k-1)
and a_i,k+1∈K for i ∈{ 1, 2, …, k }
then f is a left factor of type (*,0) of h with (f) = k
and g is of type (0,*) with (g) = n-k.



We get the subsystems A_f (for f) and A_g (for g)
directly from the construction of the multiplication in Proposition <ref>.
Non-minimality of one of them would contradict
minimality of A. As would 1 ∈ L(f) or 1 ∈ R(g)
using multiplication type (*,1) and (1,*) respectively.
The arguments for showing that f is left factor of h=fg
are similar to that in (the proof of) Lemma <ref>.




Let h ∈F with n = (h) ≥ 2
be given by the minimal admissible linear system A = (u,A,v).
Then h has a proper left factor f with (f) = k if and only if
there exists an admissible transformation (P,Q) of the form (<ref>)
such that PAQ is of “type” (1,*), (*,1) or (0,0)
as in Figure <ref>, page fig:ft.minmul.



Assuming a proper left factor of rank k,
Lemma <ref> applies.
Conversely, assuming such a transformation,
we get a proper left factor of rank k
by Lemma <ref> for type (1,*),
by Lemma <ref> for type (*,1) and
by Lemma <ref> for type (0,0).


Fixing a rank of a possible left factor
in KX,
a variant of 
<cit.>
 can be used to detect the lower left and upper right block of zeros
(of appropriate sizes depending on the type of factorization).
Notice that there is a misprint, the coefficients corresponding
to 1 ∈ X^* are missing. Here we have

    K[α,β] = K[
         α_1,1,…,α_1,n-1,α_2,1,…,α_2,n-1,
      …, α_n,1,…,α_n,n-1, 
       β_2,1,…,β_2,n,β_3,1,…,β_3,n,
      …,β_n,1,…,β_n,n ].

The coupling conditions for type (0,0) have to be implemented
directly by adding the coefficients corresponding
to x ∈ X for the “coupling vector”.
For type (1,*) and (*,1) one can test for a
“scalar” coupling first. If there is no solution
one can try to find an appropriate transformation
for the zero blocks only.



Let the element f ∈X be given by the
minimal ALS A = (u,A,v),

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

Before we start a “brute force” attack and try to find
(admissible) transformations (P,Q), say for multiplication
type (0,0) and two systems of dimension 2, we can easily
find out that f is regular. If it cannot be tranformed
into a polynomial form, that is, f is no polynomial,
we could check if f∈X.

Now we try to find a left factor f_1 of type (*,0)
with rank n_1 = 2 
and a right factor f_2 of type (0,*) with rank n_2 = 2,
that is, minimal multiplication type (0,0).
We need an invertible transformation (P,Q) of the form
(<ref>) such that P A Q = (a'_i,j) has a
2 × 2 lower left and a 2 × 1 upper right
block of zeros and a'_1,3,a'_2,3∈.
Additional to P =1 and Q = 1 we have
12 + 6 + 4 equations. A Gröbner basis for the ideal
generated by these 24 equations (computed by FriCAS
<cit.>
, using lexicographic order) is

    (    α_1,1 + α_1,2β_2,2β_3,3β_3,4 + α_1,3 , 
        α_1,2α_2,3α_3,1 -α_1,3α_2,2α_3,1 -1, 
       α_2,1 + α_2,2β_2,2β_3,3β_3,4 + α_2,3,
        α_3,2,   α_3,3,   α_4,2,   α_4,3, 
       β_2,2β_3,3^2 β_3,4 - β_2,3,
        β_2,2β_3,3β_4,4 - β_2,2β_3,4β_4,3 -1,
        β_2,3^2,   β_2,3β_3,4, 
       β_2,3β_4,4 - β_3,3β_3,4,
        β_2,4,   β_3,1,   β_3,2,   β_3,4^2, 
        β_4,1+1,   β_4,2 ).

Since β_3,4=0, the transformation (P,Q) is of the form

(P,Q) = (
[  α_1,1  α_1,2 -α_1,1      .;  α_2,1  α_2,2 -α_2,1      .;  α_3,1      0      0      .;  α_4,1      0      0      1;        ],
[     1     .     .     .; β_2,1 β_2,2     0     0;     0     0 β_3,3     0;    -1     0 β_4,3 β_4,4;       ]
)

with a solution over :

(P,Q) = (
[   2   0  -2   .;   0   1   0   .; 1/2   0   0   .;   0   0   0   1 ],
[  1  .  .  .;  0  1  0  0;  0  0  1  0; -1  0  0  1 ]
).

The transformed system P A Q is

[ -2 -2y     -2      .      0;    1+x      x     -1      0;      0      0  1/2 x   -1/2;      0      0     -2      x ]
s =
[ .; .; .; 1 ],

that is, f = f_1 f_2, with
f_1 = (1-xy) and f_2 =  (x^2 - 2),
which can be seen easily after applying the minimal
inverse on the two subsystems of dimension n_1 = n_2 = 2.
Both factors f_1,f_2 are atoms.
Over X the second factor f_2
is reducible, 
we have f_2 = (x - √(2)) (x + √(2)).



To find a solution in general (more systematically),
the primary decomposition of ideals can be used,
see for example
<cit.>
 and
<cit.>
.




§ EPILOGUE


The presented “free factorization theory”
is concrete enough to be implemented
in computer algebra software
to be able to apply it.
But some more theoretical questions remain open:
Is the extension of the “classical” factorization theory
(in free associative algebras) to the free field —assuming that
polynomial atoms (and their inverse) remain irreducible—
unique?
Is the free field (in this setting) a “similarity UFD”?
If so, given an element,
is the sequence of the ranks of the atoms of a factorization
an invariant (modulo permutations)?



§ ACKNOWLEDGEMENT


I thank Daniel Smertnig for the fruitful discussions about
non-commutative factorization and Michael Moßhammer for some
hints on graphs and trees and use this opportunity to
thank Sergey Berezin and Vladimir Vasilchuk
for their support in St. Petersburg in May 2017.
I am very grateful for the constructive feedback of the anonymous
referees to increase readability,
in particular for the suggested simplification of the definition
of left/right divisibility.


plain
alpha

tocsectionBibliography

