# On Factorizations of Upper Triangular Nonnegative Matrices of Order Three

Authors: Yi-Zhi Chen
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

LetT
3
(
N
0
) denote the semigroup of 3
×
3 upper triangular matrices with nonnegative integral-valued entries. In this paper, we investigate factorizations of upper triangular nonnegative matrices of order three. Firstly, we characterize the atoms of the subsemigroup S of the matrices in T
3
(
N
0
) with nonzero determinant and give some formulas. As a consequence, problems 4a and 4c presented by Baeth et al. (2011) are each half-answered for the case n
=
3. And then, we consider some factorization cases of matrix A in S with ρ
(
A
)
=
1 and give formulas for the minimum factorization length of some special matrices in S.


---

## Body

## 1. Introduction and Preliminaries

Upper triangular matrices are an important class of matrices, which lead to a broader study of all integral-valued matrices. There are many papers in the literature considering these matrices and similar topics.Factoring such matrices plays a vital role in the study of upper triangular matrices (see [1]). The problem of factoring matrices was studied by Cohn [2] as early as 1963. Later, Jacobson and Wisner [3, 4] and Ch’uan and Chuan [5, 6] investigated these factorization problems in the context of semigroups of matrices. Motivated by these results, Baeth et al. [7] applied the concepts of contemporary factorization theory to semigroups of integral-valued matrices and calculated certain important invariants to give a sense of how unique or nonunique factorization is in each of these semigroups. In [7], Baeth et al. presented six open problems.In this paper, we will investigate factorizations of upper triangular nonnegative matrices of order three. Also, we will consider open problem 4 presented in [7].Throughout this paper,N will denote the set of all positive integers and N
0
=
N
∪
{
0
}. Also, T
3
(
N
0
) will denote the semigroup of  3
×
3 upper triangular matrices with nonnegative integral-valued entries.In the following, analogous with [7] or [8], some concepts and preliminaries are recalled.Asemigroup is a pairing (
S
,
·
) where S is a set and · is an associative binary operation on S. When the binary operation is clear from context and A
,
B
∈
S, we will simply write A
B instead of A
·
B. If S contains an element I such that A
I
=
I
A
=
A for all A
∈
S, then I is theidentity of S.LetS be a semigroup with identity I. An element A
∈
S is aunit of S if there exists an element B
∈
S such that A
B
=
B
A
=
I. A nonunit A
∈
S is called anatom of S if whenever A
=
B
C for some elements B
,
C
∈
S, either B or C is a unit of S. The semigroup S is said to beatomic provided each nonunit element in S can be written as a product of atoms of S.LetS denote an atomic semigroup and let A be a nonunit element of S. The set(1)
L
(
A
)
=
t
:
A
=
A
1
A
2
⋯
A
t
with
each
A
i
an
atom
of
Sis called theset of lengths of
A.We denote byL
(
A
)
=
sup
⁡
L
(
A
) the longest (if finite) factorization length of A and  l
(
A
)
=
min
⁡
L
(
A
) the minimum factorization length of A. Theelasticity of A, denoted by (2)
ρ
(
A
)
=
L
(
A
)
l
(
A
)
,gives a coarse measure of how far away A is from having unique factorization. It is not hard to see that if A has a unique factorization A
=
A
1
A
2
⋯
A
t, whence L
(
A
)
=
{
t
} and so (3)
l
A
=
L
A
=
t
,
ρ
(
A
)
=
t
t
=
1
.Theelasticity of the semigroup
S, denoted by ρ
(
S
), is given by(4)
ρ
(
S
)
=
sup
⁡
ρ
A
:
A
∈
S
.If L
(
A
)
=
{
t
1
,
t
2
,
…
} with t
i
<
t
i
+
1 for each i, then the delta set of A is given by (5)
Δ
(
A
)
=
t
i
+
1
-
t
i
:
t
i
,
t
i
+
1
∈
L
Aand Δ
(
S
)
=
∪
A
∈
S
Δ
(
A
).This paper will be divided into two sections. In Section2, we will consider the semigroup S of upper triangular 3
×
3 matrices with nonnegative entries and nonzero determinant. Firstly, we characterize the atoms of the subsemigroup S of the matrices in T
3
(
N
0
) with nonzero determinant and give some formulas. As a result, problems 4a and 4c presented by Baeth et al. in [7] are each half-answered for the case n
=
3. And then, we consider some factorization cases of matrix A in S with ρ
(
A
)
=
1 and give formulas for the minimum factorization length of some special matrices in S.


## 2. Upper Triangular Nonnegative Matrices of Order Three

In this section we consider the semigroupS of upper triangular 3
×
3 matrices with nonnegative entries and nonzero determinant. In this case, I
3 is the only unit of S.For each pairi
,
j
∈
{
1,2
,
3
}, let E
i
,
j denote the matrix whose only nonzero entry is e
i
j
=
1.The following theorem gives some characterizations about the atoms ofS.Theorem 1.
LetS denote the subsemigroup of the matrices in T
3
(
N
0
) with nonzero determinant. The set of atoms of  S consists of the matrices (6)
X
12
=
1
1
0
0
1
0
0
0
1
,
X
13
=
1
0
1
0
1
0
0
0
1
o
r
X
23
=
1
0
0
0
1
1
0
0
1and, for each prime p, the matrices (7)
Y
11
=
p
0
0
0
1
0
0
0
1
,
Y
22
=
1
0
0
0
p
0
0
0
1
o
r
Y
33
=
1
0
0
0
1
0
0
0
p
.Proof.
Suppose thatX
i
j
=
X
1
X
2 for some X
1
,
X
2
∈
S. Since det
⁡
(
X
i
j
)
=
1, det
⁡
(
X
1
)
=
det
⁡
(
X
2
)
=
1 and we can write (8)
X
i
j
=
X
1
X
2
=
1
b
12
b
13
0
1
b
23
0
0
1
1
c
12
c
13
0
1
c
23
0
0
1
,where ∑
k
=
1
3
‍
b
i
k
c
k
j
=
1 and ∑
k
=
1
3
‍
b
h
k
c
k
l
=
0 if h
≠
i and l
≠
j. As a result, either X
1 or X
2 is the identity and hence X
i
j is an atom.
Note that the proofs thatY
i
i
(
1
≤
i
≤
3
) are atoms are similar; we only prove that Y
22 is an atom in the following. Suppose now that p is prime and Y
22
=
Y
1
Y
2, Y
1
,
Y
2
∈
S. Since p is prime, either(9)
Y
1
Y
2
=
1
b
12
b
13
0
p
b
23
0
0
1
1
c
12
c
13
0
1
c
23
0
0
1or (10)
Y
1
Y
2
=
1
b
12
b
13
0
1
b
23
0
0
1
1
c
12
c
13
0
p
c
23
0
0
1
.In either case, b
i
j
=
c
i
j
=
0 for 1
≤
i
<
j
≤
3. Consequently, either Y
1 or Y
2 is the identity and hence Y
i
i is an atom of S.
Finally, we will show that these are the only atoms ofS.
For any(11)
A
=
a
11
a
12
a
13
0
a
22
a
23
0
0
a
33
∈
S
,we can write(12)
A
=
I
3
+
a
33
-
1
E
3,3
I
3
+
a
23
E
2,3
I
3
+
a
13
E
1,3
·
I
3
+
a
22
-
1
E
2,2
I
3
+
a
12
E
1,2
I
3
+
a
11
-
1
E
1,1
=
1
0
0
0
1
0
0
0
a
33
1
0
0
0
1
a
23
0
0
1
1
0
a
13
0
1
0
0
0
1
·
1
0
0
0
a
22
0
0
0
1
1
a
12
0
0
1
0
0
0
1
a
11
0
0
0
1
0
0
0
1
.Thus, the set of atoms of S consists of the matrices A
=
I
3
+
E
i
,
j for each pair i and j with 1
<
i
<
j
<
3 or A
=
I
3
+
(
p
-
1
)
E
i
,
i for some prime p and 1
≤
i
≤
3.Recall that a unitriangular matrix is a matrix inT
3
(
N
0
) whose diagonal elements are all 1s. Denote Σ
(
A
)
=
Σ
1
≤
i
<
j
≤
3
a
i
j. From the proof of Theorem 1, we can immediately obtain the following corollary.Corollary 2.
LetS denote the unitriangular matrices in T
3
(
N
0
) and A
∈
S. Then A is an atom if and only if Σ
(
A
)
=
1.Hereafter, for any givenA
∈
T
3
(
N
0
) with nonzero determinant, we let r
(
A
) denote the number of (not necessarily distinct) prime factors of det
⁡
(
A
).Proposition 3.
LetS denote the subsemigroup of the matrices in T
3
(
N
0
) with nonzero determinant. If A can be factored as A
=
A
1
A
2
⋯
A
t with each A
i being an atom of S, then t
=
r
(
A
)
+
k, where (13)
k
=
i
:
A
i
∈
1
1
0
0
1
0
0
0
1
,
1
0
1
0
1
0
0
0
1
,
1
0
0
0
1
1
0
0
1
.Proof.
For eachi, A
i is an atom and thus det
⁡
(
A
i
) is either 1 or prime. Since (14)
det
⁡
(
A
)
=
det
⁡
(
A
1
)
det
⁡
(
A
2
)
⋯
det
⁡
(
A
t
)
,we have (15)
i
:
det
⁡
⁡
A
i
is
prime
=
r
(
A
)
.If k
=
|
{
i
:
det
⁡
(
A
i
)
=
1
}
|, then the length of this factorization of A is (16)
t
=
i
:
det
⁡
⁡
A
i
is
prime
+
i
:
det
⁡
⁡
A
i
=
1
=
r
(
A
)
+
k
.Lemma 4 (see [7, Theorem 4.4]).
LetS denote the subsemigroup of T
n
(
N
0
) of unitriangular matrices and let A
∈
S. Then L
(
A
)
=
Σ
(
A
).Theorem 5.
LetS denote the subsemigroup of the matrices in T
3
(
N
0
) with nonzero determinant and (17)
A
=
a
11
a
12
a
13
0
a
22
a
23
0
0
a
33
∈
S
.Then the following statements hold:(1)
L
(
A
)
=
r
(
A
)
+
a
12
+
a
13
+
a
23;
(2)
ifa
12
=
a
13
=
a
23
=
0, then l
(
A
)
=
r
(
A
)
=
L
(
A
) and ρ
(
A
)
=
1;
(3)
ifa
12
∣
a
11
a
22
(
a
12
>
0
), a
13
=
a
23
=
0, and then (18)
l
A
=
r
A
+
1
,
ρ
A
=
r
A
+
a
12
r
A
+
1
;
(4)
ifa
13
∣
a
11
a
33
(
a
13
>
0
), a
12
=
a
23
=
0, and then (19)
l
A
=
r
A
+
1
,
ρ
A
=
r
A
+
a
13
r
A
+
1
;
(5)
ifa
23
∣
a
22
a
33
(
a
23
>
0
), a
12
=
a
13
=
0, and then (20)
l
(
A
)
=
r
(
A
)
+
1
,
ρ
(
A
)
=
r
(
A
)
+
a
23
r
(
A
)
+
1
.Proof.
(1) Suppose thatA
=
A
1
A
2
⋯
A
t with each A
i being an atom of S. By Proposition 3, t
=
r
(
A
)
+
k where (21)
k
=
i
:
A
i
∈
I
3
+
E
12
,
I
3
+
E
13
,
I
3
+
E
23
.Note that the numbers of factors I
3
+
E
12 (I
3
+
E
13
,
I
3
+
E
23, resp.) of A are not more than a
12 (a
13
,
a
23, resp.). Then we have (22)
k
≤
a
12
+
a
13
+
a
23
=
Σ
(
A
)and thus (23)
L
(
A
)
≤
r
(
A
)
+
Σ
(
A
)
.On the other hand, from the proof of Theorem 1, we know that(24)
A
=
A
1
A
2
A
3
A
4
A
5
A
6
=
I
3
+
a
33
-
1
E
3,3
I
3
+
a
23
E
2,3
·
I
3
+
a
13
E
1,3
I
3
+
a
22
-
1
E
2,2
I
3
+
a
12
E
1,2
·
I
3
+
a
11
-
1
E
1,1
,and then,(25)
L
A
≥
L
A
1
+
L
A
2
+
L
A
3
+
L
A
4
+
L
A
5
+
L
A
6
=
r
(
A
1
)
+
r
(
A
4
)
+
r
(
A
6
)
+
L
(
A
2
)
+
L
(
A
3
)
+
L
(
A
5
)
=
r
(
A
)
+
Σ
1
≤
i
<
j
≤
n
a
i
j
=
r
(
A
)
+
Σ
(
A
)
.Thus, combining (23) and (25), we have L
(
A
)
=
r
(
A
)
+
Σ
(
A
).
(2) Suppose thatA is a diagonal matrix; that is, a
i
j
=
0 for all i
,
j
∈
{
1,2
,
3
} with i
<
j, and write t
=
r
(
A
)
+
k as in Proposition 3. If k
≥
1, then A contains at least one factor of X
12
=
I
3
+
E
12, X
13
=
I
3
+
E
13, or X
23
=
I
3
+
E
23, and then there is at least one superdiagonal entry of A that is not 0. This contradicts with the fact that A is a diagonal matrix. Thus, t
=
r
(
A
)
=
l
(
A
)
=
L
(
A
) and, in this case, (26)
ρ
(
A
)
=
L
(
A
)
l
(
A
)
=
1
.
(3) Suppose thata
12
∣
a
11
a
22
(
a
12
>
0
), a
13
=
a
23
=
0. Denote l
(
A
)
=
r
(
A
)
+
k as in Proposition 3. Notice that r
(
A
) is the number of (not necessarily distinct) prime factors of det
⁡
(
A
) and a
12
>
0. Then k
≥
1, and so l
(
A
)
≥
r
(
A
)
+
1. Since a
12
>
0, a
12
∣
a
11
a
22, a
12 can be factored as a product of one factor of a
11 and one factor of a
22; say a
12
=
a
11
′
a
22
′ where a
11
=
m
11
a
11
′ and a
22
=
n
22
a
22
′ for some positive integers m
11 and n
22. Factor A as (27)
A
=
A
1
A
2
⋯
A
8
=
a
33
′
0
0
0
1
0
0
0
1
1
0
0
0
n
22
0
0
0
1
1
1
0
0
1
0
0
0
1
1
0
0
0
1
0
0
0
a
33
·
1
0
0
0
a
22
0
0
0
1
a
11
0
0
0
1
0
0
0
1
m
11
0
0
0
1
0
0
0
1
·
1
0
0
0
a
22
′
0
0
0
1
.
By the above factorization ofA and (2), it is not hard to see that (28)
l
(
A
)
≤
l
(
A
1
)
+
l
(
A
2
)
+
⋯
+
l
(
A
8
)
=
r
(
A
)
+
1
.Thus, l
(
A
)
=
r
(
A
)
+
1.
In this case we immediately get(29)
ρ
(
A
)
=
r
(
A
)
+
Σ
(
A
)
r
(
A
)
+
1
=
r
(
A
)
+
a
12
r
(
A
)
+
1
.
Hence, (3) holds.
Similarly, we can show that (4) and (5) hold.Remark 6.
GivenA
∈
S, Theorem 5 provides a formula for L
(
A
). Consequently, open problems 4a and 4c in [7] are each half-answered for the case n
=
3.Theorem 7.
LetS denote the subsemigroup of the matrices in T
3
(
N
0
) with nonzero determinant and (30)
A
=
a
11
a
12
a
13
0
a
22
a
23
0
0
a
33
∈
S
.If A satisfies one of the following conditions,(1)
a
12
=
a
13
=
a
23
=
0;
(2)
a
11
=
a
22
=
a
33
=
1, a
12
=
0;
(3)
a
11
=
a
22
=
a
33
=
1, a
13
=
0;
(4)
a
11
=
a
22
=
a
33
=
1, a
23
=
0;
(5)
a
12
=
a
23
=
1, a
13
=
0;
(6)
a
12
=
a
23
=
1, a
23
=
0;
(7)
a
13
=
a
23
=
1, a
12
=
0,then ρ
(
A
)
=
1.Proof.
(1) Ifa
12
=
a
13
=
a
23
=
0, by Theorem 5, l
(
A
)
=
r
(
A
)
=
L
(
A
). In this case, ρ
(
A
)
=
1.
(2) Suppose thata
11
=
a
22
=
a
33
=
1 and a
12
=
0. If a
13
=
a
23
=
0, by (1), the conclusion holds. Now, assume that a
13
=
a
23
≠
0; the cases of that a
13
=
0, a
23
≠
0 or a
13
≠
0, a
23
=
0 can be proved similarly. In this case, X
12 is not an atomic factor of A and X
13 and X
23 are atomic factors of A. Note that X
13 can commute with X
23; then A only has the following factorization: (31)
A
=
1
0
1
0
1
0
0
0
1
a
13
·
1
0
0
0
1
1
0
0
1
a
23
,with ρ
(
A
)
=
1 and the minimum factorization length l
(
A
)
=
a
13
+
a
23.
Analogous with the proof of (2), we can show that (4) holds.
(3) Suppose thata
11
=
a
22
=
a
33
=
1 and a
13
=
0. If a
12
=
a
23
=
0, by (1), the conclusion holds. Now, assume that a
12
=
a
23
≠
0; the cases of that a
12
=
0, a
23
≠
0 or a
12
≠
0, a
23
=
0 can be proved similarly. In this case, X
13 is not an atomic factor of A and X
12 and X
23 are atomic factors of A. Note that X
12
X
23
=
X
23
X
12
X
13; the factorizations of A must satisfy that all the X
23 matrices are before X
12 matrices, and then A only has the following factorization: (32)
A
=
1
0
0
0
1
1
0
0
1
a
23
·
1
1
0
0
1
0
0
0
1
a
12
,with ρ
(
A
)
=
1 and the minimum factorization length l
(
A
)
=
a
12
+
a
23.
(5) Suppose thata
12
=
a
23
=
1 and a
13
=
0. In this case, X
13 is not an atomic factor of A, and X
12 and X
23 are atomic factors of A. Assume that A can be factored as A
=
A
1
A
2
⋯
A
t with each A
i being an atom; then t
=
r
(
A
)
+
k, where (33)
k
=
i
:
A
i
∈
X
12
,
X
23
.By Theorem 5 (1), k
≤
a
12
+
a
23
+
a
13
=
2. On the other hand, since a
12
=
a
23
=
1, X
12, X
23 are atomic factors of A, and we have k
≥
2. Thus, k
=
2. In this case, A can factorize as follows:(34)
A
=
I
3
+
a
33
-
1
E
3,3
I
3
+
E
2,3
I
3
+
a
22
-
1
E
2,2
·
I
3
+
E
1,2
I
3
+
a
11
-
1
E
1,1
=
1
0
0
0
1
0
0
0
a
33
1
0
0
0
1
1
0
0
1
1
0
0
0
a
22
0
0
0
1
·
1
1
0
0
1
0
0
0
1
a
11
0
0
0
1
0
0
0
1
.
So if we give the atomic factorizations of[
I
3
+
(
a
33
-
1
)
E
3,3
], [
I
3
+
(
a
22
-
1
)
E
2,2
], and [
I
3
+
(
a
11
-
1
)
E
1,1
], then we will obtain the atomic factorization of A with ρ
(
A
)
=
1 and the minimum factorization length l
(
A
)
=
r
(
A
)
+
2.
Analogous with the proof of (5), we can show that (6) and (7) hold.Example 8.
Consider(35)
A
=
1
0
2
0
1
3
0
0
1
∈
T
3
(
N
0
)
.Then by Theorem 7 (2), we can obtain the atomic factorization of A with ρ
(
A
)
=
1 and the minimum factorization length l
(
A
)
=
2
+
3
=
5 as follows: (36)
A
=
1
0
1
0
1
0
0
0
1
2
·
1
0
0
0
1
1
0
0
1
3
.Example 9.
Consider(37)
A
=
6
1
0
0
4
1
0
0
8
∈
T
3
(
N
0
)
.Then by Theorem 7 (5), we can obtain the atomic factorization of A with ρ
(
A
)
=
1 and the minimum factorization length l
(
A
)
=
r
(
A
)
+
2
=
9 as follows:(38)
A
=
1
0
0
0
1
0
0
0
2
3
1
0
0
0
1
1
0
0
1
1
0
0
0
2
0
0
0
1
2
·
1
0
0
0
1
1
0
0
1
2
0
0
0
1
0
0
0
1
3
0
0
0
1
0
0
0
1
.Theorem 10.
LetS denote the unitriangular matrices in T
3
(
N
0
) and (39)
A
=
1
a
12
a
13
0
1
a
23
0
0
1
∈
S
,
a
12
,
a
13
,
a
23
>
0
.Then we have (40)
l
(
A
)
=
a
12
+
a
23
,
i
f
a
13
≤
a
12
a
23
,
a
12
+
a
23
+
a
13
-
a
12
a
23
,
i
f
a
13
≥
a
12
a
23
.Proof.
It is a routine way to check thatX
12
X
13
=
X
13
X
12, X
23
X
13
=
X
13
X
23, and X
12
X
23
=
X
23
X
13
X
12. Hence the maximum length is achieved by putting all the X
23 matrices before the X
12 matrices. In this case, we have the form X
23
a
23
X
12
a
12
X
13
a
13. The minimum length is achieved by having as few as possible X
13 matrices, that is, by putting X
23 matrices after X
12 matrices. If a
13
≤
a
12
a
23, we can run out of X
13 matrices, leaving a form X
12
a
12
′
X
23
a
23
′
X
12
X
23
a
23
′′
X
12
a
12
′′, where these powers satisfy a
12
′
+
1
+
a
12
′′
=
a
12, a
23
′
+
a
23
′′
=
a
23, and a
12
′
a
23
+
a
23
′′
=
a
13. And, in this case, we have l
(
A
)
=
a
12
+
a
23. If a
13
≥
a
12
a
23, then we can put all the X
23 matrices after all of the X
12 matrices, getting the form X
12
a
12
X
23
a
23
X
13
a
13
-
a
12
a
23. Thus, in this case, we have l
(
A
)
=
a
12
+
a
23
+
a
13
-
a
12
a
23.Example 11.
Consider(41)
A
=
1
2
2
0
1
3
0
0
1
∈
T
3
(
N
0
)
.Then by Theorem 10, we can obtain a factorization of A with the minimum factorization length l
(
A
)
=
a
12
+
a
23
=
5 as follows:(42)
A
=
1
0
0
0
1
1
0
0
1
2
1
1
0
0
1
0
0
0
1
2
1
1
0
0
1
0
0
0
1
.Example 12.
Consider(43)
A
=
1
2
6
0
1
3
0
0
1
∈
T
3
(
N
0
)
.Then by Theorem 10, we can obtain a factorization of A with the minimum factorization length l
(
A
)
=
a
12
+
a
23
=
5 as follows: (44)
A
=
1
1
0
0
1
0
0
0
1
2
1
0
0
0
1
1
0
0
1
3
.Example 13.
Consider(45)
A
=
1
2
7
0
1
3
0
0
1
∈
T
3
N
0
.Then by Theorem 10, we can obtain a factorization of A with the minimum factorization length l
(
A
)
=
a
12
+
a
23
+
a
13
-
a
12
a
23
=
6 as follows: (46)
A
=
1
1
0
0
1
0
0
0
1
2
1
0
0
0
1
1
0
0
1
3
1
0
1
0
1
0
0
0
1
.



---

*Source: 960182-2015-03-29.xml*