## FACTORIZATION OF A PRIME MATRIX IN EVEN BLOCKS

## HAOMING WANG

Abstract. In this paper, a matrix is said to be prime if the row and column of this matrix are both prime numbers. We establish various necessary and sufficient conditions for developing matrices into the sum of tensor products of prime matrices. For example, if the diagonal of a matrix blocked evenly are pairwise commutative, it yields such a decomposition. The computational complexity of multiplication of these algorithms is shown to be O n ( 5 / 2 ). In the section 5, a decomposition is proved to hold if and only if every even natural number greater than 2 is the sum of two prime numbers.

## Contents

| 1.          | Introduction                          | Introduction                          |   1 |
|-------------|---------------------------------------|---------------------------------------|-----|
| 2.          | The case n = ab                       | The case n = ab                       |   4 |
| 3.          | The canonical diagonal form           | The canonical diagonal form           |   5 |
| 4.          | The computational complexity          | The computational complexity          |   6 |
| 5.          | The semi-prime and qausi-prime matrix | The semi-prime and qausi-prime matrix |   8 |
| 6.          | The non-square problem                | The non-square problem                |  10 |
| 7.          | Conclusion                            | Conclusion                            |  11 |
| References  | References                            | References                            |  12 |
| Appendix A. | Appendix A.                           | Examples of 4 × 4 matrices            |  12 |
| Appendix B. | Appendix B.                           | Factorization algorithm               |  13 |

## 1. Introduction

In this note, a prime matrix is a p × q matrix with both p and q prime numbers. Assume m and n are natural numbers with the prime decomposition. The aim of this paper is two-fold:

- · Reducing an m n × matrix into the sum of tensor products of prime matrices.
- · Reducing an n × n Hermite matrix into the sum of tensor products of prime matrices.

An m × n matrix might be developed into the sum of tensor products of prime matrices, In linear algebra, an m × n matrix A has the spectral decomposition in

2020 Mathematics Subject Classification. Primary 11Axx, 15Axx; Secondary 11A51, 15A69, 15A99.

Key words and phrases. Factorization of prime matrix, Diagonal Form, Tensor product, Matrix multiplication.

the sense that

$$( 1. 1 ) & & A = \sum _ { i = 1 } ^ { \min \{ m, n \} } \sigma _ { i } u _ { i } v _ { i } ^ { * }, \\ & &. &. &.$$

where U = [ u , u 1 2 , . . . , u m ] and V = [ v , v 1 2 , . . . , v n ] are orthogonal matrices. It's quite hard to compute the σ , u i i and v i when the size of matrix is large. The usual method relies on the computation of eigenvalues and eigenvectors of AA ∗ and A A ∗ . If n = m , with the aid of usual elimination algorithm, the computational complexity is O n ( 3 ), which increases the same as a cubic polynomial as the size of matrix gets large. However, this could be remedied provided a tensor form exists by the prime number decomposition theorem.

If m = p r 1 1 p r 2 2 . . . p r k k and n = q s 1 1 q s 2 2 . . . q s l l are the prime decomposition of m and n respectively, the m × n matrix A could be blocked according to the prime decomposition. For example, an m p ′ × n q ′ matrix A may be blocked as follows:

$$A & = \begin{bmatrix} q & \cdots & q \\ \vdots & \ddots & \vdots \\ A _ { m ^ { \prime } 1 } & \cdots & A _ { m ^ { \prime } n ^ { \prime } } \end{bmatrix} p \\ \text{where each $A_{ij}$ has $p$ rows and $q$ columns. If the diagonal set of $l$}$$

where each A ij has p rows and q columns. If the diagonal set of block sub-matrices { A ii } consists of a pairwise commutative family of matrices of p rows and q columns in the sense that the following equation is satisfied

$$A B ^ { * } = B A ^ { * }, \ \ A ^ { * } B = B ^ { * } A,$$

for each A and B in the family of matrices, then there exists a set of orthonormal column vectors { b i } and { c j } which diagonalizes each matrix A ii , say,

$$A _ { i i } = \sigma _ { i i } ^ { k } b _ { k } c _ { k } ^ { * },$$

where the sum is taken over repeated index. Therefore, the mp ′ × n q ′ block matrix can be developed into the sum of tensor products

$$( 1. 5 ) \quad ( 1 _ { m ^ { \prime } \times m ^ { \prime } } \otimes B ) ^ { * } A ( 1 _ { n ^ { \prime } \times n ^ { \prime } } \otimes C ) = \begin{bmatrix} q & \dots & q \\ \text{$\vdots$} & \ddots & \vdots \\ A ^ { \prime } _ { m ^ { \prime } 1 } & \dots & \text{diag} ( \sigma ^ { k } _ { m ^ { \prime } n ^ { \prime } } ) \end{bmatrix} ; \\ \text{where $1_{m\times n}$ denote the $m\times n$ matrix with entries all $1$, $B=[b_{1},b_{2},\dots,b_{p}]$, $C=$}$$

where 1 m n × denote the m × n matrix with entries all 1, B = [ b 1 , b 2 , . . . , b p ], C = [ c 1 , c 2 , . . . , c q ] and A ′ ij ( k, l ) = b ∗ k A c ij l . The symbol ⊗ means the tensor product defined for an m × n matrix A and p × q matrix B :

$$A \otimes B = \begin{bmatrix} a _ { 1 1 } B & a _ { 1 2 } B & \dots & a _ { 1 n } B \\ a _ { 2 1 } B & a _ { 2 2 } B & \dots & a _ { 2 n } B \\ \vdots & \ddots & \dots \\ a _ { m 1 } B & a _ { m 2 } B & \dots & a _ { m n } B \end{bmatrix} \\ \text{is defined to be a pm} \times q n \text{ block matrix. We will defer the non-square } \, ]$$

is defined to be a pm × qn block matrix. We will defer the non-square problem to the section 6.

The second aim of this paper is to reduce an n × n Hermite matrix A where A = A ∗ into the sum of tensor products in the following four type.

- T 1 The matrix A blocked according to (1.2) can be developed into the sum

$$A = \sum _ { i, j } B _ { i j } \otimes C _ { i j },$$

where B ij and C ij are n ′ × n ′ and q × q matrices respectively. T 1 1 The matrix A

2 blocked according to (1.2) can be developed into the sum

$$A = \sum _ { i } B _ { i } \otimes C _ { i },$$

where B i and C i are n ′ × n ′ and q × q matrices respectively. T 2 The matrix A blocked according to (1.2) can be developed into the sum

$$A = \sum _ { i, j } \alpha _ { i j } B _ { i } \otimes C _ { j },$$

where α ij , B i and C j are real numbers, n ′ × n ′ and q × q matrices respectively.

T 3 The matrix A blocked according to (1.2) can be developed into the sum

$$A = B \otimes C,$$

where B and C are n ′ × n ′ and q × q matrices respectively.

where the required properties for α ij , B ij , B , B, C i ij , C , C i will be explained in the section 2 explicitly. Here we only illustrate the main idea of this procedure.

- · First, examine whether the diagonal set of block matrix A in (1.2) is pairwise commutative:

$$A _ { i i } A _ { j j } = A _ { j j } A _ { i i }, \ \ i, j = 1, 2, \dots, n ^ { \prime },$$

This requires O n ( 5 / 2 ) computational complexity.

- · Second, examine whether the lower-triangular set of block matrix A in (1.2) is pairwise commutative.

$$A _ { i j } A _ { i ^ { \prime } j ^ { \prime } } = A _ { i ^ { \prime } j ^ { \prime } } A _ { i j }, \ \ i = j, \dots, n ^ { \prime }, i ^ { \prime } = j ^ { \prime }, \dots, n ^ { \prime }, j, j ^ { \prime } = 1, \dots, n ^ { \prime }$$

This requires O n ( 5 / 2 ) computational complexity.

- · Third, examine whether the diagonal set of the family of n ′ × n ′ matrices { B i } in (1.5) where B k,l i ( ) = b ∗ i A c kl i is pairwise commutative.

$$B _ { i } B _ { j } = B _ { j } B _ { i }, \ \ i, j = 1, 2, \dots, n ^ { \prime },$$

This requires O n ( 5 / 2 ) computational complexity.

- · Finally, compute the rank of n ′ × n ′ real matrix ( α ij ) where α ij = b B j ii b ∗ j via the similar diagonal form:

$$\begin{matrix} \text{use} \, \text{unagonal norm.} \\ P _ { 1 } P _ { 2 } \dots P _ { n } \begin{bmatrix} 1 & & O \\ & 1 & \\ & \ddots & \\ O & & \end{bmatrix} Q _ { n } ^ { - 1 } \dots Q _ { 2 } ^ { - 1 } Q _ { 1 } ^ { - 1 } \\ \text{is requires O} ( n ^ { 3 / 2 } ) \, \text{computational complexity.} \end{matrix}$$

This requires O n ( 3 / 2 ) computational complexity.

The total computational complexity of these algorithm is therefore O n ( 5 / 2 ), much less than that of the usual matrix multiplication, which is known to be O n ( 3 ). For this algorithm requires, in the worst case, n 3 multiplications of scalars and n 3 -n 2 additions for computing the product of two n × n matrices. This enables

us to utilize the above algorithm as a first examination so that if passed, it requires at most n 5 / 2 + n 2 -n 3 / 2 multiplications of scalars and n 5 / 2 -n 3 / 2 additions for multiplying two n × n matrices. These methods are introduced in section 4 and their algorithms are illustrated in Appendix B.

However, we are only interested in the case n is divisible, that is, n contains at least two prime factors that may not be distinct since if the order n of the square matrix A is a prime number, this problem has only trivial solution,. According to the fundamental theorem of arithmetic, every natural number has a unique decomposition as the product of prime numbers. The proof of arithmetic fundamental theorem is inductive so we use the induction to derive our desired decomposition too. We begin to start with a decomposable number n = ab where a and b are two natural numbers larger than 2.

$$2. \text{ THE CASE } n = a b$$

Here we give some assumptions about the reduction of an square matrix A of order n = ab into the sum of tensor products. Familiar with them is helpful in our coming discussion. Let's look at the Hermite case.

## Definition 2.1. Let A be an Hermite matrix of order ab . Block A as

$$( 2. 1 ) \quad \quad A = \begin{bmatrix} A _ { 1 1 } & A _ { 1 2 } & \dots & A _ { 1 a } \\ A _ { 2 1 } & A _ { 2 2 } & \dots & A _ { 2 a } \\ \vdots & & \ddots & \vdots \\ A _ { a 1 } & A _ { a 2 } & \dots & A _ { a a } \end{bmatrix} \\ \,. \quad \, \cdot \, \cdot \, \cdot \, \cdot \, \quad \text{r} \quad. \quad \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \end{bmatrix}$$

$$\begin{bmatrix} \vdots & \ddots & \vdots \\ A _ { a 1 } & A _ { a 2 } & \dots & A _ { a a } \end{bmatrix}$$

where each A ij is an Hermite matrix of order b . We assume A is decomposable of the type

- T 1 with respect to some column bases if there exist orthonormal column vectors { c j } of order b such that A can be developed into the sum

$$A = \sum _ { i, j } B _ { i j } \otimes C _ { i j }$$

/negationslash where C ij = c c i ∗ j and B ij = ( c ∗ i A kl c j ). In this case, B ij ( k, k ) = β i ( k δ ) ij . In a word, B ij vanishing on diagonal if i = . j

/negationslash

T 1 1 2 with respect to some mutually orthogonal row coefficients if it is T 1 decomposable and additionally, B ij = B δ ii ij , i.e. B ij vanishing if i = . j

- T 2 with respect to some row-column bases if it is T 1 decomposable and there exist further orthonormal column vectors { b i } of order a such that A can be developed into the sum

$$A = \sum _ { i, j } \alpha _ { i j } B _ { i } \otimes C _ { j },$$

where B i = b b i ∗ i and C j = c c j ∗ j .

T 3 totally decomposable with respect to some row-column bases if it is T 2 decomposable and additionally, there exist β , γ i j such that α ij = β γ i j and

$$A = B \otimes C$$

$$\text{where } B = \sum _ { i } \beta _ { i } b _ { i } b _ { i } ^ { * } \text{ and } C = \sum _ { j } \gamma _ { j } c _ { j } c _ { j } ^ { * }.$$

As for the non-Hermite case, we will assume A has n distinct eigenvalues. In this setting, replace the word orthogonal with independent and rephrase word for word in the above paragraph. We leave this work to the reader.

## 3. The canonical diagonal form

We define a binary operation between an m × n matrix A and a k × l matrix B when n and k has common divisor a as follows: block A = [ A , A , . . . , A 1 2 a ] and B = [ B ,B ,..., B ∗ 1 ∗ 2 ∗ ∗ a ] according to the partition of n = as columns of A and k = at rows of B and m × s sub-matrices A i and t × l sub-matrices B i , i = 1 2 , , . . . , a .

$$( 3. 1 ) \quad \ \ A \otimes _ { a, a } B = \sum _ { i = 1 } ^ { a } A _ { i } \otimes B _ { i } \quad \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$$

The result A ⊗ a,a B is a tm × ls matrix, dividing the factor of km × ln both by a . Besides, we define a unary operation on an m × n matrix A when m and n has both common divisor a : block A according to m = ar and n = as

$$\text{$row$ common unvisor $a$} \text{, $rows $a$ according $\upsilon m - a$ and $n$} - \\ ( 3. 2 ) & \begin{bmatrix} A _ { 1 1 } & A _ { 1 2 } & \dots & A _ { 1 s } \\ A _ { 2 1 } & A _ { 2 2 } & \dots & A _ { 2 s } \\ \vdots & \ddots & \vdots \\ A _ { r 1 } & A _ { r 2 } & \dots & A _ { r s } \end{bmatrix} \\ \text{where $A_{ij} s$ are $a\times a$ matrices and then define}$$

where A ij s are a × a matrices and then define

$$\bigoplus _ { a, a } A = \sum _ { i, j } A _ { i j }$$

Now return to our topic of decomposing an Hermite matrix of order n = ab . We will denote the block matrix C = ( C ij ) according to C ij as described in section 2 if it appears.

$$D _ { 1 } = \begin{bmatrix} B _ { 1 1 } & B _ { 1 2 } & \dots & B _ { 1 a } \\ B _ { 2 1 } & B _ { 2 2 } & \dots & B _ { 2 a } \\ \vdots & & \ddots & \vdots \\ B _ { a 1 } & B _ { a 2 } & \dots & B _ { a a } \end{bmatrix} \quad \quad D _ { 1 \frac { 1 } { 2 } } = \begin{bmatrix} B _ { 1 1 } & \dots & & O \\ & B _ { 2 2 } & & \vdots \\ & B _ { 2 2 } & & \vdots \\ \vdots & & \ddots & B _ { a a } \end{bmatrix}$$

$$\text{FIGURE 1. The canon-} \\ \text{ical diagonal form with} \\ A = \oplus _ { a, a } \left ( D _ { 1 } \otimes _ { a, a } C \right ) & & A = \oplus _ { a, a } \left ( D _ { 1 \frac { 1 } { 2 } } \otimes _ { a, a } C \right )$$

Since an Hermite matrix may have a canonical diagonal decomposition, we tabulate some equivalent conditions for them to hold explicitly in Table (1):

Table 1: Comparison of T , T 1 1 1 2 , T 2 and T 3 .

T 1 ⇔ A = ∑ i,j B ij ⊗ C ij where C ij = c c i ∗ j . ⇔ C ij = c c i ∗ j consists of common eigenvectors c i of A kk , independent of k , corresponding to eigenvalues B ii ( k, k ).

- T 1 1 2 ⇔ A = ∑ i B i ⊗ C i where C i = c c i ∗ i .
- ⇔ C i = c c i ∗ i consists of common eigenvectors c i of A kl , independent of k, l , corresponding to eigenvalues B k,l i ( ).
- T 2 ⇔ A = ∑ i,j α ij B i ⊗ C j where B i = b b i ∗ i and C j = c c j ∗ j ⇔ B i = b b i ∗ i , C j = c c j ∗ j consists of eigenvectors b i ⊗ c j of A , corresponding to eigenvalues α ij .
- ⇔ b i ⊗ c j are eigenvectors of A , corresponding to eigenvalues β γ i j .
- T 3 ⇔ A = B ⊗ C and B = ∑ i β b b i i ∗ i , C = ∑ j γ c c j j ∗ j .

From Table (1), there are some obvious deductions.

Theorem 3.1. Let A be an n × n Hermite matrix blocked in the form (2.1).

- 1. T 3 ⇒ T 2 ⇒ T 1 1 2 ⇒ T 1 .
- 2. The converses T 1 ⇒ T 1 1 2 and T 1 ⇒ T 2 and T 2 ⇒ T 3 are already made clear in the definition.
- 3. If the diagonal set { A ii } is pairwise commutative, then T 1 holds.
- 4. If the lower-triangular set { A ij } is pairwise commutative, then T 1 1 2 holds.
- 5. T 1 1 2 + b j is the eigenvector of B i , independent of i , corresponding to eigenvalue α ij ⇒ T 2 .
- 6. T 2 + α ij = β γ i j ⇒ T 3 ;
- 7. T 1 1 2 + B jj = ω B j where ω j is constant and B Hermite matrix ⇒ T 3 .

Proof. We only prove 3 and 4. This is because any permutation σ a of { 1 2 , , . . . , n } can be decomposed into the product of the replacement σ n = τ 1 τ 2 . . . τ m and commutativity means simultaneous diagonalization. /square

## 4. The computational complexity

Take the matrix multiplication for example, This algorithm requires, in the worst case, n 3 multiplications of scalars and n 3 -n 2 additions for computing the product of two square n × n matrices. Its computational complexity is therefore O n ( 3 ). If the n 2 × n 2 matrix blocked evenly in the form (2.1), we execute the following algorithm:

- · First, examine whether the diagonal set of block matrix A in

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00627v1-figure-0c82197c-0288-40e1-a868-900c3f2c8b13.jpg)

is pairwise commutative:

$$A _ { i i } A _ { j j } = A _ { j j } A _ { i i }, \ \ i, j = 1, 2, \dots, n,$$

This step requires, in the worst case 2 ( ) n 2 · n 3 = n 5 -n 4 multiplication of

$$\text{scalars and } 2 \binom { n } { 2 } \cdot ( n ^ { 3 } - n ^ { 2 } ) = n ^ { 5 } - 2 n ^ { 4 } + n ^ { 3 } \text{ additions.}$$

$$D _ { 2 } = \begin{bmatrix} \alpha _ { 1 1 } & \alpha _ { 1 2 } & \dots & \alpha _ { 1 a } \\ \alpha _ { 2 1 } & \alpha _ { 2 2 } & \dots & \alpha _ { 2 a } \\ \vdots & & \ddots & \vdots \\ \alpha _ { a 1 } & \alpha _ { a 2 } & \dots & \alpha _ { a a } \end{bmatrix}$$

$$D _ { 3 } = \begin{bmatrix} \beta _ { 1 } \gamma _ { 1 } & \beta _ { 1 } \gamma _ { 2 } & \dots & \beta _ { 1 } \gamma _ { a } \\ \beta _ { 2 } \gamma _ { 1 } & \beta _ { 2 } \gamma _ { 2 } & \dots & \beta _ { 2 } \gamma _ { a } \\ \vdots & & \ddots & \vdots \\ \beta _ { a } \gamma _ { 1 } & \beta _ { a } \gamma _ { 2 } & \dots & \beta _ { a } \gamma _ { a } \end{bmatrix}$$

Figure 3. The canonical diagonal form with A = D 2 · ( B ⊗ C ).

Figure 4. The canonical diagonal form with A = D 3 · ( B ⊗ C ).

- · Second, examine whether the lower-triangular set of block matrix A in

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00627v1-figure-86857a67-e9ac-44b7-badd-7c82af31a6cc.jpg)

is pairwise commutative.

$$A _ { i j } A _ { i ^ { \prime } j ^ { \prime } } = A _ { i ^ { \prime } j ^ { \prime } } A _ { i j }, \ \ i = j, \dots, n ^ { \prime }, i ^ { \prime } = j ^ { \prime }, \dots, n ^ { \prime }, j, j ^ { \prime } = 1, \dots, n$$

This step requires, in the worst case 2 ( n 2 2 ) · n = n 5 -n 3 multiplication of scalars and 2 ( n 2 2 ) · ( n -1) = n 5 -n 4 -n 3 + n 2 additions.

- · Third, examine whether the diagonal set of the family of n × n matrices { B ii } in







![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00627v1-figure-dbb66d70-5f95-42e2-ae07-83b75fb52190.jpg)









where B ii ( k, l ) = b ∗ i A c kl i is pairwise commutative.

$$B _ { i i } B _ { j j } = B _ { j j } B _ { i i }, \ \ i, j = 1, 2, \dots, n,$$

This step requires, in the worst case 2 ( ) n 2 · n 3 = n 5 -n 4 multiplication of

$$\text{scalars and } 2 \binom { n } { 2 } \cdot ( n ^ { 3 } - 1 ^ { 2 } ) = n ^ { 5 } - 2 n ^ { 4 } + n ^ { 3 } \text{ additions.} \\ \text{$row$} \cdot \text{ $n$} \cdot \text{ $n$} \cdot \text{ $n$} \cdot \text{ $n$} \cdot \text{ $n$} \cdot \text{ $n$} \cdot \text{ $n$} \cdot \text{ $n$} \cdot \text{ $n$} \cdot \text{ $n$} \cdot \text{ $n$} \cdot \text{ $n$} \cdot \text{ $n$} \cdot \text{ $n$} \cdot \text{ $n$} \cdot \text{ $n$} \cdot \text{ $n$} \cdot \text{ $n$} \cdot \text{ $n$} \cdot \text{ $n$} \cdot \text{ $t$}$$

- · Finally, examine whether the rank of n × n real matrix ( α ij ) is 1

$$\begin{bmatrix} \alpha _ { 1 1 } ( = \beta _ { 1 } \gamma _ { 1 } ) & \alpha _ { 1 2 } ( = \beta _ { 1 } \gamma _ { 2 } ) & \dots & \alpha _ { 1 n } ( = \beta _ { 1 } \gamma _ { n } ) \\ \alpha _ { 2 1 } ( = \beta _ { 2 } \gamma _ { 1 } ) & \alpha _ { 2 2 } ( = \beta _ { 2 } \gamma _ { 2 } ) & \dots & \alpha _ { 2 n } ( = \beta _ { 2 } \gamma _ { 1 } ) \\ \vdots & & \ddots & \vdots \\ \alpha _ { n 1 } ( = \beta _ { n } \gamma _ { 1 } ) & \alpha _ { n 2 } ( = \beta _ { n } \gamma _ { 2 } ) & \dots & \alpha _ { n n } ( = \beta _ { n } \gamma _ { n } ) \end{bmatrix}$$

where α ij = b B j ii b ∗ j . This could be done via the similar diagonal form:

$$\begin{matrix} \psi & \psi & \psi \\ & & & \\ & P _ { 1 } P _ { 2 } \dots P _ { n ^ { \prime } } \begin{bmatrix} 1 & & & O \\ & 1 & & \\ & & \ddots & \\ O & & & \end{bmatrix} Q _ { n ^ { \prime } } ^ { - 1 } \dots Q _ { 2 } ^ { - 1 } Q _ { 1 } ^ { - 1 } & & \\.. & &. &. & n \searrow & \psi & \psi & \dots \end{matrix}$$

This step requires, in the worst case 2 ( ) n 2 · n = n 3 -n 2 multiplication of scalars and 2 ( ) n 2 · ( n -1) = n 3 -2 n 2 + n additions.

Table 2: Computing multiplication of two square n 2 × n 2 matrices.

|         | Multiplications     | Additions             |
|---------|---------------------|-----------------------|
| T 1     | 2 A n 2 · n 3 + n n | n 5 - 2 n 4 + n 3     |
| T 1 1 2 | 2 A n 2 2 · n + n 4 | n 5 - n 4 - n 3 + n 2 |
| T 2     | 2 A n 2 2 · n + n 3 | 2 n 4 + n 3           |
| T 3     | 2 A n 2 · n + n 3   | n 3 - 2 n 2 + n       |

The computational complexity is hence not surprisingly O n ( 5 / 2 ), much less than usual multiplication.

Theorem 4.1. If A is an Hermite matrix of decomposable order n = p r 1 1 p r 2 2 . . . p r s s , then it has decomposable type 4 r 1 + ··· + r s , according to Definition 2.1. The computational complexity of this algorithm is also O n ( 5 / 2 ) .

## 5. The semi-prime and qausi-prime matrix

Definition 5.1 (Semi-prime matrix) . A semi-prime matrix is an m × n matrix where the minimum of m and n is a prime number.

Recall an m × n matrix A is said to have a left inverse if there exists an m × m matrix B such that BA = [ I m O ] and a right inverse if there exists an n × n matrix C such that AC = [ I n O ] . It is said be invertible if both inverses exist and quasi-invertible if there exists only one-side inverse.

Definition 5.2 (Quasi-prime matrix) . A matrix is said to be quasi-prime if it is the product of two quasi-invertible semi-prime matrices.

Two n × n matrices A and B are said to be orthogonal if AB ∗ = A B ∗ = O .

Conjecture 5.3 . Every n × n matrix where n is an even natural number greater than 2 is the sum of two orthogonal quasi-prime matrices.

Lemma 5.4. There are unique orthogonal matrices U and V for any quasi-prime matrix A such that U AV ∗ is diagonal, and the number of whose non-zero entries is a prime number.

Proof. Suppose there are two A = U V 1 1 = U V 2 2 decomposition of the m × n matrix A given by Definition 5.2, then by the uniqueness of spectral decomposition, the U , U 1 2 and V , V 1 2 are unitarily equivalent matrices. If the m × n matrix A has the spectral decomposition,

$$A = \sum _ { i = 1 } ^ { \min \{ m, n \} } \sigma _ { i } ^ { 2 } u _ { i } v _ { i } ^ { * } \\ + \quad \ v r \quad \ t$$

where U = [ u , u 1 2 , . . . , u m ] and V = [ v , v 1 2 , . . . , v n ] are orthogonal matrices, it suffices to prove that the number of non-zero σ i is a prime number. This follows from the unique decomposition of semi-prime matrix. /square

Corollary 5.5. Every quasi-invertible semi-prime matrix is quasi-prime.

Proof. Suppose m is the minimum of m and n . An m × n matrix that is semi-prime can be expressed as the product A = I m A . /square

Corollary 5.6. The product of two m × n and n × k quasi-prime matrices is a m × k quasi-prime matrix.

Theorem 5.7. The conjecture 5.3 holds true if and only if every even natural number greater than 2 is the sum of two prime numbers.

Proof. The necessity is easily seen from the preceding lemma and orthogonal relation. It suffices to prove the sufficiency. If an even natural number n larger than 2 can be developed as the sum of two prime numbers p and q , block the n × n matrix A as follows

$$\frac { \stackrel { p } { [ A _ { 1 1 } ] } q } { | O ] } ^ { p } _ { q } + \frac { \stackrel { p } { [ } | A _ { 1 2 } ] } { O | } ^ { p } _ { q } + \cdots + \frac { \stackrel { p } { [ } O | } { | A _ { 2 2 } ] } ^ { q } _ { q }$$

and choose two n × n orthogonal matrices U = [ u , u 1 2 , . . . , u n ] and V = [ v , v 1 2 , . . . , v n ] such that

$$U ^ { * } A V = \frac { \stackrel { p } { [ \Lambda _ { 1 } | } \stackrel { q } { O } ] } { [ O | \stackrel { \Lambda _ { 2 } } { \Lambda _ { 2 } } ] } p _ { q }$$

where Λ 1 = diag( λ , . . . , λ 1 p ) and Λ 2 = diag( λ p +1 , . . . , λ n ). Then block U and V as

$$\dots \cdots \cdots _ { 2 } \cdots \cdots _ { \circ \vee p + 1 }, \\ U = \begin{bmatrix} p & q \\ U _ { 1 } & | & U _ { 2 } ] & n \\ V = \begin{bmatrix} p & q \\ V _ { 1 } & | & V _ { 2 } ] & n \\ \text{yields} \end{bmatrix}$$

The spectral decomposition yields

$$A = U _ { 1 } \Lambda _ { 1 } V _ { 1 } ^ { * } + U _ { 2 } \Lambda _ { 2 } V _ { 2 } ^ { * }$$

Since U , V 1 1 , U 2 , V 2 and Λ 1 , Λ 2 are n × p , n × p , n × q, n × q semi-prime matrices and p × p, q × q invertible prime matrices, it follows from V ∗ 1 V 2 = U U ∗ 1 2 = O that the conjecture holds true. /square

Two m × n matrices A and B are said to be congruent if there are two invertible square matrices U and V of order m and n respectively such that UA = BV .

Conjecture 5.8 . For every natural number k , there are infinitely many prime numbers n and ( n -2 k ) × ( n ) semi-prime matrices that are not congruent to each other. In particular, the semi-prime matrices can be chosen quasi-invertible.

and a weak form of above

Conjecture 5.9 . For every natural number k , there are infinitely many prime numbers n and ( n -2 k ) × n quasi-prime matrices that are not congruent to each other.

Theorem 5.10. The conjecture 5.8 holds true if and only if there are infinitely many twin primes with gaps equal k ; The conjecture 5.9 holds true if and only if there are infinitely many twin primes with gaps less or equal than k .

## 6. The non-square problem

The non-square problem arises in real-life applications since in this case the matrix we take into consideration is non-Hermite. It's usually impossible to find a diagonal form but we will try another method to reduce the non-square matrix. For example, if m = p r 1 1 p r 2 2 . . . p r k k and n = q s 1 1 q s 2 2 . . . q s l l are the prime decomposition of m and n , the m × n matrix A could be blocked as an m p ′ 1 × n q ′ 1 matrix, say,

$$A & = \begin{bmatrix} q _ { 1 } & \dots & q _ { 1 } \\ A _ { 1 1 } & \dots & A _ { 1 n ^ { \prime } } \\ \vdots & \ddots & \vdots \\ A _ { m ^ { \prime } 1 } & \dots & A _ { m ^ { \prime } n ^ { \prime } } \end{bmatrix} p _ { 1 } \\ \text{where each } A _ { i j } \, \text{has } p _ { 1 } \, \text{rows and } q _ { 1 } \, \text{columns. If the diagonal set of } b$$

where each A ij has p 1 rows and q 1 columns. If the diagonal set of block sub-matrices { A ii } consists of a pairwise commutative family matrices of p 1 rows and q 1 columns in the sense that this relation is fulfilled:

$$A B ^ { * } = B A ^ { * }, \ \ A ^ { * } B = B ^ { * } A,$$

for each A and B in the family of matrices, then there exists two p 1 × p 1 and q 1 × q 1 orthogonal matrices C L = [ c L 1 , c L 2 , . . . , c L p 1 ] and C R = [ c R 1 , c R 2 , . . . , c R q 1 ] which diagonalizes each matrix A ii , say,

$$A _ { i i } = \sigma _ { i i } ^ { k } c _ { k } ^ { L } c _ { k } ^ { R * },$$

where the sum is taken over repeated index. Therefore, the mp ′ 1 × n q ′ 1 block matrix can be developed into the sum of tensor products

$$A = \sum _ { i, j } B _ { i j } \otimes C _ { i j }$$

/negationslash where C ij = c L R i c ∗ j , B ij = ( c L ∗ i A kl c R j ) and B ij ( k, k ) = β i ( k δ ) ij . In a word, B ij vanishing on diagonal if i = . Thus the j m × n matrix is said to be decomposable of the type

- T 1 with respect to some column bases if there exist orthonormal column vectors { c L j } and { c R j ′ } of order p 1 and q 1 respectively such that A can be developed into the sum

$$A = \sum _ { i, j } B _ { i j } \otimes C _ { i j }$$

/negationslash where C ij = c L R i c ∗ j , B ij = ( c L ∗ i A c kl R j ) . In this case, B ij ( k, k ) = β i ( k δ ) ij . In a word, B ij vanishing on diagonal if i = . j

/negationslash

T 1 1 2 with respect to some mutually orthogonal row coefficients if it is T 1 decomposable and additionally, B ij = B δ ii ij , i.e. B ij vanishing if i = . j

- T 2 with respect to some row-column bases if it is T 1 decomposable and there exist further orthonormal column vectors { b L i } and { b R i ′ } of order m ′ and n ′ respectively such that A can be developed into the sum

$$A = \sum _ { i, j } \alpha _ { i j } B _ { i } \otimes C _ { j },$$

where B i = b L R i b ∗ i and C j = c L R j c ∗ j .

- T 3 totally decomposable with respect to some row-column bases if it is T 2 decomposable and additionally, there exist β , γ i j such that α ij = β γ i j and

$$A = B \otimes C$$

$$\text{where $B=\sum_{i} \beta_{i} b_{i}^{L} b_{i}^{R*}$ and $C=\sum_{j}\gamma_{j}c_{j}^{L}c_{j}^{R*}$.} \\ \text{Equivalent conditions for these assumptions are similar to $1$}$$

Equivalent conditions for these assumptions are similar to Table 1 and Theorem 3.1 provided the commutativity relation replaced by (6.2).

## 7. Conclusion

There are still possible representations of matrix B ij ( k, l ) in T 1 . For example, B ′ ij = ( c ∗ k A c ij l ). We could develop the matrix A into the sum

$$A = \sum _ { i, j } B ^ { \prime } _ {.. } ( i, j ) \otimes C _ { i j }$$

and the canonical diagonal form varies according to the representation

$$D _ { 1 } ^ { \prime } = \begin{bmatrix} \text{diag} ( B _ { 1 1 } ( i, i ) ) & B _ { 1 2 } & \dots & B _ { 1 a } \\ B _ { 2 1 } & \text{diag} ( B _ { 2 2 } ( i, i ) ) & \dots & B _ { 2 a } \\ \vdots & & \ddots & \vdots \\ B _ { a 1 } & B _ { a 2 } & \dots & \text{diag} ( B _ { a a } ( i, i ) ) \end{bmatrix}$$

Figure 5. The canonical diagonal form D ′ 1

$$D _ { 1 \frac { 1 } { 2 } } ^ { \prime } = \begin{bmatrix} \text{diag} ( B _ { 1 1 } ( i, i ) ) & \text{diag} ( B _ { 1 2 } ( i, i ) ) & \dots & \text{diag} ( B _ { 1 a } ( i, i ) ) \\ \text{diag} ( B _ { 2 1 } ( i, i ) ) & \text{diag} ( B _ { 2 2 } ( i, i ) ) & \dots & \text{diag} ( B _ { 2 a } ( i, i ) ) \\ \vdots & & \ddots & \vdots \\ \text{diag} ( B _ { a 1 } ( i, i ) ) & \text{diag} ( B _ { a 2 } ( i, i ) ) & \dots & \text{diag} ( B _ { a a } ( i, i ) ) \end{bmatrix}$$

Figure 6. The canonical diagonal form D ′ 1 1 2

However, this dosen't indicate explicitly B ij as the projection of A onto C ij so we still adopt the former B ij as our assumption.

## References

- 1. Lei Cheng, Yik-Chung Wu, and H. Vincent Poor, Probabilistic tensor canonical polyadic decomposition with orthogonal factors , IEEE Transactions on Signal Processing 65 (2017), no. 3, 663-676.
- 2. , Scaling probabilistic tensor canonical polyadic decomposition to massive data , IEEE Trans. Signal Process. 66 (2018), no. 21, 5534-5548.
- 3. Yves Baudelaire Fomatati, On tensor products of matrix factorizations , Journal of Algebra 609 (2022), 180-216.
- 4. Johan H˚stad, a Tensor rank is NP-complete , J. Algorithms 11 (1990), no. 4, 644-654.
- 5. Tamara G. Kolda and Brett W. Bader, Tensor decompositions and applications , SIAM Review 51 (2009), no. 3, 455-500.
- 6. L. De Lathauwer, Decompositions of a higher-order tensor in block terms-Part I: Lemmas for partitioned matrices, Part II: Definitions and uniqueness , SIAM J. Matrix Anal. Appl. 30 (2008), pp. 1022-1032, 1033-1066.

## Appendix A. Examples of 4 × 4 matrices

This problem originates from decomposition of large covariance matrix with hidden structure in spatio-temporal statistics, wireless communication and mathematical physics etc. For example, the white noise problem states that there is a random signal, viewed as a stochastic process on the Minkovski space or a general manifold with

$$\left ( \text{A.1} \right ) & & \left \langle \eta ( \mathbf x, t ) \ | \ \eta ( \mathbf x ^ { \prime }, t ^ { \prime } ) \right \rangle = \delta ( \mathbf x - \mathbf x ^ { \prime } ) \delta ( t - t ^ { \prime } )$$

where δ is the Dirac function. The white noise has the identity matrix as its covariance which can be reduced into the tensor product of two factor matrix

$$I _ { q p } = I _ { p } \otimes I _ { q }$$

where I denotes the identity matrix. This demonstration holds true depends on the hidden structure between x and t . In fact, the white noise of form (A.1) has the matrix normal density with respect to two m × m and n × n Hermite matrices A and B and a m × n matrix M

$$( 2 \pi ) ^ { - m n / 2 } | A | ^ { - n / 2 } | B | ^ { - m / 2 } \text{etr} \left ( - \frac { 1 } { 2 } A ^ { - 1 } ( X - M ) B ^ { - 1 } ( X - M ) ^ { * } \right ) \prod _ { i, j } x _ { i j }$$

where etr( A ) means exp(tr A ) and | A | the determinant of A , if and only if, vec( X ) viewed as an mn × 1 vector pilling up the columns of the m × n matrix stacked on top of one another, is the multivariate normal distribution N mn (vec( M ,A ) ⊗ B ). The soul problem is to decide whether the covariance of vec( X ), an mn × mn Hermite positive definite matrix, is of the form A ⊗ B for some m × m and n × n Hermite matrices A and B . However, if the order n is a product of two divisors a and b , it's still impossible for all n × n matrices to possess a factorization of Kronecker product of two a × a matrix A and b × b matrix B . Let's look at this

## Example A.1. The following square matrix of order 4

$$\begin{bmatrix} \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stack | \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel { \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \textrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \textrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stack | \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stack. \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackrel \, \stackparen \, \, \,$$

is not a Kronecker product of two 2 × 2 matrices.

Therefore, it sounds absurd to presume such a tensor form since it cannot always describe all situations behind the hidden structure of mathematical models. This initiates our study of weak assumptions for matrices. Although not all square matrices of divisible order n = ab are of the form A × B for some a × a matrix A and b × b matrix B , it's still possible for a square matrix to have a reduced form of the sum of Kronecker products. The following three examples show how this could be done.

## Example A.2 (Partial diagonalization) .

$$\begin{bmatrix} 1 & 0. 5 & 0. 2 & 0. 1 \\ 0. 5 & 1 & 0. 5 & 0. 2 \\ 0. 2 & 0. 5 & 1 & 0. 5 \\ 0. 1 & 0. 2 & 0. 5 & 1 \end{bmatrix} & = \begin{bmatrix} 0. 5 & - 0. 1 \\ - 0. 1 & 0. 5 \end{bmatrix} \otimes \begin{bmatrix} 0. 5 & - 0. 5 \\ - 0. 5 & 0. 5 \end{bmatrix} + \begin{bmatrix} 0. 5 & 0. 2 \\ 0. 2 & 1. 5 \end{bmatrix} \otimes \begin{bmatrix} - 0. 5 & - 0. 5 \\ 0. 5 & 0. 5 \end{bmatrix} \\ & \quad + \begin{bmatrix} 1. 5 & - 0. 2 \\ - 0. 2 & 0. 5 \end{bmatrix} \otimes \begin{bmatrix} - 0. 5 & 0. 5 \\ - 0. 5 & 0. 5 \end{bmatrix} + \begin{bmatrix} 1. 5 & 0. 5 \\ 0. 5 & 1. 5 \end{bmatrix} \otimes \begin{bmatrix} 0. 5 & 0. 5 \\ 0. 5 & 0. 5 \end{bmatrix}$$

$$= A _ { 1 1 } \otimes B _ { 1 1 } + A _ { 1 2 } \otimes B _ { 1 2 } + A _ { 2 1 } \otimes B _ { 2 1 } + A _ { 2 2 } \otimes B _ { 2 2 }$$

where rank( B 11 ) = rank( B 12 ) = rank( B 21 ) = rank( B 22 ) = 1.

Example A.3 (Partially orthogonal diagonalization) .

$$\begin{bmatrix} 1 & 0. 5 & 0. 2 & 0. 3 \\ 0. 5 & 1 & 0. 3 & 0. 2 \\ 0. 2 & 0. 3 & 1 & 0. 5 \\ 0. 3 & 0. 2 & 0. 5 & 1 \end{bmatrix} & = \begin{bmatrix} 0. 5 & - 0. 1 \\ - 0. 1 & 0. 5 \end{bmatrix} \otimes \begin{bmatrix} 0. 5 & - 0. 5 \\ - 0. 5 & 0. 5 \end{bmatrix} + \begin{bmatrix} 1. 5 & 0. 5 \\ 0. 5 & 1. 5 \end{bmatrix} \otimes \begin{bmatrix} 0. 5 & 0. 5 \\ 0. 5 & 0. 5 \end{bmatrix} \\ & = A _ { 1 } \otimes B _ { 1 } + A _ { 2 } \otimes B _ { 2 } \end{bmatrix}$$

$$= A _ { 1 } \otimes B _ { 1 } + A _ { 2 } \otimes B _ { 2 }$$

where rank( B 1 ) = rank( B 2 ) = 1 and B 1 and B 2 are commutative.

Example A.4 (Totally orthogonal diagonalization) .

$$\text{Example A.4} & \text{(Iotally orthogonal diagonalization).} \\ \begin{bmatrix} 1 & 0. 1 5 & 0. 1 5 & 0. 5 \\ 0. 1 5 & 1 & 0. 5 & 0. 1 5 \\ 0. 1 5 & 0. 5 & 1 & 0. 1 5 \\ 0. 5 & 0. 1 5 & 0. 1 5 & 1 \end{bmatrix} & = \frac { 6 } { 5 } \begin{bmatrix} 0. 5 & - 0. 5 \\ - 0. 5 & 0. 5 \end{bmatrix} \otimes \begin{bmatrix} 0. 5 & - 0. 5 \\ - 0. 5 & 0. 5 \end{bmatrix} + \frac { 1 } { 2 } \begin{bmatrix} 0. 5 & - 0. 5 \\ - 0. 5 & 0. 5 \end{bmatrix} \otimes \begin{bmatrix} 0. 5 & 0. 5 \\ 0. 5 & 0. 5 \end{bmatrix} \\ & + \frac { 1 } { 2 } \begin{bmatrix} 0. 5 & 0. 5 \\ 0. 5 & 0. 5 \end{bmatrix} \otimes \begin{bmatrix} 0. 5 & - 0. 5 \\ - 0. 5 & 0. 5 \end{bmatrix} + \frac { 6 } { 5 } \begin{bmatrix} 0. 5 & 0. 5 \\ 0. 5 & 0. 5 \end{bmatrix} \otimes \begin{bmatrix} 0. 5 & 0. 5 \\ 0. 5 & 0. 5 \end{bmatrix}$$

$$= c _ { 1 1 } A _ { 1 } \otimes B _ { 1 } + c _ { 1 2 } A _ { 1 } \otimes B _ { 2 } + c _ { 2 1 } A _ { 2 } \otimes B _ { 1 } + c _ { 2 2 } A _ { 2 } \otimes B _ { 2 }$$

where rank( A 1 ) = rank( A 2 ) = rank( B 1 ) = rank( B 2 ) = 1, A 1 and A 2 are commutative and B 1 and B 2 are commutative.

## Appendix B. Factorization algorithm

School of Mathematics, Sun Yat-sen University, Guangzhou 510275 , China Email address : wanghm37@mail2.sysu.edu.cn

## Algorithm 0 An algorithm for tensor decomposition

```
Algorithm 0 An algorithm for tensor decomposition

Require: An n x n Hermite matrix A
Ensure: n = p _ { 1 } ^ { r _ { 2 } } p _ { 2 } ^ { r _ { 3 } } \cdots p _ { t } ^ { r _ { 4 } } \text{ with } p _ { 1 }, \dots, p _ { t } \text{ distinct primes and } r _ { 1 }, \dots, r _ { t } \geq 0
    m = n
    s <- 0                                                                                                                                                                                                         > Set global variable
    while m \geq 4 do                                                                                                                                                                                                        < Min algorithm
           for i = 1 \colon r do
                 for j = 1 \colon r [ i ] do
                          q = p [ j ]
                           m = n / q
                           Run Algorithm 1 with input A, n, q
                      end for
            end for
    end while
    
Algorithm 1 An algorithm for T _ { 1 }
```

## Algorithm 1 An algorithm for T 1

Require:

Ensure:

```
            end for
        end while
        
        Algorithm 1 An algorithm for T _ { 1 }
        
        Require:  An n × n Hermite matrix A
        Ensure:  A natural number n and a prime number p such that p | n
          m = n / p
          for i = 1 : m do
              for j = 1 : m do
                    A [ i, j ] <= A [ ( i p + 1 ) : ( i + 1 ) p, ( j p + 1 ) : ( j + 1 ) p ]
              end for
          end for
          for i, j = 1 : m do
              if  A [ i, i ] A [ j, j ] = A [ j, j ] A [ i, i ] then
                     Find the eigenvectors C <- [ c [ 1, \dots, c [ p ] ] for A [ i, i ]
              else
                    s <- [ s, 0 ]                                                                                                                                                                                                         > T _ { 1 } } ] failure!
                    quit
              end if
        end for
          for i = 1 : m do
              for k, l = 1 : p do
                     B [ i, i ] [ k, l ] <- c [ i ] * A [ k, l ] c [ i ]
              end for
          end for
          s <- [ s, 1 ]                                                                                                                                                                                                       >  T _ { 1 } } ] success!
              Run Algorithm 2 with input A, n, p
          return  B [ i, j ], C, s
```

## Algorithm 2 An algorithm for T 1 1 2

```
                                                                                                                                                                                                       
                                                                                                                                                                                                       

                                                                                                                                                                                                        }
                                                                                                                                                                                                      

                                                                                                                                                                                                       }

                                                                                                                                                                                                      
	                                                                                                                                                                                                       	                                                                                                                                                                                                      
---------------------------------------------------------------------------------------------------------------------
                                                                                                                                                                                                      	
                                                                                                                                                                                                      

	                                                                                                                                                                                                       }
```

```
16                                                                                                                                                                                                        
                                                                                                                                                                                                       

                                                                                                                                                                                                        }
                                                                                                                                                                                                      

                                                                                                                                                                                                       }
```
Haoming Wang
Factorization of a prime matrix in even blocks
In this paper, a matrix is said to be prime if the row and column of this
matrix are both prime numbers. We establish various necessary and sufficient
conditions for developing matrices into the sum of tensor products of prime
matrices. For example, if the diagonal of a matrix blocked evenly are pairwise
commutative, it yields such a decomposition. The computational complexity of
multiplication of these algorithms is shown to be $O(n^{5/2})$. In the section
5, a decomposition is proved to hold if and only if every even natural number
greater than 2 is the sum of two prime numbers.