where CH$_{n,1}$ (resp., CH$_{1,m}$) denotes the set of all the centrohermitian column (resp., row) vectors of length n (resp., m) and the Frobenius norm of a complex matrix A is defined by $||A||_{Frob} = \sqrt{trace(A^* A)}$, where A* stands for the adjoint matrix. Using the fact that the transformation ρ is unitary and the Frobenius norm is invariant by unitary transformations, we then have:

$$ \begin{aligned} & \min_{u \in \text{CH}_{n,1}, v_i \in \text{CH}_{1,m}} \left\| \sum_{i=1}^{r} D_i u v_i - M \right\|_{\text{Frob}} \\ & = \min_{u_{\rho} \in \mathbb{R}^{n \times 1}, v_{i_{\rho}} \in \mathbb{R}^{1 \times m}} \left\| \sum_{i=1}^{r} \rho(D_i) u_{\rho} v_{i_{\rho}} - \rho(M) \right\|_{\text{Frob}}. \end{aligned} \quad (65) $$

For more details, see [18]. Hence, the optimization problem eq. (64) is reduced to a real polynomial optimization problem eq. (65). This last problem will be studied in the future. In particular, the results developed in the paper on the solution space of the rank factorization problem eq. (4) should provide important information for investigating the corresponding polynomial optimization problem eq. (65).

Finally, we want to develop a noise sensitivity analysis of the method proposed here, i.e., analyze the continuity of our method to small variations of the matrix M that model measurement errors.

## References

[1] M. Barakat and M. Lange-Hegermann. The homalg project. Computeralgebra Rundbrief, pages 303–312, homalg project: https://homalg--project.github.io/, 2012.

[2] Y. Bouzidi, R. Dagher, E. Hubert, and A. Quadrat. Algebraic aspects of a rank factorization problem arising in vibration analysis. In Springer, editor, Maple in Mathematics Education and Research, Communications in Computer and Information Science, volume 1414, pages 104–118, 2020.

[3] C. Capdessus. Aide au diagnostic des machines tournantes par traitement du signal. PhD thesis, University of Grenoble, 1992.

[4] C. Capdessus and M. Sidahmed. Analyse des vibrations d'un engrenage : cepstre, corrélation, spectre. In Colloque francophone de traitement du signal et des images, volume 8, pages 365–372, 1991.

[5] F. Chyzak, A. Quadrat, and D. Robertz. Effective algorithms for parametrizing linear control systems over ore algebras. Applicable Algebra in Engineering, Communications and Computing, 16:319–376, 2005.

[6] F. Chyzak, A. Quadrat, and D. Robertz. Applications of Time-Delay Systems, chapter ORE-MODULES: A symbolic package for the study of multidimensional linear systems, pages 233–264, OREMODULES project: https://who.rocq.inria.fr/Alban.Quadrat/OreModules/index.html. Springer, 2007.

[7] T. Cluzeau and A. Quadrat. Factoring and decomposing a class of linear functional systems. Linear Algebra and Its Applications, 428:324–381, 2008.

[8] T. Cluzeau and A. Quadrat. OREMORPHISMS: A homological algebraic package for factoring, reducing and decomposing linear functional systems, volume 388, pages 179–196, OREMORPHISMS project: https://who.rocq.inria.fr/Alban.Quadrat/OreMorphisms.html. Springer, 2009.

[9] R. Dagher, E. Hubert, and A. Quadrat. RANKFACTORIZATION, a symbolic package for the study of the rank factorization problem. Technical report, Inria Report, 2023, project: https://who.rocq.inria.fr/Alban.Quadrat/RankFactorization.html.

[10] D. Eisenbud. Commutative Algebra with a View Toward Algebraic Geometry. Springer, 1985.

[11] A. Fabianśka and A. Quadrat. Applications of the Quillen-Suslin theorem to multidimensional systems theory, pages 23–106, QUILLENSUSLIN project: https://who.rocq.inria.fr/Alban.Quadrat/QuillenSuslin/index.html. de Gruyter publisher, 2007.
[12] G. P. G.-M. Greuel. *A Singular Introduction to Commutative Algebra*. Springer, Singular: https://www.singular.uni-kl.de/, 2002.

[13] R. D. Hill, R. G. Bates, and S. R. Waters. On centrohermitian matrices. *SIAM Journal on Matrix Analysis and Applications*, 11:128–133, 1990.

[14] E. Hubert. *Amplitude and phase demodulation of multi-carrier signals: Application to gear vibration signals*. PhD thesis, University of Lyon, France, 2019.

[15] E. Hubert, A. Barrau, and M. E. Badaoui. New multi-carrier demodulation method applied to gearbox vibration analysis. In *Proceedings of ICASSP*, 2018.

[16] E. Hubert, A. Barrau, Y. Bouzidi, R. Dagher, and A. Quadrat. On a rank factorisation problem arising in gearbox vibration analysis. In *Proceedings of the 21st IFAC World Congress*, 2020.

[17] E. Hubert, Y. Bouzidi, R. Dagher, A. Barrau, and A. Quadrat. Algebraic aspects of the exact signal demodulation problem. In *Proceedings of SSSC & TDS*, 2019.

[18] E. Hubert, Y. Bouzidi, R. Dagher, and A. Quadrat. Centrohermitian solutions of a factorization problem arising in vibration: Part I: Lee's transformation. In *Proceedings of European Control Conference*, 2021.

[19] E. Hubert, Y. Bouzidi, R. Dagher, and A. Quadrat. Centrohermitian solutions of a factorization problem arising in vibration: Part II: A coninvolutory matrix approach. In *Proceedings of European Control Conference*, 2021.

[20] E. Kunz. *Introduction to Commutative Algebra and Algebraic Geometry*. Birkhäuser, 2013.

[21] A. Lee. Centrohermitian and skew-centrohermitian matrices. *Linear Algebra and its Applications*, 29:205–210, 1980.

[22] W. D. Mark. Analysis of the vibratory excitation of gear systems: Basic theory. *The Journal of the Acoustical Society of America*, 63:1409–1430, 1978.

[23] D.-G. Northcott. *Finite Free Resolutions*. Cambridge University Press, 1976.

[24] A. V. Oppenheim and R. W. Schafer. *Discrete-Time Signal Processing*. Prentice Hall Signal Processing Series, 1999.

[25] J. J. Rotman. *Introduction to Homological Algebra*. Springer, 2009.

[26] B. L. V. D. Waerden. On varieties in multiple-projective spaces. *Indagationes Mathematicæ*, 81:303–312, 1978.

# 6 Appendix: The RANKFACTORIZATION package

The RANKFACTORIZATION package is dedicated to the rank factorization problem eq. (4) and its applications to demodulation problems and vibration analysis. The main algorithmic aspects of the rank factorization problem eq. (4) developed in this paper are implemented in this package. In particular, the general solutions of the rank factorization problem can be computed following Algorithm 3. More commands concerning the applications to the demodulation problems and vibration analysis will soon be added. The package is written in Maple and is built upon the OREMODULES package [6]. Its binary is freely available at https://who.rocq.inria.fr/Alban.Quadrat/RankFactorizationProblem.html.

In the next table, we list the main functions of the RANKFACTORIZATION package.
<table><caption>Table 1: Main functions of the RANKFACTORIZATION package</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>RankFactorization(M, L, k)</td><td>Compute the outputs of Algorithm 3, where M ∈ K<sup>m×n</sup>, L is a list of matrices D<sub>1</sub>, ..., D<sub>r</sub> ∈ K<sup>m×m</sup>, and k ∈ ₪[0, ..., r − 1]. Using the option “reduced” as the last argument of the function, a reduction of the sizes of the parameters q and t<sub>i</sub> in Algorithm 3 is attempted but at the cost of calculation time.</td></tr><tr><td>Solutions(M, L, k)</td><td>Compute the solutions eq. (57) of the rank factorization problem eq. (4), where M ∈ K<sup>m×n</sup>, L is a list of r matrices D<sub>1</sub>, ..., D<sub>r</sub> ∈ K<sup>m×m</sup>, and k ∈ ₪[0, ..., r − 1]. Using the option “reduced” as the last argument of the function, a reduction of the sizes of the parameters q and t<sub>i</sub> in Algorithm 3 is attempted but at the cost of calculation time.</td></tr><tr><td>IsSolution</td><td>Check again that the outputs of Solutions(M, L, k) define solutions of the corresponding rank factorization problem eq. (4).</td></tr></tbody></table>

In the next table, we list low-level functions of the RANKFACTORIZATION package. In this table, we shall note $\mathcal{R} = \mathbb{Q}[x_1, \dots, x_m]$.

<table><caption>Table 2: Low-level functions of the RANKFACTORIZATION package</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>Factorization(M<sub>1</sub>, M<sub>2</sub>, V, R)</td><td>Left factorize M<sub>1</sub> ∈ S<sup>a×b</sup> by M<sub>2</sub> ∈ S<sup>c×b</sup>, i.e., find (when possible) F ∈ S<sup>a×c</sup> such that M<sub>1</sub> = F M<sub>2</sub>, where S = R/⟨V<sub>1</sub>, ..., V<sub>s</sub>⟩ and V<sub>i</sub> ∈ R is the i<sup>th</sup> entry of the column matrix V.</td></tr><tr><td>FittingIdeal(M, i, R)</td><td>Compute a set of generators for the i<sup>th</sup> Fitting ideal Fitt<sub>i</sub>(M) of the R-module M = coker<sub>R</sub>(M) finitely presented by M ∈ R<sup>q×p</sup>. With the option “reduced”, it returns a Gröbner basis for this set for the tdeg monomial order.</td></tr><tr><td>IsInvertible(P, V, R)</td><td>Check whether or not the residue class of P in the factor ring R/⟨V<sub>1</sub>, ..., V<sub>s</sub>⟩ is invertible, where V<sub>i</sub> ∈ R is the i<sup>th</sup> entry of the column matrix V.</td></tr><tr><td>IsNilpotent(P, V, R)</td><td>Check whether or not the residue class of P in the factor ring R/⟨V<sub>1</sub>, ..., V<sub>s</sub>⟩ is nilpotent, where V<sub>i</sub> ∈ R is the i<sup>th</sup> entry of the column matrix V.</td></tr><tr><td>Saturation(P, L, R)</td><td>Compute the saturation ⟨L<sub>1</sub>, ..., L<sub>r</sub>⟩ : ⟨P⟩<sup>∞</sup> of the ideal ⟨L<sub>1</sub>, ..., L<sub>r</sub>⟩ w.r.t. P, where L<sub>i</sub> is the i<sup>th</sup> entry of the list L and P, L<sub>1</sub>, ..., L<sub>r</sub> ∈ R</td></tr><tr><td>Simplification(M, V, R)</td><td>Simplify the entries of M ∈ R<sup>q×p</sup> by computing their normal forms in the factor ring R/⟨V<sub>1</sub>, ..., V<sub>s</sub>⟩, where V<sub>i</sub> ∈ R is the i<sup>th</sup> entry of the column matrix V.</td></tr><tr><td>Syzygies(M, V, R)</td><td>Compute P ∈ S<sup>r×q</sup> such that ker<sub>S</sub>(M) = im<sub>S</sub>(P), where S = R/⟨V<sub>1</sub>, ..., V<sub>s</sub>⟩, V<sub>i</sub> ∈ R is the i<sup>th</sup> entry of the column matrix V, and M ∈ R<sup>q×p</sup>. If R = T[Y] and J<sub>s</sub> = Y P − 1, where P, V<sub>1</sub>, ..., V<sub>s−1</sub> ∈ T, then S is the localization A<sub>P</sub> of A = T/⟨V<sub>1</sub>, ..., V<sub>s−1</sub>⟩ at P.</td></tr><tr><td>ReducedSyzygies(M, V, R)</td><td>Reduce the output of the Syzygies function, i.e., reduce the integer r by removing trivial syzygies among the syzygies (but at the cost of calculation time). This function is used by the RankFactorization and Solutions functions when the option “reduced” is added.</td></tr></tbody></table>

Finally, Table 3 gives functions that are useful for studying the demodulation problems. More functions will be added in the future.
<table><caption>Table 3: Functions of the RANKFACTORIZATION package for the demodulation problem</caption><tr><td>AntiDiagonal(n)</td><td>Compute the antidiagonal matrix of the size n</td></tr><tr><td>LeeMatrix(n)</td><td>Compute a Lee matrix of size n. If the option "unitary" is added, then a unitary Lee matrix is returned.<br>If the option "unitary_symbolic" is added, then a symbolic unitary Lee matrix is returned which depends on a parameter q given as the third argument satisfying q<sup>2</sup> = 2</td></tr><tr><td>IsCentroHermitian(M)</td><td>Test whether or not a complex matrix M is centrohermitian</td></tr><tr><td>CentroHermitian(M)</td><td>Compute a centrohermitian matrix from M</td></tr></table>

Let us illustrate the functions of the RANKFACTORIZATION package with explicit examples.
To use the RANKFACTORIZATION package, the OREMODULES package has to be called. The Maple LinearAlgebra package can also be helpful to handle matrices.

> with(LinearAlgebra): with(OreModules): with(RankFactorization):

## 6.1 Low-level functions

Let us first demonstrate low-level functions of the RANKFACTORIZATION package (see Table 2).

### 6.1.1 FittingIdeal

Let us first introduce the commutative polynomial ring $\mathcal{R} = \mathbb{Q}[x_1, x_2, x_3x_4]$ in the OREMODULES package. To do that, the simplest way is to consider the Weyl algebra $A_4(\mathbb{Q})$ of partial differential operators in $x_i = \partial/\partial t_i$ for $i = 1, \dots, 4$, and consider ideals and matrices defined by polynomials in the $x_i$'s (which commutes with each other). In other words, we can do as follows:

> R := DefineOreAlgebra(seq(diff=[x[i],t[i]],i=1..4),polynom=[seq(t[i],i=1..4)]):

Let us now consider the following matrix

> M := Matrix([[a,b,c],[d,e,f],[g,h,j],[l,m,n]]);

$$M := \begin{bmatrix} a & b & c \\ d & e & f \\ g & h & j \\ l & m & n \end{bmatrix}$$

whose entries are symbols but can also be elements of the ring $R$. Let $\mathcal{M} = \text{coker}_{\mathcal{R}}(\cdot, M) = \mathcal{R}^{1 \times 3}/(\mathcal{R}^{1 \times 4} M)$ be the $\mathcal{R}$-module finitely presented by the matrix $M$. Let us now compute the different Fitting ideals of $\mathcal{M}$, i.e., $\text{Fitt}_i(\mathcal{M})$ for $i \in \mathbb{Z}_{\ge 0}$. We have:

> FittingIdeal(M,0,R);

$$[ae-jf-hbdj+bfg+cdh-ceg, aen-afm-bdn+bf1+cdm-cel, ahn-ajm-bgn+bjl+cgm-chl, dhn-djm-egn+ejl+fgm-fhl]$$

> FittingIdeal(M,1,R);

$$[ae-bd, ah-bg, am-bl, af-cd, aj-cg, an-cl, bf-ce, bj-ch, bn-cm, dh-eg, dm-el, dj-fg, dn-fl, ej-fh, en-fm, gm-hl, gn-jl, hn-jm]$$

> FittingIdeal(M,2,R);

$$[a, b, c, d, e, f, g, h, j, l, m, n]$$

> FittingIdeal(M,3,R);

[1]

> FittingIdeal(M,4,R);

[1]
Let us now consider a more explicit matrix $M$ with entries in $\mathcal{R}$.

> M := Matrix([[0,-x[3],0,-x[2]], [0,x[2],0,x[3]], [x[1]+x[4],0,x[1]+x[4],0]]);

$$M := \begin{bmatrix} 0 & -x_3 & 0 & -x_2 \\ 0 & x_2 & 0 & x_3 \\ x_1 + x_4 & 0 & x_1 + x_4 & 0 \end{bmatrix}$$

Let us consider the $\mathcal{R}$-module $\mathcal{M} = \text{coker}_{\mathcal{R}}(.M) = \mathcal{R}^{1 \times 4}/(\mathcal{R}^{1 \times 3} M)$ and let us compute $\text{Fitt}_i(\mathcal{M})$ for $i \in \mathbb{Z}_{\ge 0}$. We have:

> FittingIdeal(M,0,R);

[0]

> FittingIdeal(M,1,R);

$$[0, (x_1 + x_4)(x_2^2 - x_3^2), -x_2^2 x_1 + x_3^2 x_1 - x_2^2 x_4 + x_3^2 x_4]$$

Note that the elements of the above list are the different minors of all the $3 \times 3$ minors of $M$. These elements form a family of generators of the ideal $\text{Fitt}_1(\mathcal{M})$. But we can also compute a Gröbner basis for the total degree of this set to obtain a more tractable family of generators of $\text{Fitt}_1(\mathcal{M})$. This can be done by adding the option ‘reduced’ in the $\text{FittingIdeal}$ function as follows:

> FittingIdeal(M,1,R,"reduced");

$$[x_2^2 x_1 - x_3^2 x_1 + x_2^2 x_4 - x_3^2 x_4]$$

Similarly, we have:

> FittingIdeal(M,2,R);

$$[0, x_2(x_1 + x_4), x_3(x_1 + x_4), -x_2(x_1 + x_4), -x_3(x_1 + x_4), x_2^2 - x_3^2]$$

> FittingIdeal(M,2,R,"reduced");

$$[x_3x_1 + x_3x_4, x_2^2 - x_3^2, x_2x_1 + x_2x_4]$$

> FittingIdeal(M,3,R);

$$[0, x_2, x_3, -x_2, -x_3, x_1 + x_4]$$

> FittingIdeal(M,3,R,"reduced");

$$[x_3, x_2, x_1 + x_4]$$

> FittingIdeal(M,4,R);

[1]

### 6.1.2 Saturation

The **Saturation** function computes the saturation $\mathcal{I} : \langle P \rangle^{\infty}$ of the ideal $\mathcal{I}$ defined by the elements of the list given in the second argument of the **Saturation** function by a polynomial $P$ given in the first argument (the last one being the ring $\mathcal{R}$). Let us illustrate this function with simple examples.

> Saturation(x[1],[x[1]^2],R);

[1]

Therefore, we have $\langle x_1^2 \rangle : \langle x_1 \rangle^{\infty} = \{r \in \mathcal{R} \mid \exists k \in \mathbb{Z}_{\ge 0}, r x_1^k \in \langle x_1^2 \rangle\} = \langle 1 \rangle = \mathcal{R}$.

> Saturation(x[1]*x[2],[x[1]*x[2]*x[3]],R);

[x_3]

Therefore, we have $\langle x_1 x_2 x_3 \rangle : \langle x_1 x_2 \rangle^{\infty} = \langle x_2 \rangle$.

> Saturation(x[1],[x[2]^2,x[1]*x[3]-x[2]^2],R);

[x_3, x_2^2]
Therefore, we have $\langle x_2^2, x_1 x_3 - x_2^2 \rangle : \langle x_1 x_2 \rangle^\infty = \langle x_3, x_2^2 \rangle$.

$$> \text{Saturation}(x[3], [x[1]^5*x[3]^3, x[1]*x[2]*x[3], x[2]*x[3]^4, R);$$
$$[x_2, x_1^5]$$

Therefore, we have $\langle x_1^5 x_3^3, x_1 x_2 x_3, x_2 x_3^4 \rangle : \langle x_3 \rangle^\infty = \langle x_2, x_1^5 \rangle$.

### 6.1.3 IsNilpotent & IsInvertible

Let us first consider the `IsNilpotent` function which checks whether or not the residue class of an element $r \in \mathcal{R}$ – given as the first argument of the function – in the factor ring $S = \mathcal{R}/\mathcal{I}$ is nilpotent, where $\mathcal{I}$ is the ideal generated by the entries of the column matrix given in the second argument of the function (the last one being the ring $\mathcal{R}$). Equivalently, this function tests whether or not the ring $S_r$ – defined as the localization of the ring $S$ at the multiplicatively closed set $\{r^k\}_{k \in \mathbb{Z}}$ – is trivial, i.e., $S_r = 0$.

Let us check again that the residue class of $x_1$ in $S = \mathbb{Q}[x_1, \dots, x_4]/\langle x_1^2 \rangle$ is nilpotent

$$> \text{IsNilpotent}(x[1], \text{Matrix}([x[1]^2]), R);$$
$$\text{true}$$

whereas the residue class of $x_1 + 1$ in $S$ is not:

$$> \text{IsNilpotent}(x[1]+1, \text{Matrix}([x[1]^2]), R);$$
$$\text{false}$$

Let us give a few more simple examples by now considering the factor ring $S = \mathcal{R}/\langle x_1^3, x_1^2 x_2, x_1 x_2^2, x_2^3 \rangle$:

$$> \text{IsNilpotent}(x[1], \text{Matrix}([x[1]^3], [x[1]^2*x[2]], [x[1]*x[2]^2], [x[2]^3]), R);$$
$$\text{true}$$

Thus, the residue class of $x_1$ in $S$ is nilpotent.

$$> \text{IsNilpotent}(x[1]*x[2]+x[1], \text{Matrix}([x[1]^3], [x[1]^2*x[2]], [x[1]*x[2]^2], [x[2]^3]), R);$$
$$\text{true}$$

Thus, the residue class of $x_1 x_2 + x_1$ in $S$ is nilpotent. We can check again that $(x_1^2 x_2 + x_1)^3$ is a polynomial combination of the generators of $\mathcal{I}$:

$$> \text{Factorize}(\text{Matrix}([x[1]*x[2]+x[1]^3]), \text{Matrix}([x[1]^3], [x[1]^2*x[2]], [x[1]*x[2]^2], [x[2]^3]), R);$$

$$[ 1 \ 3x_1 \ 3x_1^2 \ x_1^3 ]$$

i.e., we have $(x_1^2 x_2 + x_1)^3 = x_1^3 + 3x_1(x_1^2 x_2) + 3x_1^2(x_1 x_2^2) + x_1^3(x_2^3)$.

$$> \text{IsNilpotent}(0, \text{Matrix}([x[1]^3], [x[1]^2*x[2]], [x[1]*x[2]^2], [x[2]^3]), R);$$
$$\text{true}$$

Let us now consider the `IsInvertible` function which checks whether or not the residue class of an element $r \in \mathcal{R}$ – given as the first argument of the function – in the factor ring $S = \mathcal{R}/\mathcal{I}$ is invertible, where $\mathcal{I}$ is the ideal generated by the entries of the column matrix given in the second argument of the function (the last one being the ring $\mathcal{R}$). For instance, let us test whether or not the residue class of $x_1$ in $S = \mathbb{Q}[x_1]/\langle x_1^2 \rangle$ is invertible:

$$> \text{IsInvertible}(x[1], \text{Matrix}([x[1]^2]), R);$$
$$\text{false}$$

Therefore, the residue class of $x_1$ in $S$ is not invertible (since it is nilpotent).

Similarly, let us test the invertibility of the residue class of $x_1 + 1$ in $S$.

$$> \text{IsInvertible}(x[1]+1, \text{Matrix}([x[1]^2]), R);$$
true

We obtain that it is invertible. We can check again this result by noticing that $(-x_1+1)(x_1+1) = 1 - x_1^2$ shows that the inverse of the residue class of $x_1+1$ in $S$ is the residue class of $-x_1+1$.

Let us now check whether or not $x_1+1$ is invertible in the ring $S = \mathcal{R}/\langle x_1^3, x_1^2 x_2, x_1 x_2^2, x_2^3 \rangle$:

$$ > \text{IsInvertible}(x[1]+1, \text{Matrix}([[x[1]^3], [x[1]^2*x[2]], [x[1]*x[2]^2], [x[2]^3]]), \mathbb{R}); \text{true} $$

To check this last point, we can note that the identity $(x_1^2 - x_1 + 1)(x_1 + 1) = x_1^3 + 1$ shows that the residue class of $x_1^2 - x_1 + 1$ is the inverse of the residue class of $x_1 + 1$ in $S$. This last identity can be obtained using the `LeftInverse` function of the `OREMODULES` package as follows:

$$ > \text{LeftInverse}(\text{Matrix}([[x[1]+1], [x[1]^3], [x[1]^2*x[2]], [x[1]*x[2]^2], [x[2]^3]]), \mathbb{R}); \quad [x_1^2 - x_1 + 1 \quad -1 \quad 0 \quad 0 \quad 0] $$

### 6.1.4 Syzygies, ReducedSyzygies, Factorization & Simplification

The `Syzygies` function computes the left kernel $ker_S(.M)$ of a matrix $M$, given as the first input of the function, whose entries belong to the ring $S = \mathcal{R}/\mathcal{J}$, where $\mathcal{R}$ is a commutative polynomial ring defined in the third argument and $\mathcal{J}$ is the ideal generated by the entries of the column matrix $V$ given in the second argument of the function.

The `ReducedSyzygies` function tries to reduce the number of generators of the left kernel $ker_S(.M)$ of a matrix $M \in S^{q \times p}$, where $S = \mathcal{R}/\mathcal{J}$, $\mathcal{R}$ is a commutative polynomial ring defined in the third argument and $\mathcal{J}$ is the ideal generated by the entries of the column matrix $V$ given in the second argument of the function.

Note that if $\mathcal{R} = \mathcal{T}[Y]$, where $\mathcal{T}$ is a commutative polynomial ring, $V = (V_1 \dots V_{r-1} \quad V_r)^T$, where $V_r = Y P - 1$ and $P, V_1, \dots, V_{r-1} \in \mathcal{T}$, then $S$ corresponds to the localization $A_P$ of $\mathcal{A} = \mathcal{T}/\langle V_1, \dots, V_{r-1} \rangle$ at $P$. Note that the index of $Y P - 1$ does not need to be the last one for the functions (it can be any).

The `Simplification` function computes the normal form of all the entries of a matrix $M$ given in the first argument of the function – in the ring $S = \mathcal{R}/\mathcal{J} = \mathcal{R}/\langle V_1, \dots, V_r \rangle$, where $\mathcal{R}$ is a commutative polynomial ring defined in the third argument and $\mathcal{J}$ is the ideal generated by the entries of the column matrix $V$ given in the second argument of the function.

Let us first illustrate these functions with a simple example.

> $M := \text{Matrix([[x[1]+1,0],[0,x[1]-1]]));$

$$ \begin{bmatrix} x_1+1 & 0 \\ 0 & x_1-1 \end{bmatrix} $$

Let us first compute the left kernel of $M$ when $V$ is the empty list, i.e., when $S = \mathcal{R}$:

> $\text{Syzygies}(M, [], \mathbb{R});$

INJ(2)

Thus, $ker_{\mathcal{R}}(.M) = 0$, i.e., the rows of $M$ are $\mathcal{R}$-linearly independent or equivalently $M$ has full row rank. Since $\mathcal{J} = \langle 0 \rangle$, the same result can be obtained by considering the matrix $0$ in the second entry:

> $\text{Syzygies}(M, \text{Matrix([[0]]), \mathbb{R}));$

INJ(2)

Let us now consider $V = [x_1^2 - 1]$, which is the determinant of $M$. Then, we have $S = \mathcal{R}/\langle x_1^2 - 1 \rangle$, and $ker_S(.M)$ is defined by:

> $K := \text{Syzygies}(M, \text{Matrix([[x[1]^2-1]]), \mathbb{R}));$

$$ K := \begin{bmatrix} x_1 - 1 & 0 \\ 0 & x_1 + 1 \end{bmatrix} $$
Equivalently, we have $ker_S(.M) = im_S(.K)$, i.e., the $S$-module $ker_S(.M)$ can be generated by the two rows of $K$. In particular, the residue classes of the entries of the matrix $KM$ in $S$ is 0. But if we use the standard product of the matrices $K$ and $M$ in $R$, we obtain

> $P := \text{Mult}(K,M,R);$

$$P := \begin{bmatrix} x_1^2 - 1 & 0 \\ 0 & x_1^2 - 1 \end{bmatrix}$$

which is not the zero matrix in $R$. To compute the product $KM$ in $S$, we have to use the Simplification function which computes the residue classes of the entries of the matrix $KM$ in $S$:

> $\text{Simplification}(P, \text{Matrix}([[x[1]^2-1]]), R);$

$$\begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix}$$

Let us now check whether or not the rows of the matrix $K$ are $S$-linearly independent, i.e., whether or not $K$ has full row rank or equivalently whether or not $ker_S(.M)$ is a free $S$-module.

> $\text{Syzygies}(K, \text{Matrix}([[x[1]^2-1]]), R);$

$$\begin{bmatrix} x_1 + 1 & 0 \\ 0 & x_1 - 1 \end{bmatrix}$$

We obtain $ker_S(.K) = im_S(.M)$, which shows that the $S$-module $M = \text{coker}_S(.M) = S^{1 \times 2}/(S^{1 \times 2} M)$ has the following cyclic free resolution:

$$... \xrightarrow{.M} S^{1 \times 2} \xrightarrow{.K} S^{1 \times 2} \xrightarrow{.M} S^{1 \times 2} \xrightarrow{.K} S^{1 \times 2} \xrightarrow{.M} S^{1 \times 2} \xrightarrow{\pi} M \longrightarrow 0.$$

Let us consider the localization $S_{x_1+1}$ of $S$ at the multiplicatively closed set $\{(x_1 + 1)^k\}_{k \in \mathbb{Z}}$ and let us compute the left kernel $ker_{S_{x_1+1}}(.K)$ of the matrix $K$ over $S_{x_1+1}$:

> $L := \text{Syzygies}(K, \text{Matrix}([[x[1]^2-1], [x[2] \cdot (x[1]+1)-1]]), R);$

$$L := \begin{bmatrix} 1 & 0 \\ 2 & 0 \end{bmatrix}$$

We obtain that $ker_{S_{x_1+1}}(.K) = im_{S_{x_1+1}}(.L)$. We note that the second row of $L$ is twice of the first one, i.e., $ker_{S_{x_1+1}}(.K) = S_{x_1+1}(1 \ 0)$, which shows that $ker_{S_{x_1+1}}(.K)$ is a free $S_{x_1+1}$-module.

The trivial linear dependence of the rows of the output of the Syzygies function can be removed using the ReducedSyzygies function (see more below):

> $\text{ReducedSyzygies}(K, \text{Matrix}([[x[1]^2-1], [x[2] \cdot (x[1]+1)-1]]), R);$

$$\begin{bmatrix} 2 & 0 \end{bmatrix}$$

Now, using the fact that $ker_S(.M) = im_S(.K)$ (see the above free resolution of $M$) and the fact that $S_{x_1+1}$ is a flat $S$-module, we have $ker_{S_{x_1+1}}(.M) = im_{S_{x_1+1}}(.K) = S_{x_1+1}(1 \ 0) \cong S_{x_1+1}$, i.e., $ker_{S_{x_1+1}}(.M)$ is a free $S_{x_1+1}$-module. This result is coherent with the fact that over the ring $S_{x_1+1}$, $M$ is reduced to

> $N := \text{Simplification}(M, \text{Matrix}([[x[1]^2-1], [x[2] \cdot (x[1]+1)-1]]), R);$

$$N := \begin{bmatrix} 2 & 0 \\ 0 & 0 \end{bmatrix}$$

and thus, $S_{x_1+1} \otimes_S M = \text{coker}_{S_{x_1+1}}(.M) = \text{coker}_{S_{x_1+1}}(.N) \cong S_{x_1+1}$ is a free $S_{x_1+1}$-module. For more details, see the proof of Theorem 4. Finally, note that a similar comment holds if we consider the localization $S_{x_1-1}$ of the ring $S$ at the multiplicatively closed set $\{(x_1 - 1)^k\}_{k \in \mathbb{Z}}$.

Let us now consider Example 6, i.e., the following matrix:

> $Q := \text{Matrix}([[x[1], x[2], 0], [x[2], x[1], 0]]);$
$$Q := \begin{bmatrix} x_1 & x_2 & 0 \\ x_2 & x_1 & 0 \end{bmatrix}$$

Let us compute the Fitting ideals $Fitt_i(Q)$'s of the $\mathcal{R}$-module $Q = \operatorname{coker}_{\mathcal{R}}(\cdot, Q) = \mathcal{R}^{1 \times 3}/(\mathcal{R}^{1 \times 2} Q)$:

$$\begin{array}{l} > \mathcal{J}_0 := \operatorname{FittingIdeal}(Q, 0, \mathcal{R}, \text{"reduced"}); \\ \qquad \qquad \qquad \qquad \qquad \qquad [0] \end{array}$$

$$\begin{array}{l} > \mathcal{J}_1 := \operatorname{FittingIdeal}(Q, 1, \mathcal{R}, \text{"reduced"}); \\ \qquad \qquad \qquad \qquad \qquad \qquad [x_1^2 - x_2^2] \end{array}$$

$$\begin{array}{l} > \mathcal{J}_2 := \operatorname{FittingIdeal}(Q, 2, \mathcal{R}, \text{"reduced"}); \\ \qquad \qquad \qquad \qquad \qquad \qquad [x_2, x_1] \end{array}$$

$$\begin{array}{l} > \mathcal{J}_3 := \operatorname{FittingIdeal}(Q, 3, \mathcal{R}, \text{"reduced"}); \\ \qquad \qquad \qquad \qquad \qquad \qquad [1] \end{array}$$

Let us now consider the rings $S_k = \mathcal{R}/\operatorname{Fitt}_k(Q)$ for $k = 0, 1, 2$, and let us compute $\operatorname{ker}_{S_k}(Q)$. Since the Syzygies function only computes left kernels, we shall compute $\operatorname{ker}_{S_k}(Q^T)$, where $Q^T$ is given by

$$\begin{array}{l} > \mathcal{Q}_t := \operatorname{Transpose}(Q); \end{array}$$

$$Q_t := \begin{bmatrix} x_1 & x_2 \\ x_2 & x_1 \\ 0 & 0 \end{bmatrix}$$

and finally transpose the obtained matrix. Hence, we first have

$$\begin{array}{l} > \mathcal{K}_0 := \operatorname{Transpose}(\operatorname{Syzygies}(\mathcal{Q}_t, \operatorname{Transpose}(\operatorname{convert}(\mathcal{J}_0, \operatorname{Matrix})), \mathcal{R})); \end{array}$$

$$\mathcal{K}_0 := \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}$$

which shows that $\operatorname{ker}_{S_0}(Q) = \operatorname{im}_{S_0}(\mathcal{K}_0)$. We have

$$\begin{array}{l} > \mathcal{K}_1 := \operatorname{Transpose}(\operatorname{Syzygies}(\mathcal{Q}_t, \operatorname{Transpose}(\operatorname{convert}(\mathcal{J}_1, \operatorname{Matrix})), \mathcal{R})); \end{array}$$

$$\mathcal{K}_1 := \begin{bmatrix} -x_2 & x_1 & 0 \\ x_1 & -x_2 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

which shows that $\operatorname{ker}_{S_1}(Q) = \operatorname{im}_{S_1}(\mathcal{K}_1)$. In particular, we can check again that all the entries of $\mathcal{Q} \mathcal{K}_1$ are reduced to zero in $S_1$:

$$\begin{array}{l} > \operatorname{Simplification}(\operatorname{Mult}(\mathcal{Q}, \mathcal{K}_1, \mathcal{R}), \operatorname{Transpose}(\operatorname{convert}(\mathcal{J}_1, \operatorname{Matrix})), \mathcal{R}); \\ \qquad \qquad \qquad \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix} \end{array}$$

We finally have

$$\begin{array}{l} > \mathcal{K}_2 := \operatorname{Transpose}(\operatorname{Syzygies}(\mathcal{Q}_t, \operatorname{Transpose}(\operatorname{convert}(\mathcal{J}_2, \operatorname{Matrix})), \mathcal{R})); \end{array}$$

$$\mathcal{K}_2 := \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

which shows that $\operatorname{ker}_{S_2}(Q) = \operatorname{im}_{S_2}(\mathcal{K}_2) = S_2^{3 \times 1}$.

Let us now consider Example 7, i.e., let us repeat the same computations with the following matrix:

$$\begin{array}{l} > \mathcal{Q} := \operatorname{Matrix}(\text{[}[x[1], x[2], 2*x[1]+x[2]]], \text{[}x[2], x[1], x[1]+2*x[2]\text{]}); \end{array}$$
$$Q := \begin{bmatrix} x_1 & x_2 & 2x_1 + x_2 \\ x_2 & x_1 & x_1 + 2x_2 \end{bmatrix}$$

We can check that that the Fitting ideals $Fitt_i(Q)$'s of the $\mathcal{R}$-module $Q = \operatorname{coker}_{\mathcal{R}}(\cdot, Q)$ are the same as the previous example (i.e., Example 6):

$$\begin{array}{l} > J0 := \operatorname{FittingIdeal}(Q, 0, \mathcal{R}, \text{"reduced"}); \\ \qquad \qquad \qquad \qquad \qquad \qquad \qquad [0] \end{array}$$

$$\begin{array}{l} > J1 := \operatorname{FittingIdeal}(Q, 1, \mathcal{R}, \text{"reduced"}); \\ \qquad \qquad \qquad \qquad \qquad \qquad \qquad [x_1^2 - x_2^2] \end{array}$$

$$\begin{array}{l} > J2 := \operatorname{FittingIdeal}(Q, 2, \mathcal{R}, \text{"reduced"}); \\ \qquad \qquad \qquad \qquad \qquad \qquad \qquad [x_2, x_1] \end{array}$$

$$\begin{array}{l} > J3 := \operatorname{FittingIdeal}(Q, 3, \mathcal{R}, \text{"reduced"}); \\ \qquad \qquad \qquad \qquad \qquad \qquad \qquad [1] \end{array}$$

Now, we have $\ker_{S_0}(Q.) = \operatorname{im}_{S_0}(K_{0.})$, where $K_0$ is defined by:

$$\begin{array}{l} > K0 := \operatorname{Transpose}(\operatorname{Syzygies}(\operatorname{Transpose}(Q), \operatorname{Transpose}(\operatorname{convert}(J0, \operatorname{Matrix})), \mathcal{R})); \\ \qquad K0 := \begin{bmatrix} 2 \\ 1 \\ -1 \end{bmatrix} \end{array}$$

We also have $\ker_{S_1}(Q.) = \operatorname{im}_{S_1}(K_{1.})$, where $K_1$ is defined by:

$$\begin{array}{l} > K1 := \operatorname{Transpose}(\operatorname{Syzygies}(\operatorname{Transpose}(Q), \operatorname{Transpose}(\operatorname{convert}(J1, \operatorname{Matrix})), \mathcal{R})); \\ \qquad K1 := \begin{bmatrix} 2 & 0 & 0 \\ 1 & -3x_2 & 2x_1 + x_2 \\ -1 & 2x_1 - x_2 & -x_2 \end{bmatrix} \end{array}$$

We then have $\ker_{S_2}(Q.) = \operatorname{im}_{S_2}(K_{2.})$, where $K_2$ is defined by:

$$\begin{array}{l} > K2 := \operatorname{Transpose}(\operatorname{Syzygies}(\operatorname{Transpose}(Q), \operatorname{Transpose}(\operatorname{convert}(J2, \operatorname{Matrix})), \mathcal{R})); \\ \qquad K2 := \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \end{array}$$

which shows that $\ker_{S_2}(Q.) = \operatorname{im}_{S_2}(K_2) = S_2^{3 \times 1}$.

Finally, let us illustrate the ReducedSyzygies and Factorization functions.

Let us first consider the matrix $Q$ defined in Example 4, i.e.:

$$\begin{array}{l} > Q := \operatorname{Matrix}(3, 2, [[-6*x[4], 10*x[1] - 9*x[2] - 10*x[3]], [3*x[1] + x[4], 0], [-2*x[4], 2*x[2]])); \\ \qquad Q := \begin{bmatrix} -6x_4 & 10x_1 - 9x_2 - 10x_3 \\ 3x_1 + x_4 & 0 \\ -2x_4 & 2x_2 \end{bmatrix} \end{array}$$

$$Q := \begin{bmatrix} -6x_4 & 10x_1 - 9x_2 - 10x_3 \\ 3x_1 + x_4 & 0 \\ -2x_4 & 2x_2 \end{bmatrix}$$

As in Example 5, we are interesting in computing $\ker_S(Q.)$, i.e., $\ker_S(Q^T)$, where $Q^T$ is defined by

$$> Q_t := \operatorname{Transpose}(Q);$$

$$Q_t := \begin{bmatrix} -6x_4 & 3x_1 + x_4 & -2x_4 \\ 10x_1 - 9x_2 - 10x_3 & 0 & 2x_2 \end{bmatrix}$$

and the ring $S$ is defined by $\mathcal{R}/\langle e_1, e_2, e_3 \rangle$, where $e_i$ is the $i^{th}$ entry of the following matrix:
```h
> e := Vector(column)(4, [2*x[1]*x[4] - 3*x[2]*x[4] - 2*x[3]*x[4], 3*x[1]*x[2]
> + x[2]*x[4], 2*x[1]^2 - 2*x[1]*x[3] + x[2]*x[4], 9*x[2]^2*x[4] + 6*x[2]*x[3]*x[4]
> + 2*x[2]*x[4]^2]);
```

$$e := \begin{bmatrix}
2x_1 x_4 - 3x_2 x_4 - 2x_3 x_4 \\
3x_1 x_2 + x_2 x_4 \\
2x_1^2 - 2x_1 x_3 + x_2 x_4 \\
9x_2^2 x_4 + 6x_3 x_4 x_2 + 2x_2 x_4^2
\end{bmatrix}$$

Using the Syzygies function, we obtain

```h
> K_t := Syzygies(Q_t, e, R);
```

$$K_t := \begin{bmatrix}
x_2 & x_4 \\
2x_1 - 2x_3 & 3x_4 \\
0 & 3x_1 + x_4 \\
0 & 9x_2 x_4 + 6x_3 x_4 + 2x_4^2
\end{bmatrix}$$

i.e., $ker_S(Q^T) = im_S(K_t)$. Equivalently, we have $ker_S(Q) = im_S(K_t^T)$, where $K_t^T$ is defined by:

```h
> Transpose(K_t);
```

$$\begin{bmatrix}
x_2 & 2x_1 - 2x_3 & 0 & 0 \\
x_4 & 3x_4 & 3x_1 + x_4 & 9x_2 x_4 + 6x_3 x_4 + 2x_4^2
\end{bmatrix}$$

We note that the above matrix has a column more than the matrix $K$ given in Example 5. It comes from the fact that the rows of $K_t$ have trivial relations as it can be checked by computing $ker_S(K_t)$:

```h
> K_t2 := Syzygies(K_t, e, R);
```

$$K_{t2} := \begin{bmatrix}
3x_4 & -x_4 & 0 & 0 \\
18x_3 & 9x_2 + 2x_4 & 0 & -3 \\
18x_1 & 2x_4 & 0 & -3 \\
0 & 6x_1 + 2x_4 & 0 & -3 \\
0 & 0 & 2x_4 & -1 \\
0 & 0 & x_2 & 0 \\
0 & 0 & 2x_1 - 2x_3 & 0 \\
0 & 0 & 0 & x_2 \\
0 & 0 & 0 & x_1 - x_3
\end{bmatrix}$$

Thus, we get $ker_S(K_t) = im_S(K_{t2})$, where some entries of $K_{t2}$ are invertible in $S$ as it can be checked:

```h
> map(IsInvertible, K_t2, e, R);
```

$$\begin{bmatrix}
\text{false} & \text{false} & \text{false} & \text{false} \\
\text{false} & \text{false} & \text{false} & \text{true} \\
\text{false} & \text{false} & \text{false} & \text{true} \\
\text{false} & \text{false} & \text{false} & \text{true} \\
\text{false} & \text{false} & \text{false} & \text{true} \\
\text{false} & \text{false} & \text{false} & \text{true} \\
\text{false} & \text{false} & \text{false} & \text{false} \\
\text{false} & \text{false} & \text{false} & \text{false} \\
\text{false} & \text{false} & \text{false} & \text{false}
\end{bmatrix}$$

Hence, certain syzygies defined by the rows of the matrix $K$ can be removed. There are many strategies to remove these “trivial syzygies”. The ReducedSyzygies function implements one method to do that. Applying the ReducedSyzygies function to the matrix $Q_t$, we obtain a set of generators of $ker_S(Q_t)$ with three generators, namely, the rows of the following matrix

```h
> K_tbis := ReducedSyzygies(Q_t, e, R);
```
$$K_{tbis} := \begin{bmatrix} x_2 & x_4 \\ 2x_1 - 2x_3 & 3x_4 \\ 0 & 3x_1 + x_4 \end{bmatrix}$$

whereas the Syzygies function returned four generators, namely, the four rows of the matrix $K_t$. Therefore, we have $ker_S(.Q_t) = im_S(.K_{tbis})$, i.e., $ker_S(Q.) = im_S(K_{tbis}^T)$, where $K_{tbis}^T$ is defined by:

> Transpose(K_tbis);

$$\begin{bmatrix} x_2 & 2x_1 - 2x_3 & 0 \\ x_4 & 3x_4 & 3x_1 + x_4 \end{bmatrix}$$

We find again the matrix $K$ given in Example 5. Finally, since $ker_S(.Q_t) = im_S(.K_t) = im_S(.K_{tbis})$, the rows of $K_t$ (resp., $K_{tbis}$) belong to $im_S(.K_{tbis})$ (resp., $im_S(.K_t)$), which means that $K_t = F K_{tbis}$ and $K_{tbis} = G K_t$ for certain matrices $F$ and $G$ having entries in $S$. These two matrices can be computed using the Factorization function as follows:

> Factorization(K_t,K_tbis,e,R);

$$F := \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 2x_4 \end{bmatrix}$$

> G := Factorization(K_tbis,K_t,e,R);

$$G := \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix}$$

Finally, let us consider Example 12, where the following matrix $B$ is considered

> B := Matrix([[x[4]*(5*x[2]/2+x[3]), x[3]*(3*x[1]+x[4]), 3*x[4]*(5*x[2]/2+x[3])]]);

$$B := \begin{bmatrix} x_4 \left( \frac{5x_2}{2} + x_3 \right) & x_3 (3x_1 + x_4) & 3x_4 \left( \frac{5x_2}{2} + x_3 \right) \end{bmatrix}$$

whose transpose matrix is defined by

> B_t := Transpose(B);

$$B_t := \begin{bmatrix} x_4 \left( \frac{5x_2}{2} + x_3 \right) \\ x_3 (3x_1 + x_4) \\ 3x_4 \left( \frac{5x_2}{2} + x_3 \right) \end{bmatrix}$$

Considering the ring $S = \mathbb{R}/\langle e_1, e_2, e_3 \rangle$, where the $e_i$'s are defined by:

> e1 := (10*x[1]-9*x[2]-10*x[3])*(3*x[1]+x[4]);

> e2 := (2*x[1]-3*x[2]-2*x[3])*x[4];

> e3 := (3*x[1]+x[4])*x[2];

$$\begin{aligned} & (10x_1 - 9x_2 - 10x_3) (3x_1 + x_4) \\ & (2x_1 - 3x_2 - 2x_3) x_4 \\ & (3x_1 + x_4) x_2 \end{aligned}$$

Let us compute the right kernel of $B$, i.e., the left kernel of $B^T$, over two localizations of the ring $S$ at multiplicative set $\{h_i^k\}_{k \in \mathbb{Z}}$, where $h_1$ and $h_2$ are respectively defined by:

> h1 := x[4]*(5*x[2]/2+x[3]);

> h2 := (3*x[1]+x[4])*x[3];
> Transpose(C_h1t);

$$ \begin{bmatrix} 3 & 0 \\ 0 & -6x_4 \\ -1 & 9x_2 + 6x_3 + 2x_4 \end{bmatrix} $$

Let us check that $im_{S_{h_1}}(.C_{h_1}) = im_{S_{h_1}}(.C_{1t})$. To do that, using Factorization function, we can check that $C_{1t}$ (resp., $C_{h_1}$) is a left factor of $C_{h_1}$ (resp., $C_{1t}$):

> Factorization(C_h1t,C_1tbis,Matrix([[_y*h1-1],[e1],[e2],[e3]]),R2);

$$ \begin{bmatrix} 1 & 0 \\ 0 & \frac{x_2}{2} + \frac{x_3}{5} \end{bmatrix} $$

> Factorization(C_1tbis,C_h1t,Matrix([[_y*h1-1],[e1],[e2],[e3]]),R2);

$$ \begin{bmatrix} 1 & 0 \\ 0 & 5\_yx_4 \end{bmatrix} $$

Finally, let us compute $ker_{S_{h_2}}(.B^T)$. Using the Syzygies function, we obtain that the rows of the matrix

> C_2t := Syzygies(B_t,Matrix([[_y*h2-1],[e1],[e2],[e3]]),R2);

$$ C_{2t} := \begin{bmatrix} 3 & 0 & -1 \\ 0 & -12x_4 & 12x_3 + 4x_4 \\ 0 & -6x_4 & 6x_3 + 2x_4 \\ 0 & 6\_yx_3x_4 & -2 \\ 0 & -30\_yx_3x_4 & 10 \\ 0 & 6x_4 & -6x_3 - 2x_4 \\ 0 & -6x_4 & 6x_3 + 2x_4 \end{bmatrix} $$

generate $ker_{S_{h_2}}(.B^T)$. Hence, the seven rows of the matrix $C_{2t}$ generate $ker_{S_{h_2}}(.B^T)$. Let us search for a set of generators containing fewer elements by using ReducedSyzygies function:

> C_2tbis := ReducedSyzygies(B_t,Matrix([[_y*h2-1],[e1],[e2],[e3]]),R2);

$$ C_{2tbis} := \begin{bmatrix} 3 & 0 & -1 \\ 0 & -6x_4 & 6x_3 + 2x_4 \end{bmatrix} $$

Thus, we have $ker_{S_{h_2}}(.B^T) = im_{S_{h_2}}(.C_{2tbis})$, which shows that $ker_{S_{h_2}}(.B^T)$ can be generated by the two rows of the matrix $\tilde{C}_{2tbis}$. Transposing this last matrix

> Transpose(C_2tbis);

$$ \begin{bmatrix} 3 & 0 \\ 0 & -6x_4 \\ -1 & 6x_3 + 2x_4 \end{bmatrix} $$

we obtain $ker_{S_{h_2}}(B.) = im_{S_{h_2}}(C_{2tbis}^T)$. Using the Factorization function, we can check again that $C_{2tbis}$ (resp., $C_{2t}$) is a left factor of $C_{2t}$ (resp., $C_{2tbis}$):

> Factorization(C_2t,C_2tbis,Matrix([[_y*h2-1],[e1],[e2],[e3]]),R2);

$$ \begin{bmatrix} 1 & 0 \\ 0 & 2 \\ 0 & 1 \\ 0 & -\_yx_1 + \frac{3}{2}\_yx_2 \\ 0 & 5\_yx_1 - \frac{15}{2}\_yx_2 \\ 0 & -1 \\ 0 & 1 \end{bmatrix} $$
> Factorization(C_2tbis,C_2t,Matrix([[__y*h2-1], [e1], [e2], [e3]]),R2);

[ 1 0 0 0 0 0 0 0 0 0 0 0 1 ]

Therefore, we have $\mathrm{im}_{S_{h_2}}(.C_{2tbis}) = \mathrm{im}_{S_{h_2}}(.C_{2t})$. Finally, in Example 12, the matrix $C_{h_2}^T$, defined by

> C_h2t := Matrix([[Row(C_2t,1)], [Row(C_2t,3)/2]]);

$$C_{h2t} := \begin{bmatrix} 3 & 0 & -1 \\ 0 & -3x_4 & 3x_3 + x_4 \end{bmatrix}$$

is given. Up to a factor of 2 for the second row, we obtain again $C_{2tbis}$. Such an esthetical cleaning will be added to the **ReducedSyzygies** function in the future.

## 6.2 Main commands for solving the rank factorization problem

### 6.2.1 Description of the main functions of the RankFactorization package

Let us now illustrate the main functions of the `RankFactorization` package (see Table 1).

The `RankFactorization`(M, L, k) function computes the outputs of Algorithm 3, where $M \in \mathbb{K}^{m \times n}$ and the list L of matrices $D_1, \dots, D_r \in \mathbb{K}^{m \times m}$ define the rank factorization problem eq. (4), and the index $k \in [0, \dots, r-1]$ fixes the “leaf of the solution space” we are considering in the sense that the solutions that are computed are defined over the ring $S_k = \mathbb{R}/\mathcal{J}_k$, where $\mathcal{J}_k = \mathrm{Fitt}_k(Q)$.

The first output is a list of elements of $\mathbb{R}$ which generates the ideal $\mathcal{J}_k$, the second (resp., third) one is the matrix K (resp., Y), the fourth is a list $\{g_{k,i}\}_{i \in I_k}$, where $g_{k,i} \in \mathbb{R}$ is a preimage of $h_{k,i}$, where $\mathcal{I} = \langle h_{k,1}, \dots, h_{k,\beta_k} \rangle_{S_k}$ and $I_k \subseteq [1, \dots, \beta_k]$ is the set of the indices of the non-nilpotents elements $h_{k,i}$, the fifth (resp., the sixth) is a list of right inverses $\{E_{k,h_i}\}_{i \in I_k}$ (resp., of kernels $\{C_{k,h_i}\}_{i \in I_k}$) of the matrix B over the localization of the ring $S_k$ at the multiplicatively closed set $\{h_{k,i}^k\}_{k \in \mathbb{Z}}$ for $i \in I_k$. The seventh is the polynomial ring $\mathbb{R}[y]$ (which allows one to work with the ring $\mathbb{R}_{g_{k,i}}$, and thus, with the ring $S_{h_{k,i}}$; see the comment after Lemma 9), and the last one is the matrix $A = (D_1 x \dots D_r x) \in \mathbb{R}^{m \times r}$.

If the option “reduced” is used as the last argument of the `RankFactorization` function, i.e., if `RankFactorization`(M, L, k, “reduced”) is used, then a reduction of the parameters $q_k$ and $t_{k,i}$ — respectively defining the matrices $K_k \in S_k^{r \times q_k}$ and $C_{h_{k,i}} \in \mathbb{K}^{q \times t_{k,i}}$ (see the proof of Theorem 6 and the general expression eq. (59) of the solutions of the rank factorization problem) — is attempted by reducing trivial syzygies (usually at the cost of computational cost).

The `Solutions` function builds the explicit solutions eq. (59) of the rank factorization eq. (4) from the data obtained from the `RankFactorization` function (see Theorem 6). Its entries are the same as the `RankFactorization` function, namely, the matrix $M \in \mathbb{K}^{m \times n}$, a list of matrices $D_1, \dots, D_r \in \mathbb{K}^{m \times m}$, and $k \in [0, \dots, r-1]$. The first output is a set of elements of $\mathbb{R}$ defining the ideal $\mathcal{J}_k$, the second one is $\{g_{k,i}\}_{i \in I_k}$, the third one is $A = (D_1 x \dots D_r x)$, the fourth is a list formed by the $v_{k,h_{k,i}}$'s for $i \in I_k$ defined by eq. (59), and the last one is the polynomial ring $\mathbb{R}[y]$.

As for `RankFactorization`, the option “reduced” can be used to reduce the sizes of the outputs of the v-components of the solutions (u, v) of the rank factorization problem eq. (4).

Finally, the `Isolution` function checks whether or not the outputs of the `Solutions` function define solutions of the corresponding rank factorization problem eq. (4) by substituting the expressions returned by `Solutions` into eq. (4) and checking whether or not the normal forms of the obtained expressions exactly reduce to 0 in the corresponding ring $S_{k,h_i}$.

### 6.2.2 Computation of the solutions of the rank factorization for Example 1 & Example 13

Let us first enter the different matrices considered in Example 1 for the rank factorization problem eq. (4):

> M := Matrix([[1,0$2,1],[0$4],[0$4],[1,0$2,1]]);

$$M := \begin{bmatrix} 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \end{bmatrix}$$
> D1 := Matrix([[1,0$3],[0$4],[0$4],[0$3,-1]]);

$$D1 := \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & -1 \end{bmatrix}$$

> D2 := Matrix([[0$4],[0,1,0$2],[0$2,-1,0],[0$4]]);

$$D2 := \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}$$

> D3 := Matrix([[0$3,1],[0$4],[0$4],[1,0$3]]);

$$D3 := \begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ -1 & 0 & 0 & 0 \end{bmatrix}$$

> D4 := Matrix([[0$4],[0$2,1,0],[0,-1,0$2],[0$4]]);

$$D4 := \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & -1 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}$$

We have $m = n = 4$ and $r = 4$. Moreover, we can easily check that $rank_Q(M) = 1$ or the standard Rank function of the LinearAlgebra package can be used.

RankFactorization(M, [D1, D2, D3, D4], 0) & Solutions(M, [D1, D2, D3, D4], 0) Let us now apply the RankFactorization function for the above matrices and $k = 0$. Since the outputs are too long to be shown in a single line, we display the data in separate lines.

> RFO := RankFactorization(M, [D1,D2,D3,D4], 0):

> nops(RFO);

8

The first output is a set of generators for the ideal $J_0 = \text{Fitt}_0(Q)$ of $R$:

> RFO[1];

[0]

Thus, we have $J_0 = \langle 0 \rangle$, and thus, $S_0 = R$. The second output is the matrix $K_0$ defined by:

> RFO[2];

$$\begin{bmatrix} 1 \\ 0 \\ -1 \\ 0 \end{bmatrix}$$

The third one is the matrix $Y$ defined by:

> RFO[3];

$$\begin{bmatrix} 1 & 0 & 0 & 1 \end{bmatrix}$$

The fourth output is a list of the non-nilpotent elements of a set of generators $\{g_{0,i}\}_{i \in I_0}$ of $\mathcal{I}_0 = \text{Fitt}_0(\mathcal{B}_0)$:

> RFO[4];

$$[x_1 - x_4]$$
We thus get $I_0 = \{1\}$ and $g_{0,1} = x_1 - x_4$. In particular, a unique solution of the rank factorization problem eq. (4) can be found over the localization of $S_0 = \mathcal{R}$ with respect to the multiplicative set $\{g_{0,1}^k\}_{k \in \mathbb{Z}}$, i.e., $S_{0,g_{0,1}} = S_0[y]/\langle y g_{0,1} - 1 \rangle = S_0[g_{0,1}^{-1}]$.

In the RANKFACTORIZATION package, we use the notation _y instead of y to protect this variable and to avoid any possible confusion with a variable y which could have been used in the Maple worksheet.

The next output is a right inverse of the matrix $B_0$ with entries in the ring $S_{0,g_{0,1}}$:

> RFO[5];

table ([1 = [ _y ]])

Thus, _y is the inverse of $B_0 = (x_1 - x_4)$.

The sixth output is a matrix defining a set of generators of $ker_{S_{0,g_{0,1}}}(B_0)$.

> RFO[6];

table ([1 = []])

We thus have $ker_{S_{0,g_{0,1}}}(B_0) = 0$.

The next output is the polynomial ring $\mathcal{R}[y]$. It is internally displayed in OREMODULES as follows:

> RFO[7];

$[\text{Ore\_algebra}, [\text{"diff"}, \text{"diff"}, \text{"diff"}, \text{"diff"}, \text{"diff"}], [t_1, t_2, t_3, t_4, _t], [x_1, x_2, x_3, x_4, _y], [t_1, t_2, t_3, t_4, _t], [], []], [t_1, t_2, t_3, t_4, _t], [], [], [diff = [x_1, t_1], diff = [x_2, t_2], diff = [x_3, t_3], diff = [x_4, t_4], diff = [_, y, _t]],
\begin{bmatrix}
-\alpha & -\alpha * x_1 - \left(\frac{\partial}{\partial t_1} - \alpha\right), & -\alpha & -\alpha * x_2 - \left(\frac{\partial}{\partial t_2} - \alpha\right), & -\alpha & -\alpha * x_3 - \left(\frac{\partial}{\partial t_3} - \alpha\right), & -\alpha & -\alpha * x_4 - \left(\frac{\partial}{\partial t_4} - \alpha\right), & -\alpha & -\alpha * y - \left(\frac{\partial}{\partial t} - \alpha\right)
\end{bmatrix}
\end{array}
\]

Finally, the last output is the matrix $A = (D_1 x \dots D_4 x)$, where $x = (x_1 \dots x_4)^T$, then defined by:

> RFO[8];

$$
\begin{bmatrix}
x_1 & 0 & x_4 & 0 \\
0 & x_2 & 0 & x_3 \\
0 & -x_3 & 0 & -x_2 \\
-x_4 & 0 & -x_1 & 0
\end{bmatrix}
$$

From the above data of the RankFactorization, we can then form the explicit solutions eq. (59). The Solutions function first computes RankFactorization and then builds the corresponding solutions. Again, the outputs of Solutions are too long to be displayed in a single line. Hence, we show the data in separate lines.

> Sol0 := Solutions(M, [D1, D2, D3, D4], 0);

> nops(Sol0);

5

The first output is a list of generators of the ideal $\mathcal{J}_0$.

> Sol0[1];

[0]

As above, we have $\mathcal{J}_0 = \langle 0 \rangle$, and thus, $\mathcal{S} = \mathcal{R}$ and $\mathcal{V}(\mathcal{J}_0) = \mathbb{K}^{4 \times 1}$.

The second output

> Sol0[2];

$[x_1 - x_4]$

shows that there is one solution defined over $\mathcal{R}_{g_{0,1}} = \mathcal{R}[y]/\langle y g_{0,1} - 1 \rangle = \mathcal{R}[g_{0,1}^{-1}]$, where $g_{0,1} = x_1 - x_4$, i.e., in $\mathcal{V}(\mathcal{J}_0) \setminus \mathcal{V}(\langle g_0 \rangle) = \mathbb{K}^{4 \times 1} \setminus \{(u_1 \ u_2 \ u_3 \ u_4)^T \mid u_1, u_2, u_3 \in \mathbb{K}\} = \{(u_1 \ \dots \ u_4)^T \in \mathbb{K}^{4 \times 1} \mid u_1 \neq u_4\}$.
The next output is the matrix $A = (D_1 x \dots D_4 x)$, where $x = (x_1 \dots x_4)^T$:

> Sol0[3];

$$ \begin{bmatrix} x_1 & 0 & x_4 & 0 \\ 0 & x_2 & 0 & x_3 \\ 0 & -x_3 & 0 & -x_2 \\ -x_4 & 0 & -x_1 & 0 \end{bmatrix} $$

The fourth output gives the v-component of the solution $(u, v)$ of the rank factorization problem:

> Sol0[4];

$$ \text{table}\left(\left[1 = \begin{bmatrix} -y & 0 & 0 & -y \\ 0 & 0 & 0 & 0 \\ -y & 0 & 0 & -y \\ 0 & 0 & 0 & 0 \end{bmatrix}\right]\right) $$

Finally, the last output is the ring $\mathcal{R}[y]$ which is used to check again that the above expressions for $u$ and $v$ define solutions to the rank factorization problem using the `IsSolution` function.

> Sol0[5];

```
table([1 = [ Ore_algebra, ["diff", "diff", "diff", "diff", "diff"], [t_1, t_2, t_3, t_4, _t], [x_1, x_2, x_3, x_4, _y], [t_1, t_2, t_3, t_4, _t], [y_1,1, y_1,2, y_1,3, y_1,4, y_2,1, y_2,2, y_2,3, y_2,4, y_3,1, y_3,2, y_3,3, y_3,4], 0, [], [], [t_1, t_2, t_3, t_4, _t], [], [], [diff = [x_1, t_1],
    diff = [x_2, t_2], diff = [x_3, t_3], diff = [x_4, t_4], diff = [_, y, _t]]
```

$$ \begin{bmatrix} -a \rightarrow -a * x_1 - \left(\frac{\partial}{\partial t_1} - a\right), & -a \rightarrow -a * x_2 - \left(\frac{\partial}{\partial t_2} - a\right), & -a \rightarrow -a * x_3 - \left(\frac{\partial}{\partial t_3} - a\right), \\ -a \rightarrow -a * x_4 - \left(\frac{\partial}{\partial t_4} - a\right), & -a \rightarrow -a * y - \left(\frac{\partial}{\partial t} - a\right) & -a \rightarrow -a * _y - \left(\frac{\partial}{\partial _y} - a\right) \end{bmatrix} \] $$

We find again the solution $(u, v)$, where $u \in \{(u_1 \dots u_4)^T \in \mathbb{K}^{4 \times 1} | u_1 \neq u_4\}$ and $v_{h_{0,1}}$ defined by the above matrix, where $\_y = (x_1 - x_4)^{-1}$, obtained in Example 13. Finally, using the `IsSolution` function, we can check again that $(u, v)$ defines a solution of the corresponding rank factorization problem eq. (4).

> IsSolution(Sol0);

```
table([1 = [true]])
```

If the option "reduced" is added to the `RankFactorization` or the `Solutions` functions, then we obtain the same solution.

As explained in Theorem 6, `Sol0` is the component of the solution space of the corresponding rank factorization problem corresponding the affine algebraic set $\mathcal{V}(\mathcal{J}_0)$, i.e., the 0th leaf of the solution space. We can also get other solutions by considering $\mathcal{J}_k$ for $k = 1, 2, r-1 = 3$, and their corresponding affine algebraic sets $\mathcal{V}(\mathcal{J}_k)$, i.e., the other $k^{th}$ leaves of the solution space for $k = 1, 2, 3$.

`RankFactorization(M, [D1, D2, D3, D4], 1) & Solutions(M, [D1, D2, D3, D4], 1)` Let us briefly display the different outputs of the `RankFactorization` for $k = 1$.

> RF1 := RankFactorization(M, [D1,D2,D3,D4],1):

The first output is a set of generators for the ideal $\mathcal{J}_1 = \text{Fitt}_1(\mathcal{Q})$ of $\mathcal{R}$:

> RF1[1];

$$ [x_2^2 x_1 - x_1 x_3^2 + x_2^2 x_4 - x_3^2 x_4] $$

Thus, we have $\mathcal{J}_1 = \langle(x_2 - x_3)(x_2 + x_3)(x_1 + x_4)\rangle$ and $\mathcal{S}_1 = \mathcal{R}/\mathcal{J}_1$.

The second output is the matrix $K_1$ defined by:

> RF1[2];
$$ \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & -x_3 x_1 - x_3 x_4 & x_2 x_1 + x_2 x_4 & 0 \\ -1 & 0 & 0 & x_2^2 - x_3^2 \\ 0 & x_2 x_1 + x_2 x_4 & -x_3 x_1 - x_3 x_4 & 0 \end{bmatrix} $$

The third one is the matrix Y defined by:

> RF1 [3];

[ 1 0 0 1 ]

The fourth output is a list of the non-nilpotent elements of a set of generators {$g_{1,i}$}$_{i \in I_1}$ of $\mathcal{I}_1 = \text{Fitt}_0(\mathcal{B}_1)$:

> RF1 [4];

$[x_1 - x_4, x_2^2 x_4 - x_3^2 x_4]$

We thus have $I_1 = \{1, 2\}$, $g_{1,1} = x_1 - x_4$, and $g_{1,2} = x_4(x_2 - x_3)(x_2 + x_3)$. If we denote by $h_{1,i}$ the residue class of $g_{1,i}$ in $S_1$ for $i = 1, 2$, then two solutions exist respectively over the localization $S_{1,h_{1,i}} = S_1[y]/\langle y h_{1,i} - 1 \rangle = S_1[h_{1,i}^{-1}]$ for $i = 1, 2$.

The next output is a right inverse of the matrix $B_1$ over respectively the ring $S_{1,g_{1,i}}$ for $i = 1, 2$:

> RF1 [5];

$$ \text{table} \left( \left[ \begin{array}{c} 1 = \begin{bmatrix} -y \\ 0 \\ 0 \\ 0 \end{bmatrix} \\ 2 = \begin{bmatrix} 0 \\ 0 \\ 0 \\ -y \end{bmatrix} \end{array} \right] \right) $$

The sixth output is a table containing the right kernel of the matrix $B_1$ over respectively the ring $S_{1,h_{1,i}}$, i.e., $\ker_{S_{1,h_{1,i}}}(B_1)$ for $i = 1, 2$.

> RF1 [6];

$$ \text{table} \left( \left[ \begin{array}{ccccccc} 1 & x_2^2 - x_3^2 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & x_1 + x_4 & 2 \_y x_4 + 1 & -2 \_y x_4 - 1 & 0 \end{array} \right], 2 = \left[ \begin{array}{ccccccc} 1 & x_2^2 - x_3^2 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 \_y x_4 & 2 & 0 & 0 & 0 & 0 & 0 \end{array} \right] \right) $$

Similarly, the next output is the polynomial ring $\mathcal{R}[y]$.

> RF1 [7];

$[\text{Ore\_algebra}, [\text{diff}, \text{diff}, \text{diff}, \text{diff}, \text{diff}], [t_1, t_2, t_3, t_4, \_t], [x_1, x_2, x_3, x_4, \_y], [t_1, t_2, t_3, t_4, \_t], [], 0, [], [], [t_1, t_2, t_3, t_4, \_t], [], [], [\text{diff} = [x_1, t_1], \text{diff} = [x_2, t_2], \text{diff} = [x_3, t_3], \text{diff} = [x_4, t_4], \text{diff} = [\_y, \_t]],$

$$ \begin{aligned} [-a \to -a * x_1 - \left(\frac{\partial}{\partial t_1} - a\right), & -a \to -a * x_2 - \left(\frac{\partial}{\partial t_2} - a\right), -a \to -a * x_3 - \left(\frac{\partial}{\partial t_3} - a\right), \\ -a \to -a * x_4 - \left(\frac{\partial}{\partial t_4} - a\right), & -a \to -a * -y - \left(\frac{\partial}{\partial \_t} - a\right)] \end{aligned} $$

Again, the last output is the matrix $A = (D_1 x \dots D_4 x)$, where $x = (x_1 \dots x_4)^T$, defined by:

> RF1 [8];

$$ \begin{bmatrix} x_1 & 0 & x_4 & 0 \\ 0 & x_2 & 0 & x_3 \\ 0 & -x_3 & 0 & -x_2 \\ -x_4 & 0 & -x_1 & 0 \end{bmatrix} $$

If the option “reduced” is added to the RankFactorization, then the same matrix $K_1$, returned in RF1[2], is obtained. However, the matrices $C_{h_{1,i}}$ defining $\ker_{S_{1,h_{1,i}}}(B_1)$ are then shorter:

> RF1bis := RankFactorization(M, [D1,D2,D3,D4], 1, "reduced"):

> RF1bis[6];
$$
\text{table}\left(\left[1 = \begin{bmatrix} x_2^2 - x_3^2 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 2 & 0 & 0 \end{bmatrix}, 2 = \begin{bmatrix} x_2^2 - x_3^2 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 2 & 0 & 0 \end{bmatrix}\right]\right)
$$

As we shall later, the corresponding expressions for the solutions will thus be shorter with the “reduced”
option, i.e., fewer free parameters in the matrices $Y'$ will be needed (even if both expressions define the
same set of solutions).

> Sol1 := Solutions(M, [D1,D2,D3,D4], 1):

We first obtain that the ideal $\mathcal{J}_1$ is generated by:

> Sol1[1];

$$
[x_2^2 x_1 - x_1 x_2^2 + x_2^2 x_4 - x_3^2 x_4]
$$

i.e., $\mathcal{J}_1 = \langle (x_2 - x_3)(x_2 + x_3)(x_1 + x_4) \rangle$. The second output

> Sol1[2];

$$
[x_1 - x_4, x_2^2 x_4 - x_3^2 x_4]
$$

shows that two solutions can be found respectively over the localization $S_{1,h_{1,1}}$ (resp., $S_{1,h_{1,2}}$) of the ring $S_1 = \mathcal{R}/\mathcal{J}_1$ with respect respectively to the multiplicatively closed set $\{h_{1,1}^k\}_{k \in \mathbb{Z}}$ (resp., $\{h_{1,2}^k\}_{k \in \mathbb{Z}}$), where $h_{1,1}$ (resp., $h_{1,2}$) denotes the residue class of $g_{1,1} = x_1 - x_4$ (resp., $g_{1,2} = x_4(x_2 - x_3)(x_2 + x_3)$) in the ring $S_{1,h_{1,1}}$ (resp., $S_{1,h_{1,2}}$). Thus, the $u$-component of the two solutions $(u, v)$ respectively belongs to $\mathcal{V}(\mathcal{J}_1) \setminus \mathcal{V}(\langle g_{1,1} \rangle)$ and $\mathcal{V}(\mathcal{J}_1) \setminus \mathcal{V}(\langle g_{1,2} \rangle)$.

As above, the third output is the matrix $A = (D_1 x \dots D_4 x)$, where $x = (x_1 \dots x_4)^T$:

> Sol1[3];

$$
\begin{bmatrix}
x_1 & 0 & x_4 & 0 \\
0 & x_2 & 0 & x_3 \\
0 & -x_3 & 0 & -x_2 \\
-x_4 & 0 & -x_1 & 0
\end{bmatrix}
$$

which is useful for the IsSolution function to test if the expressions returned by the Solutions function
are solutions of the corresponding rank factorization problem. The fourth output is a table with the two
$v$-components of solutions.

> nops(Sol1[4]);

2

For a better display, we successively show the rows of these two solutions. Let us start with the first one:

> Row(Sol1[4][1],1);

$$
[ -y + (x_2^2 - x_3^2) y_{1,1} \quad (x_2^2 - x_3^2) y_{1,2} \quad (x_2^2 - x_3^2) y_{1,3} \quad -y + (x_2^2 - x_3^2) y_{1,4} ]
$$

> Row(Sol1[4][1],2);

$$
\begin{bmatrix}
(-x_3 x_1 - x_3 x_4) y_{2,1} + (x_2 x_1 + x_2 x_4) y_{3,1} & (-x_3 x_1 - x_3 x_4) y_{2,2} + (x_2 x_1 + x_2 x_4) y_{3,2} \\
(-x_3 x_1 - x_3 x_4) y_{2,3} + (x_2 x_1 + x_2 x_4) y_{3,3} & (-x_3 x_1 - x_3 x_4) y_{2,4} + (x_2 x_1 + x_2 x_4) y_{3,4}
\end{bmatrix}
$$

> Row(Sol1[4][1],3);

$$
\begin{aligned}
& [ -y - (x_2^2 - x_3^2) y_{1,1} + (x_2^2 - x_3^2) (2 y_{1,1} + (x_1 + x_4) y_{4,1} + (2 \underline{y} x_4 + 1) y_{5,1} + (-2 \underline{y} x_4 - 1) y_{6,1}) \\
& \qquad - (x_2^2 - x_3^2) y_{1,2} + (x_2^2 - x_3^2) (2 y_{1,2} + (x_1 + x_4) y_{4,2} + (2 \underline{y} x_4 + 1) y_{5,2} + (-2 \underline{y} x_4 - 1) y_{6,2}) \\
& \qquad - (x_2^2 - x_3^2) y_{1,3} + (x_2^2 - x_3^2) (2 y_{1,3} + (x_1 + x_4) y_{4,3} + (2 \underline{y} x_4 + 1) y_{5,3} + (-2 \underline{y} x_4 - 1) y_{6,3}) \\
& \qquad - y - (x_2^2 - x_3^2) y_{1,4} + (x_2^2 - x_3^2) (2 y_{1,4} + (x_1 + x_4) y_{4,4} + (2 \underline{y} x_4 + 1) y_{5,4} + (-2 \underline{y} x_4 - 1) y_{6,4}) ]
\end{aligned}
$$

> Row(Sol1[4][1],4);

$$
\begin{bmatrix}
(x_2 x_1 + x_2 x_4) y_{2,1} + (-x_3 x_1 - x_3 x_4) y_{3,1} & (x_2 x_1 + x_2 x_4) y_{2,2} + (-x_3 x_1 - x_3 x_4) y_{3,2} \\
(x_2 x_1 + x_2 x_4) y_{2,3} + (-x_3 x_1 - x_3 x_4) y_{3,3} & (x_2 x_1 + x_2 x_4) y_{2,4} + (-x_3 x_1 - x_3 x_4) y_{3,4}
\end{bmatrix}
$$
$$
> \text{Row}(\text{Sol1bis}[4][1],2);
[ (-x_3 x_1 - x_4 x_3) y_{2,1} + (x_2 x_1 + x_4 x_2) y_{3,1} & (-x_3 x_1 - x_4 x_3) y_{2,2} + (x_2 x_1 + x_4 x_2) y_{3,2} \\
(-x_3 x_1 - x_4 x_3) y_{2,3} + (x_2 x_1 + x_4 x_2) y_{3,3} & (-x_3 x_1 - x_4 x_3) y_{2,4} + (x_2 x_1 + x_4 x_2) y_{3,4} ]
$$

$$
> \text{Row}(\text{Sol1bis}[4][1],3);
[ -y + (x_2^2 - x_3^2) y_{1,1} & (x_2^2 - x_3^2) y_{1,2} + (x_2^2 - x_3^2) y_{1,3} - y + (x_2^2 - x_3^2) y_{1,4} ]
$$

$$
> \text{Row}(\text{Sol1bis}[4][1],4);
[ (x_2 x_1 + x_4 x_2) y_{2,1} + (-x_3 x_1 - x_4 x_3) y_{3,1} & (x_2 x_1 + x_4 x_2) y_{2,2} + (-x_3 x_1 - x_4 x_3) y_{3,2} \\
(x_2 x_1 + x_4 x_2) y_{2,3} + (-x_3 x_1 - x_4 x_3) y_{3,3} & (x_2 x_1 + x_4 x_2) y_{2,4} + (-x_3 x_1 - x_4 x_3) y_{3,4} ]
$$

Finally, let us successively display the rows of the second solution:

$$
> \text{Row}(\text{Sol1bis}[4][2],1);
[ (x_2^2 - x_3^2) y_{1,1} & (x_2^2 - x_3^2) y_{1,2} + (x_2^2 - x_3^2) y_{1,3} - (x_2^2 - x_3^2) y_{1,4} ]
$$

$$
> \text{Row}(\text{Sol1bis}[4][2],2);
[ (-x_1 x_3 - x_3 x_4) y_{2,1} + (x_1 x_2 + x_2 x_4) y_{3,1} & (-x_1 x_3 - x_3 x_4) y_{2,2} + (x_1 x_2 + x_2 x_4) y_{3,2} \\
(-x_1 x_3 - x_3 x_4) y_{2,3} + (x_1 x_2 + x_2 x_4) y_{3,3} & (-x_1 x_3 - x_3 x_4) y_{2,4} + (x_1 x_2 + x_2 x_4) y_{3,4} ]
$$

$$
> \text{Row}(\text{Sol1bis}[4][2],3);
[ - (x_2^2 - x_3^2) y_{1,1} + (x_2^2 - x_3^2) (-y + 2 y_{1,1}) & (x_2^2 - x_3^2) y_{1,2} \\
(x_2^2 - x_3^2) y_{1,3} & - (x_2^2 - x_3^2) y_{1,4} + (x_2^2 - x_3^2) (-y + 2 y_{1,4}) ]
$$

$$
> \text{Row}(\text{Sol1bis}[4][2],4);
[ (x_1 x_2 + x_2 x_4) y_{2,1} + (-x_1 x_3 - x_3 x_4) y_{3,1} & (x_1 x_2 + x_2 x_4) y_{2,2} + (-x_1 x_3 - x_3 x_4) y_{3,2} \\
(x_1 x_2 + x_2 x_4) y_{2,3} + (-x_1 x_3 - x_3 x_4) y_{3,3} & (x_1 x_2 + x_2 x_4) y_{2,4} + (-x_1 x_3 - x_3 x_4) y_{3,4} ]
$$

Hence, using the option "reduced", shorter expressions for the v-components of the solutions for k = 1 are obtained.

RankFactorization(M, [D1, D2, D3, D4], 2) & Solutions(M, [D1, D2, D3, D4], 2) Let us now apply RankFactorization with k = 2.

> RF2 := RankFactorization(M, [D1,D2,D3,D4],2):

We first obtain that the ideal $\mathcal{J}_2$ is generated by:

> RF2[1];
[x_3 x_1 + x_3 x_4, x_2^2 - x_3^2, x_2 x_1 + x_2 x_4]

Thus, we have $\mathcal{J}_2 = \langle x_3(x_1+x_4), (x_2-x_3)(x_2+x_3), x_2(x_1+x_4) \rangle$ and $S_2 = \mathcal{R}/\mathcal{J}_2$.
The second output is the matrix $K_2$ defined by:

> RF2[2];
$$
\begin{bmatrix}
1 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & -x_3 & x_2 & x_1 + x_4 & 0 & 0 & 0 \\
-1 & 0 & 0 & 0 & x_3 & x_2 & 0 \\
0 & x_2 & -x_3 & 0 & 0 & 0 & x_1 + x_4
\end{bmatrix}
$$

Again, the third one is the matrix $Y$ defined by:

> RF2[3];
[ 1 0 0 1 ]

The fourth output is a list of the non-nilpotent elements of a set of generators {$g_{2,i}$}$_{i \in I_2}$ of $\mathcal{I}_2 = \text{Fitt}_0(\mathcal{B}_2)$:

> RF2[4];
$$[x_1 - x_4, x_3 x_4, x_2 x_4]$$

We thus have $I_2 = \{1, 2, 3\}$, $g_{2,1} = x_1 - x_4$, $g_{2,2} = x_3 x_4$, and $g_{2,3} = x_2 x_4$. If we denote by $h_{2,i}$ the residue class of $g_{2,i}$ in $S_2$ for $i = 1, 2, 3$, then three solutions exist respectively over the localization $S_{2,h_{2,i}} = S_2[y]/\langle y h_{2,i} - 1 \rangle = S_2[h_{2,i}^{-1}]$ for $i = 1, 2, 3$.

The next output is a right inverse of the matrix $B_2$ over respectively the ring $S_{2,h_{2,i}}$ for $i = 1, 2, 3$:

> RF2[5];

$$\text{table}\left(\left[\begin{array}{c|c} 1 = \begin{bmatrix} -y \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} & 2 = \begin{bmatrix} 0 \\ 0 \\ 0 \\ -y \\ 0 \\ 0 \end{bmatrix} & 3 = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ -y \end{bmatrix} \end{array}\right]\right)$$

The sixth output is a table containing the right kernel of the matrix $B_2$ over respectively the ring $S_{2,h_{2,i}}$, i.e., $\ker_{S_{2,h_{2,i}}}(B_2)$, for $i = 1, 2, 3$.

> RF2[6];

table([

$$1 = \begin{bmatrix} x_3 & x_2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 & 0 & -x_3 & x_2 & x_1 + x_4 & 2_-y x_4 + 1 & -2_-y x_4 - 1 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 & x_2 & -x_3 & 0 & 0 & 0 & x_1 + x_4 & 2_-y x_4 + 1 & -2_-y x_4 - 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix},$$

$$2 = \begin{bmatrix} x_3 & x_2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 2 & 0 & 2_-y x_4 & 0 & 0 & 0 & -x_3 & x_2 & 0 \\ 0 & 2 & 0 & 0 & 0 & 0 & x_2 & -x_3 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix},$$

$$3 = \begin{bmatrix} x_3 & x_2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 & 0 & 0 & -x_3 & x_2 & -y x_3 x_4 & 0 \\ 0 & 2 & 2_-y x_4 & 0 & 0 & 0 & x_2 & -x_3 & -1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}$$

The next output is the polynomial ring $\mathcal{R}[y]$.

> RF2[7];

$[\text{Ore\_algebra}, [\text{"diff"}, \text{"diff"}, \text{"diff"}, \text{"diff"}, \text{"diff"}], [t_1, t_2, t_3, t_4, \_t], [x_1, x_2, x_3, x_4, \_y], [t_1, t_2, t_3, t_4, \_t], [], 0, [], [], [t_1, t_2, t_3, t_4, \_t], [], [], [diff = [x_1, t_1], diff = [x_2, t_2], diff = [x_3, t_3], diff = [x_4, t_4], diff = [\_y, \_t]],

$$\begin{bmatrix} -a \rightarrow -a * x_1 - \left(\frac{\partial}{\partial t_1} - a\right), & -a \rightarrow -a * x_2 - \left(\frac{\partial}{\partial t_2} - a\right), & -a \rightarrow -a * x_3 - \left(\frac{\partial}{\partial t_3} - a\right), \\ -a \rightarrow -a * x_4 - \left(\frac{\partial}{\partial t_4} - a\right), & -a \rightarrow -a * \_y - \left(\frac{\partial}{\partial \_t} - a\right) \end{bmatrix}$$

Again, the last output is the matrix $A = (D_1 x \dots D_4 x)$, where $x = (x_1 \dots x_4)^T$, defined by:

> RF2[8];
$$ \begin{bmatrix} x_1 & 0 & x_4 & 0 \\ 0 & x_2 & 0 & x_3 \\ 0 & -x_3 & 0 & -x_2 \\ -x_4 & 0 & -x_1 & 0 \end{bmatrix} $$

If the option “reduced” is added to the RankFactorization, then the same matrix $K_2$, returned in RF2[2], is obtained. However, the matrices $C_{h_{2,i}}$ defining $ker_{S_{2,h_{2,i}}}(B_2)$ are then shorter:

> RF2bis := RankFactorization(M, [D1,D2,D3,D4], 2, "reduced"):

> RF2bis[6];

$$ \text{table} \left( \left[ \begin{array}{c} 1 = \begin{bmatrix} x_3 & x_2 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 2 & 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} \\ 2 = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 2\_y x_4 & 0 & 0 & 0 & x_2 & 0 \\ 0 & 0 & 0 & 0 & -x_3 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} \\ 3 = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & -y x_3 x_4 & 0 \\ 2\_y x_4 & 0 & 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} \end{array} \right] \right) $$

Hence, as we shall, the corresponding expressions for the solutions are shorter with the “reduced” option, i.e., fewer free parameters in the matrices $Y'$ are needed (even if the expressions define the same sets of solutions). Let us now directly compute the solutions of the rank factorization for $k = 2$.

> Sol2 := Solutions(M, [D1,D2,D3,D4], 2):

We first obtain that the ideal $\mathcal{J}_2$ is generated by:

> Sol2[1];

$$ [x_3 x_1 + x_3 x_4, x_2^2 - x_3^2, x_2 x_1 + x_2 x_4] $$

i.e., $\mathcal{J}_2 = \langle x_3 (x_1 + x_4), (x_2 - x_3) (x_2 + x_3), x_2 (x_1 + x_4) \rangle$ and $S_2 = \mathcal{R}/\mathcal{J}_2$. The second output

> Sol2[2];

$$ [x_1 - x_4, x_3 x_4, x_2 x_4] $$

shows that three solutions can be found respectively over the localization $S_{2,h_{2,1}}$ (resp., $S_{2,h_{2,2}}$, $S_{2,h_{2,3}}$) of the ring $S_2$ with respect respectively to the multiplicatively closed set $\{h_{2,1}^k\}_{k \in \mathbb{Z}}$ (resp., $\{h_{2,2}^k\}_{k \in \mathbb{Z}}$, $\{h_{2,3}^k\}_{k \in \mathbb{Z}}$), where $h_{2,1}$ (resp., $h_{2,2}$, $h_{2,3}$) denotes the residue class of $g_{2,1} = x_1 - x_4$ (resp., $g_{2,2} = x_3 x_4$, $g_{2,3} = x_2 x_4$) in the ring $S_{2,h_{2,1}}$ (resp., $S_{2,h_{2,2}}$, $S_{2,h_{2,3}}$). Thus, the $u$-component of the two solutions $(u, v)$ respectively belongs to $\mathcal{V}(\mathcal{J}_2) \setminus \mathcal{V}(\langle g_{2,1} \rangle) \mathcal{V}(\mathcal{J}_2) \setminus \mathcal{V}(\langle g_{2,2} \rangle)$, and $\mathcal{V}(\mathcal{J}_2) \setminus \mathcal{V}(\langle g_{2,3} \rangle)$.

The third output is the matrix $A = (D_1 x \dots D_4 x)$, where $x = (x_1 \dots x_4)^T$:

> Sol2[3];

$$ \begin{bmatrix} x_1 & 0 & x_4 & 0 \\ 0 & x_2 & 0 & x_3 \\ 0 & -x_3 & 0 & -x_2 \\ -x_4 & 0 & -x_1 & 0 \end{bmatrix} $$

> nops(op(Sol2[4]));

3

Thus, there are three families of solutions. For a better display, we successively show the rows of the three families of solutions.

Let us start with the first one

> Row(Sol2[4][1],1);

$$ [ x_2 y_{2,1} + x_3 y_{1,1} + _y x_2 y_{2,2} + x_3 y_{1,2} \quad x_2 y_{2,3} + x_3 y_{1,3} \quad x_2 y_{2,4} + x_3 y_{1,4} + _y ] $$

> Row(Sol2[4][1],2);
$$ \begin{bmatrix} -x_3 y_{3,1} + x_2 y_{4,1} + (x_1 + x_4) y_{5,1} & -x_3 y_{3,2} + x_2 y_{4,2} + (x_1 + x_4) y_{5,2} \\ -x_3 y_{3,3} + x_2 y_{4,3} + (x_1 + x_4) y_{5,3} & -x_3 y_{3,4} + x_2 y_{4,4} + (x_1 + x_4) y_{5,4} \end{bmatrix} $$

> Row(Sol2[4][1],3);

$$ \begin{aligned} & \begin{bmatrix} -x_2 y_{2,1} - x_3 y_{1,1} - y + x_3 (2 y_{1,1} - x_3 y_{6,1} + x_2 y_{7,1} + (x_1 + x_4) y_{8,1} + (2 \_y x_4 + 1) y_{9,1} + (-2 \_y x_4 - 1) y_{10,1}) \\ +x_2 (2 y_{2,1} + x_2 y_{6,1} - x_3 y_{7,1} + (x_1 + x_4) y_{11,1} + (2 \_y x_4 + 1) y_{12,1} + (-2 \_y x_4 - 1) y_{13,1}) \\ -x_2 y_{2,2} - x_3 y_{1,2} + x_3 (2 y_{1,2} - x_3 y_{6,2} + x_2 y_{7,2} + (x_1 + x_4) y_{8,2} + (2 \_y x_4 + 1) y_{9,2} + (-2 \_y x_4 - 1) y_{10,2}) \\ +x_2 (2 y_{2,2} + x_2 y_{6,2} - x_3 y_{7,2} + (x_1 + x_4) y_{11,2} + (2 \_y x_4 + 1) y_{12,2} + (-2 \_y x_4 - 1) y_{13,2}) \\ -x_2 y_{2,3} - x_3 y_{1,3} + x_3 (2 y_{1,3} - x_3 y_{6,3} + x_2 y_{7,3} + (x_1 + x_4) y_{8,3} + (2 \_y x_4 + 1) y_{9,3} + (-2 \_y x_4 - 1) y_{10,3}) \\ +x_2 (2 y_{2,3} + x_2 y_{6,3} - x_3 y_{7,3} + (x_1 + x_4) y_{11,3} + (2 \_y x_4 + 1) y_{12,3} + (-2 \_y x_4 - 1) y_{13,3}) \end{bmatrix} \\ & -x_2 y_{2,4} - x_3 y_{1,4} - y + x_3 (2 y_{1,4} - x_3 y_{6,4} + x_2 y_{7,4} + (x_1 + x_4) y_{8,4} + (2 \_y x_4 + 1) y_{9,4} + (-2 \_y x_4 - 1) y_{10,4}) \\ & +x_2 (2 y_{2,4} + x_2 y_{6,4} - x_3 y_{7,4} + (x_1 + x_4) y_{11,4} + (2 \_y x_4 + 1) y_{12,4} + (-2 \_y x_4 - 1) y_{13,4}) \end{aligned} $$

> Row(Sol2[4][1],4);

$$ \begin{bmatrix} x_2 y_{3,1} - x_3 y_{4,1} + (x_1 + x_4) y_{14,1} & x_2 y_{3,2} - x_3 y_{4,2} + (x_1 + x_4) y_{14,2} \\ x_2 y_{3,3} - x_3 y_{4,3} + (x_1 + x_4) y_{14,3} & x_2 y_{3,4} - x_3 y_{4,4} + (x_1 + x_4) y_{14,4} \end{bmatrix} $$

where the y's are arbitrary elements of $K$.

Let us now show the v-component of the second family of solutions

> Row(Sol2[4][2],1);

$$ \begin{bmatrix} x_2 y_{2,1} + x_3 y_{1,1} + y_{3,1} & x_2 y_{2,2} + x_3 y_{1,2} + y_{3,2} & x_2 y_{2,3} + x_3 y_{1,3} + y_{3,3} & x_2 y_{2,4} + x_3 y_{1,4} + y_{3,4} \end{bmatrix} $$

> Row(Sol2[4][2],2);

$$ \begin{bmatrix} -x_3 y_{4,1} + x_2 y_{5,1} + (x_1 + x_4) y_{6,1} & -x_3 y_{4,2} + x_2 y_{5,2} + (x_1 + x_4) y_{6,2} \\ -x_3 y_{4,3} + x_2 y_{5,3} + (x_1 + x_4) y_{6,3} & -x_3 y_{4,4} + x_2 y_{5,4} + (x_1 + x_4) y_{6,4} \end{bmatrix} $$

> Row(Sol2[4][2],3);

$$ \begin{bmatrix} -x_2 y_{2,1} - x_3 y_{1,1} - y_{3,1} + x_3 (2 \_y x_4 y_{3,1} + x_2 y_{8,1} - x_3 y_{7,1} + \_y + 2 y_{1,1}) + x_2 (x_2 y_{7,1} - x_3 y_{8,1} + 2 y_{2,1}) \\ -x_2 y_{2,2} - x_3 y_{1,2} - y_{3,2} + x_3 (2 \_y x_4 y_{3,2} + x_2 y_{8,2} - x_3 y_{7,2} + 2 y_{1,2}) + x_2 (x_2 y_{7,2} - x_3 y_{8,2} + 2 y_{2,2}) \\ -x_2 y_{2,3} - x_3 y_{1,3} - y_{3,3} + x_3 (2 \_y x_4 y_{3,3} + x_2 y_{8,3} - x_3 y_{7,3} + 2 y_{1,3}) + x_2 (x_2 y_{7,3} - x_3 y_{8,3} + 2 y_{2,3}) \\ -x_2 y_{2,4} - x_3 y_{1,4} - y_{3,4} + x_3 (2 \_y x_4 y_{3,4} + x_2 y_{8,4} - x_3 y_{7,4} + \_y + 2 y_{1,4}) + x_2 (x_2 y_{7,4} - x_3 y_{8,4} + 2 y_{2,4}) \end{bmatrix} $$

> Row(Sol2[4][2],4);

$$ \begin{bmatrix} x_2 y_{4,1} - x_3 y_{5,1} + (x_1 + x_4) y_{9,1} & x_2 y_{4,2} - x_3 y_{5,2} + (x_1 + x_4) y_{9,2} \\ x_2 y_{4,3} - x_3 y_{5,3} + (x_1 + x_4) y_{9,3} & x_2 y_{4,4} - x_3 y_{5,4} + (x_1 + x_4) y_{9,4} \end{bmatrix} $$

where the y's are arbitrary elements of $K$.

Let us now show the v-component of the third family of solutions

> Row(Sol2[4][3],1);

$$ \begin{bmatrix} x_2 y_{2,1} + x_3 y_{1,1} + y_{3,1} & x_2 y_{2,2} + x_3 y_{1,2} + y_{3,2} & x_2 y_{2,3} + x_3 y_{1,3} + y_{3,3} & x_2 y_{2,4} + x_3 y_{1,4} + y_{3,4} \end{bmatrix} $$

> Row(Sol2[4][3],2);

$$ \begin{bmatrix} -x_3 y_{4,1} + x_2 y_{5,1} + (x_1 + x_4) y_{6,1} & -x_3 y_{4,2} + x_2 y_{5,2} + (x_1 + x_4) y_{6,2} \\ -x_3 y_{4,3} + x_2 y_{5,3} + (x_1 + x_4) y_{6,3} & -x_3 y_{4,4} + x_2 y_{5,4} + (x_1 + x_4) y_{6,4} \end{bmatrix} $$

> Row(Sol2[4][3],3);
Finally, we can add the “reduced” option to the Solutions function to get shorter outputs for the v-components of the solutions.

> Sol2bis := Solutions(M, [D1, D2, D3, D4], 2, "reduced"):

> IsSolution(Sol2bis);

table ([1 = [true], 2 = [true]])

Let us successively display the rows of the v-component of the first solution:

> Row(Sol2bis[4][1],1);

[ x₂ y₂,₁ + x₃ y₁,₁ + _y x₂ y₂,₂ + x₃ y₁,₂ x₂ y₂,₃ + x₃ y₁,₃ x₂ y₂,₄ + x₃ y₁,₄ + _y ]

> Row(Sol2bis[4][1],2);

[ -x₃ y₃,₁ + x₂ y₄,₁ + (x₁ + x₄) y₅,₁ -x₃ y₃,₂ + x₂ y₄,₂ + (x₁ + x₄) y₅,₂
-x₃ y₃,₃ + x₂ y₄,₃ + (x₁ + x₄) y₅,₃ -x₃ y₃,₄ + x₂ y₄,₄ + (x₁ + x₄) y₅,₄ ]

> Row(Sol2bis[4][1],3);

[ x₂ y₂,₁ + x₃ y₁,₁ - _y x₂ y₂,₂ + x₃ y₁,₂ x₂ y₂,₃ + x₃ y₁,₃ x₂ y₂,₄ + x₃ y₁,₄ - _y ]

> Row(Sol2bis[4][1],4);

[ x₂ y₃,₁ - x₃ y₄,₁ + (x₁ + x₄) y₆,₁ x₂ y₃,₂ - x₃ y₄,₂ + (x₁ + x₄) y₆,₂
x₂ y₃,₃ - x₃ y₄,₃ + (x₁ + x₄) y₆,₃ x₂ y₃,₄ - x₃ y₄,₄ + (x₁ + x₄) y₆,₄ ]

Let us successively display the rows of the v-component of the second solution:

> Row(Sol2bis[4][2],1);

[ y₁,₁ y₁,₂ y₁,₃ y₁,₄ ]

> Row(Sol2bis[4][2],2);

[ -x₃ y₂,₁ + x₂ y₃,₁ + (x₁ + x₄) y₄,₁ -x₃ y₂,₂ + x₂ y₃,₂ + (x₁ + x₄) y₄,₂
-x₃ y₂,₃ + x₂ y₃,₃ + (x₁ + x₄) y₄,₃ -x₃ y₂,₄ + x₂ y₃,₄ + (x₁ + x₄) y₄,₄ ]

> Row(Sol2bis[4][2],3);

[ -y₁,₁ + x₃ (2 _y x₄ y₁,₁ + x₂ y₅,₁ + _y) - x₂ x₃ y₅,₁
-y₁,₃ + x₃ (2 _y x₄ y₁,₃ + x₂ y₅,₃) - x₂ x₃ y₅,₃
-y₁,₄ + x₃ (2 _y x₄ y₁,₄ + x₂ y₅,₄ + _y) - x₂ x₃ y₅,₄ ]

> Row(Sol2bis[4][2],4);

[ x₂ y₂,₁ - x₃ y₃,₁ + (x₁ + x₄) y₆,₁ x₂ y₂,₂ - x₃ y₃,₂ + (x₁ + x₄) y₆,₂
x₂ y₂,₃ - x₃ y₃,₃ + (x₁ + x₄) y₆,₃ x₂ y₂,₄ - x₃ y₃,₄ + (x₁ + x₄) y₆,₄ ]

Let us successively display the rows of the v-component of the third solution:

> Row(Sol2bis[4][3],1);

[ y₁,₁ y₁,₂ y₁,₃ y₁,₄ ]

> Row(Sol2bis[4][3],2);

[ -x₃ y₂,₁ + x₂ y₃,₁ + (x₁ + x₄) y₄,₁ -x₃ y₂,₂ + x₂ y₃,₂ + (x₁ + x₄) y₄,₂
-x₃ y₂,₃ + x₂ y₃,₃ + (x₁ + x₄) y₄,₃ -x₃ y₂,₄ + x₂ y₃,₄ + (x₁ + x₄) y₄,₄ ]

> Row(Sol2bis[4][3],3);

[ -y₁,₁ + _y x₃² x₄ y₅,₁ + x₂ (2 _y x₄ y₁,₁ + _y - y₅,₁)
-y₁,₃ + _y x₃² x₄ y₅,₃ + x₂ (2 _y x₄ y₁,₃ - y₅,₃)
-y₁,₄ + _y x₃² x₄ y₅,₄ + x₂ (2 _y x₄ y₁,₄ + _y - y₅,₄) ]

> Row(Sol2bis[4][3],4);

[ x₂ y₂,₁ - x₃ y₃,₁ + (x₁ + x₄) y₆,₁ x₂ y₂,₂ - x₃ y₃,₂ + (x₁ + x₄) y₆,₂
x₂ y₂,₃ - x₃ y₃,₃ + (x₁ + x₄) y₆,₃ x₂ y₂,₄ - x₃ y₃,₄ + (x₁ + x₄) y₆,₄ ]

Using the option “reduced”, we get shorter expressions for the v-components of the solutions for k = 2.
RankFactorization(M, [D1, D2, D3, D4], 3) & Solutions(M, [D1, D2, D3, D4], 3) Let us now apply RankFactorization with k = 3.

> RF3 := RankFactorization(M, [D1,D2,D3,D4],3):

We first obtain that the ideal $\mathcal{J}_3$ is generated by:

> RF3[1];

$[x_3, x_2, x_1 + x_4]$

Thus, we have $\mathcal{J}_3 = \langle x_3, x_2, x_1 + x_4 \rangle$ and $S_3 = \mathcal{R}/\mathcal{J}_3$.

The second output is the matrix $K_3$ defined by:

> RF3[2];

$$
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}
$$

Hence, we have $K_3 = I_4$. Again, the third one is the matrix $Y$ defined by:

> RF3[3];

[ 1 0 0 1 ]

The fourth output is a list of the non-nilpotent elements of a set of generators {$g_{3,i}$}$_{i \in I_3}$ of $\mathcal{I}_3 = \text{Fitt}_0(\mathcal{B}_3)$:

> RF3[4];

[x_4]

We thus get $I_3 = \{1\}$ and $g_{3,1} = x_4$. In particular, a unique solution of the rank factorization problem eq. (4) can be found over the localization of $S_3$ with respect to the multiplicative set $\{h_{3,1}^k\}_{k \in \mathbb{Z}}$, i.e., $S_{3,h_{3,1}} = S_0[y]/\langle y h_{3,1} - 1 \rangle = S_0[h_{3,1}^{-1}]$.

The next output is a right inverse of the matrix $B_3$ over the ring $S_{3,h_{3,1}}$:

> RF3[5];

table(
  1 =
    [[
      0
      , 0
      , -y
      , 0
    ]])
)

The sixth output is the right kernel of the matrix $B_3$ over $S_{3,h_{3,1}}$, i.e., $\ker_{S_{3,h_{3,1}}}(B_3)$.

> RF3[6];

table(
  1 =
    [[
      1 & 0 & 0 \\
      0 & 1 & 0 \\
      1 & 0 & 0 \\
      0 & 0 & 1
    ]])
)

The next output is the polynomial ring $\mathcal{R}[y]$.

> RF3[7];

[Ore_algebra, ["diff", "diff", "diff", "diff", "diff"], [t_1, t_2, t_3, t_4, _t], [x_1, x_2, x_3, x_4, _y], [t_1, t_2, t_3, t_4, _t], [], 0, [], [], [t_1, t_2, t_3, t_4, _t], [], [], [diff = [x_1, t_1], diff = [x_2, t_2], diff = [x_3, t_3], diff = [x_4, t_4], diff = [_, y, _t]],

[ -a -> -a * x_1 - (partial / (partial t_1 - a)), -a -> -a * x_2 - (partial / (partial t_2 - a)), -a -> -a * x_3 - (partial / (partial t_3 - a)),

- a -> -a * x_4 - (partial / (partial t_4 - a)), -a -> -a * -y - (partial / (partial _t - a)) ]]

RR n° 9438
Again, the last output is the matrix $A = (D_1 x \dots D_4 x)$, where $x = (x_1 \dots x_4)^T$, defined by:

> RF3[8];

$$ \begin{bmatrix} x_1 & 0 & x_4 & 0 \\ 0 & x_2 & 0 & x_3 \\ 0 & -x_3 & 0 & -x_2 \\ -x_4 & 0 & -x_1 & 0 \end{bmatrix} $$

If the “reduced” option is used, then the same outputs are obtained.

Let us now directly compute the solutions of the rank factorization for $k = 3$.

> Sol3 := Solutions(M, [D1, D2, D3, D4], 3):

> for i from 1 to nops(Sol3) do print(Sol3[i]) od;

$$ [x_3, x_2, x_1 + x_4], [x_4], \begin{bmatrix} x_1 & 0 & x_4 & 0 \\ 0 & x_2 & 0 & x_3 \\ 0 & -x_3 & 0 & -x_2 \\ -x_4 & 0 & -x_1 & 0 \end{bmatrix}, $$

$$ \text{table}\left( \left[ 1 = \begin{bmatrix} y_{1,1} & y_{1,2} & y_{1,3} & y_{1,4} \\ y_{2,1} & y_{2,2} & y_{2,3} & y_{2,4} \\ -y + y_{1,1} & y_{1,2} & y_{1,3} & -y + y_{1,4} \\ y_{3,1} & y_{3,2} & y_{3,3} & y_{3,4} \end{bmatrix} \right] \right) $$

table([1 = [ Ore\_algebra, ["diff", "diff", "diff", "diff", "diff"], [t_1, t_2, t_3, t_4, _t], [x_1, x_2, x_3, x_4, _y], [t_1, t_2, t_3, t_4, _t], [y_{1,1}, y_{1,2}, y_{1,3}, y_{1,4}, y_{2,1}, y_{2,2}, y_{2,3}, y_{2,4}, y_{3,1}, y_{3,2}, y_{3,3}, y_{3,4}], 0, [], [], [t_1, t_2, t_3, t_4, _t], [], [], [diff = [x_1, t_1], diff = [x_2, t_2], diff = [x_3, t_3], diff = [x_4, t_4], diff = [_, y, _t]]],

$$ \begin{bmatrix} -a \rightarrow -a * x_1 - \left(\frac{\partial}{\partial t_1} - a\right), & -a \rightarrow -a * x_2 - \left(\frac{\partial}{\partial t_2} - a\right), & -a \rightarrow -a * x_3 - \left(\frac{\partial}{\partial t_3} - a\right), \\ -a \rightarrow -a * x_4 - \left(\frac{\partial}{\partial t_4} - a\right), & -a \rightarrow -a * y - \left(\frac{\partial}{\partial t} - a\right) & -a \rightarrow -a * _y - \left(\frac{\partial}{\partial _y} - a\right) \end{bmatrix} \] $$

Therefore, we have $\mathcal{J}_3 = \langle x_3, x_2, x_1 + x_4 \rangle$, $\mathcal{S}_3 = \mathcal{R}/\mathcal{J}_3$, $\mathcal{I}_3 = \langle x_4 \rangle_{\mathcal{S}_3}$, $u \in \mathcal{V}(\mathcal{J}_3) \setminus \mathcal{V}(\langle x_4 \rangle)$ and the v-component of the corresponding solution $(u, v)$ of the rank factorization problem is given by the matrix defined in the above table.

We can finally check again that the above expressions are solutions of the rank factorization problem:

> IsSolution(Sol3);

table([1 = [true]])

As shown above, the “reduced” option does not simplify the solutions in the case of $k = 3$.

### 6.2.3 Computation of the solutions of the rank factorization for Example 2

Let us consider again Example 2, i.e., the rank factorization problem eq. (4) with the following matrices:

> M := Matrix([[1,0],[0,1]]);

$$ M := \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} $$

> D1 := Matrix([-1,-2],[1,2]);

$$ D1 := \begin{bmatrix} -1 & -2 \\ 1 & 2 \end{bmatrix} $$

> D2 := Matrix([-3,-4],[3,4]);

$$ D2 := \begin{bmatrix} -3 & -4 \\ 3 & 4 \end{bmatrix} $$

Let us first compute the solutions of the corresponding rank factorization problem for $k = 0$.
> **Sol0** := Solutions(M, [D1, D2], 0);
"No solutions"

Thus, no solutions exist for $k = 0$.

Finally, let us compute the solutions of the corresponding rank factorization problem for $k = 1$.

> **Sol1** := Solutions(M, [D1, D2], 1);
"No solutions"

Therefore, as shown in Example 2, the rank factorization problem has no solution.

### 6.2.4 Computation of the solutions of the rank factorization for Example 3

Let us consider again Example 3, i.e., the rank factorization problem eq. (4) with the following matrices:

> **M** := Matrix([[15, 14, 13], [24, 20, 16]]);

$$M := \begin{bmatrix} 15 & 14 & 13 \\ 24 & 20 & 16 \end{bmatrix}$$

> **D1** := Matrix([[1, -1], [1, 1]]);

$$D1 := \begin{bmatrix} 1 & -1 \\ 1 & 1 \end{bmatrix}$$

> **D2** := Matrix([[1, 2], [-1, 2]]);

$$D2 := \begin{bmatrix} 1 & 2 \\ -1 & 2 \end{bmatrix}$$

> **D3** := Matrix([[1, 3], [4, 3]]);

$$D3 := \begin{bmatrix} 1 & 3 \\ 4 & 3 \end{bmatrix}$$

Let us first compute the solutions of the corresponding rank factorization problem for $k = 0$.

> **Sol0** := Solutions(M, [D1, D2, D3], 0):

> for i from 1 to 3 do print(Sol0[i]) od;

$$[x_2^2, x_2 x_1, x_1^2], [x_2^2, x_2 x_1, x_1^2], \begin{bmatrix} x_1 - x_2 & x_1 + 2x_2 & x_1 + 3x_2 \\ x_1 + x_2 & -x_1 + 2x_2 & 4x_1 + 3x_2 \end{bmatrix}$$

> nops(op(Sol0[4]));

3

Thus, we have three families of solutions.

Let us successively display the rows of the v-component of the first family of solutions

> **Row(Sol0[4][1], 1);**

$$\begin{aligned} & \left[ -\frac{15\ y\ (35\ x_1 + 194\ x_2)}{388} + \frac{6\ y\ (85\ x_1 + 194\ x_2)}{97} + (5\ x_1^2 + 12\ x_2 x_1)\ y_{1,1} \right. \\ & \left. -\frac{7\ y\ (35\ x_1 + 194\ x_2)}{194} + \frac{5\ y\ (85\ x_1 + 194\ x_2)}{97} + (5\ x_1^2 + 12\ x_2 x_1)\ y_{1,2} \right. \\ & \left. -\frac{13\ y\ (35\ x_1 + 194\ x_2)}{388} + \frac{4\ y\ (85\ x_1 + 194\ x_2)}{97} + (5\ x_1^2 + 12\ x_2 x_1)\ y_{1,3} \right] \\ & \text{Row(Sol0[4][1], 2);} \end{aligned}$$

> **Row(Sol0[4][1], 2);**

$$\begin{aligned} & \left[ \frac{15\ y\ (21\ x_1 + 31\ x_2)}{388} - \frac{6\ y\ (51\ x_1 - 91\ x_2)}{97} + (-3\ x_1^2 + 5\ x_2 x_1 + 6\ x_2^2)\ y_{1,1} \right. \\ & \left. -\frac{7\ y\ (21\ x_1 + 31\ x_2)}{194} - \frac{5\ y\ (51\ x_1 - 91\ x_2)}{97} + (-3\ x_1^2 + 5\ x_2 x_1 + 6\ x_2^2)\ y_{1,2} \right. \\ & \left. +\frac{13\ y\ (21\ x_1 + 31\ x_2)}{388} - \frac{4\ y\ (51\ x_1 - 91\ x_2)}{97} + (-3\ x_1^2 + 5\ x_2 x_1 + 6\ x_2^2)\ y_{1,3} \right] \\ & \text{RR n° 9438} \end{aligned}$$
> Row(Sol0[4][1],3);

$$ 
\begin{aligned}
& \left[ \frac{15\_y (7x_1 + 22x_2)}{194} - \frac{12\_y (17x_1 - 2x_2)}{97} + (-2x_1^2 - 4x_2^2) y_{1,1} \right. \\
& \left. \qquad + \frac{7\_y (7x_1 + 22x_2)}{97} - \frac{10\_y (17x_1 - 2x_2)}{97} + (-2x_1^2 - 4x_2^2) y_{1,2} \right. \\
& \left. \qquad + \frac{13\_y (7x_1 + 22x_2)}{194} - \frac{8\_y (17x_1 - 2x_2)}{97} + (-2x_1^2 - 4x_2^2) y_{1,3} \right]
\end{aligned}
$$

where the y's are arbitrary elements of $K$.

Let us successively display the rows of the v-component of the second family of solutions

> Row(Sol0[4][2],1);

$$ 
\begin{aligned}
& \left[ -\frac{945\_y x_1}{194} + (5x_1^2 + 12x_2 x_1) y_{1,1} + (5x_1 + 12x_2) y_{2,1} \right. \\
& \left. \qquad -\frac{435\_y x_1}{97} + (5x_1^2 + 12x_2 x_1) y_{1,2} + (5x_1 + 12x_2) y_{2,2} \right. \\
& \left. \qquad \left. -\frac{795\_y x_1}{194} + (5x_1^2 + 12x_2 x_1) y_{1,3} + (5x_1 + 12x_2) y_{2,3} \right] 
\end{aligned}
$$

> Row(Sol0[4][2],2);

$$ 
\begin{aligned}
& \left[ \frac{45\_y (11x_1 + 7x_2)}{194} + \frac{36\_y (x_1 - 17x_2)}{97} + (-3x_1^2 + 5x_2 x_1 + 6x_2^2) y_{1,1} + (6\_y x_2^3 - 3x_1 + 5x_2) y_{2,1} \right. \\
& \left. \qquad + \frac{21\_y (11x_1 + 7x_2)}{97} + \frac{30\_y (x_1 - 17x_2)}{97} + (-3x_1^2 + 5x_2 x_1 + 6x_2^2) y_{1,2} + (6\_y x_2^3 - 3x_1 + 5x_2) y_{2,2} \right. \\
& \left. \qquad \left. + \frac{39\_y (11x_1 + 7x_2)}{194} + \frac{24\_y (x_1 - 17x_2)}{97} + (-3x_1^2 + 5x_2 x_1 + 6x_2^2) y_{1,3} + (6\_y x_2^3 - 3x_1 + 5x_2) y_{2,3} \right] 
\end{aligned}
$$

> Row(Sol0[4][2],3);

$$ 
\begin{aligned}
& \left[ \frac{15\_y (11x_1 - 7x_2)}{97} + \frac{24\_y (x_1 + 17x_2)}{97} + (-2x_1^2 - 4x_2^2) y_{1,1} + (-4\_y x_2^3 - 2x_1) y_{2,1} \right. \\
& \left. \qquad + \frac{14\_y (11x_1 - 7x_2)}{97} + \frac{20\_y (x_1 + 17x_2)}{97} + (-2x_1^2 - 4x_2^2) y_{1,2} + (-4\_y x_2^3 - 2x_1) y_{2,2} \right. \\
& \left. \qquad \left. + \frac{13\_y (11x_1 - 7x_2)}{97} + \frac{16\_y (x_1 + 17x_2)}{97} + (-2x_1^2 - 4x_2^2) y_{1,3} + (-4\_y x_2^3 - 2x_1) y_{2,3} \right] 
\end{aligned}
$$

where the y's are arbitrary elements of $K$.

Finally, let us successively display the rows of the v-component of the third family of solutions

> Row(Sol0[4][3],1);

$$ 
\begin{aligned}
& \left[ \frac{1134\_y x_1}{97} + (5x_1^2 + 12x_2 x_1) y_{1,1} + (12\_y x_1 x_2 + 5) y_{2,1} + (5x_1 + 12x_2) y_{3,1} \right. \\
& \left. \qquad + \frac{1044\_y x_1}{97} + (5x_1^2 + 12x_2 x_1) y_{1,2} + (12\_y x_1 x_2 + 5) y_{2,2} + (5x_1 + 12x_2) y_{3,2} \right. \\
& \left. \qquad \left. + \frac{954\_y x_1}{97} + (5x_1^2 + 12x_2 x_1) y_{1,3} + (12\_y x_1 x_2 + 5) y_{2,3} + (5x_1 + 12x_2) y_{3,3} \right] 
\end{aligned}
$$

> Row(Sol0[4][3],2);

$$ 
\begin{aligned}
& \left[ \frac{15\_y (38x_1 + 33x_2)}{97} - \frac{24\_y (23x_1 - 3x_2)}{97} + (-3x_1^2 + 5x_2 x_1 + 6x_2^2) y_{1,1} + (5\_y x_1 x_2 + 6\_y x_2^2 - 3) y_{2,1} + (6\_y x_1 x_2^2 - 3x_1 + 5x_2) y_{3,1} \right. \\
& \left. \qquad + \frac{14\_y (38x_1 + 33x_2)}{97} - \frac{20\_y (23x_1 - 3x_2)}{97} + (-3x_1^2 + 5x_2 x_1 + 6x_2^2) y_{1,2} \right. \\
& \left. \qquad \left. + (5\_y x_1 x_2 + 6\_y x_2^2 - 3) y_{2,2} + (6\_y x_1 x_2^2 - 3x_1 + 5x_2) y_{3,2} \right. \\
& \left. \qquad \left. + \frac{13\_y (38x_1 + 33x_2)}{97} - \frac{16\_y (23x_1 - 3x_2)}{97} + (-3x_1^2 + 5x_2 x_1 + 6x_2^2) y_{1,3} \right. \\
& \left. \qquad \left. + (5\_y x_1 x_2 + 6\_y x_2^2 - 3) y_{2,3} + (6\_y x_1 x_2^2 - 3x_1 + 5x_2) y_{3,3} \right] 
\end{aligned}
$$

> Row(Sol0[4][3],3);
$$ 
\begin{aligned}
& \left[ -\frac{15\_y(7x_1 + 22x_2)}{97} + \frac{24\_y(17x_1 - 2x_2)}{97} + (-2x_1^2 - 4x_2^2) y_{1,1} + (-4\_y x_2^2 - 2) y_{2,1} + (-4\_y x_1 x_2^2 - 2x_1) y_{3,1} \right. \\
& \left. -\frac{14\_y(7x_1 + 22x_2)}{97} + \frac{20\_y(17x_1 - 2x_2)}{97} + (-2x_1^2 - 4x_2^2) y_{1,2} + (-4\_y x_2^2 - 2) y_{2,2} + (-4\_y x_1 x_2^2 - 2x_1) y_{3,2} \right. \\
& \left. -\frac{13\_y(7x_1 + 22x_2)}{97} + \frac{16\_y(17x_1 - 2x_2)}{97} + (-2x_1^2 - 4x_2^2) y_{1,3} + (-4\_y x_2^2 - 2) y_{2,3} + (-4\_y x_1 x_2^2 - 2x_1) y_{3,3} \right]
\end{aligned}
$$

where the y's are arbitrary elements of $K$.

We can check again that the above expressions are solutions to the rank factorization problem:

> IsSolution(Sol0);

table([1 = [true], 2 = [true], 3 = [true]])

Finally, let us compute the solutions of the corresponding rank factorization problem for $k = 1$.

> Sol1 := Solutions(M, [D1, D2, D3], 1);

"No solutions"

Finally, we can add the "reduced" option to the Solutions function to get shorter outputs for the v-components of the solutions.

> Sol0bis := Solutions(M, [D1, D2, D3], 0, "reduced"):

> for i from 1 to 3 do print(Sol0bis[i]) od;

$$ \begin{bmatrix} x_2^2, x_2 x_1, x_1^2 \end{bmatrix}, \begin{bmatrix} x_2^2, x_2 x_1, x_1^2 \end{bmatrix}, \begin{bmatrix} x_1 - x_2 & x_1 + 2x_2 & x_1 + 3x_2 \\ x_1 + x_2 & -x_1 + 2x_2 & 4x_1 + 3x_2 \end{bmatrix} $$

> nops(op(Sol0bis[4]));

3

Thus, we have three families of solutions.

Let us successively display the rows of the v-component of the first family of solutions

> Row(Sol0bis[4][1],1);

$$ 
\begin{aligned}
& \left[ -\frac{15\_y(35x_1 + 194x_2)}{388} + \frac{6\_y(85x_1 + 194x_2)}{97} + (5x_1^2 + 12x_1x_2) y_{1,1} \right. \\
& \left. -\frac{7\_y(35x_1 + 194x_2)}{194} + \frac{5\_y(85x_1 + 194x_2)}{97} + (5x_1^2 + 12x_1x_2) y_{1,2} \right. \\
& \left. -\frac{13\_y(35x_1 + 194x_2)}{388} + \frac{4\_y(85x_1 + 194x_2)}{97} + (5x_1^2 + 12x_1x_2) y_{1,3} \right]
\end{aligned}
$$

> Row(Sol0bis[4][1],2);

$$ 
\begin{aligned}
& \left[ \frac{15\_y(21x_1 + 31x_2)}{388} - \frac{6\_y(51x_1 - 91x_2)}{97} + (-3x_1^2 + 5x_1x_2 + 6x_2^2) y_{1,1} \right. \\
& \left. -\frac{7\_y(21x_1 + 31x_2)}{194} - \frac{5\_y(51x_1 - 91x_2)}{97} + (-3x_1^2 + 5x_1x_2 + 6x_2^2) y_{1,2} \right. \\
& \left. +\frac{13\_y(21x_1 + 31x_2)}{388} - \frac{4\_y(51x_1 - 91x_2)}{97} + (-3x_1^2 + 5x_1x_2 + 6x_2^2) y_{1,3} \right]
\end{aligned}
$$

> Row(Sol0bis[4][1],3);

$$ 
\begin{aligned}
& \left[ \frac{15\_y(7x_1 + 22x_2)}{194} - \frac{12\_y(17x_1 - 2x_2)}{97} + (-2x_1^2 - 4x_2^2) y_{1,1} \right. \\
& \left. -\frac{7\_y(7x_1 + 22x_2)}{97} - \frac{10\_y(17x_1 - 2x_2)}{97} + (-2x_1^2 - 4x_2^2) y_{1,2} \right. \\
& \left. +\frac{13\_y(7x_1 + 22x_2)}{194} - \frac{8\_y(17x_1 - 2x_2)}{97} + (-2x_1^2 - 4x_2^2) y_{1,3} \right]
\end{aligned}
$$

where the y's are arbitrary elements of $K$.

Let us successively display the rows of the v-component of the second family of solutions

> Row(Sol0bis[4][2],1);
$$ \left[ \begin{array}{c} -\frac{945}{194}yx_1 + (5x_1^2 + 12x_1x_2) y_{1,1} \\ -\frac{435}{97}yx_1 + (5x_1^2 + 12x_1x_2) y_{1,2} \\ -\frac{795}{194}yx_1 + (5x_1^2 + 12x_1x_2) y_{1,3} \end{array} \right] $$

> Row(SolObis[4][2],2);

$$ \left[ \begin{array}{c} \frac{45}{194}y(11x_1 + 7x_2) \\ \frac{36}{97}y(x_1 - 17x_2) \\ \frac{21}{97}y(11x_1 + 7x_2) \\ \frac{30}{97}y(x_1 - 17x_2) \\ \frac{39}{194}y(11x_1 + 7x_2) \\ \frac{24}{97}y(x_1 - 17x_2) \\ \frac{-3}{97}x_1^2 + 5x_1x_2 + 6x_2^2 \end{array} \right] y_{1,1} + \left[ \begin{array}{c} \frac{-3}{97}x_1^2 + 5x_1x_2 + 6x_2^2 \end{array} \right] y_{1,2} + \left[ \begin{array}{c} \frac{-3}{97}x_1^2 + 5x_1x_2 + 6x_2^2 \end{array} \right] y_{1,3} $$

> Row(SolObis[4][2],3);

$$ \left[ \begin{array}{c} \frac{15}{97}y(11x_1 - 7x_2) \\ \frac{24}{97}y(x_1 + 17x_2) \\ \frac{14}{97}y(11x_1 - 7x_2) \\ \frac{20}{97}y(x_1 + 17x_2) \\ \frac{13}{97}y(11x_1 - 7x_2) \\ \frac{16}{97}y(x_1 + 17x_2) \\ \frac{-2}{97}x_1^2 - 4x_2^2 \end{array} \right] y_{1,1} + \left[ \begin{array}{c} \frac{-2}{97}x_1^2 - 4x_2^2 \end{array} \right] y_{1,2} + \left[ \begin{array}{c} \frac{-2}{97}x_1^2 - 4x_2^2 \end{array} \right] y_{1,3} $$

where the y's are arbitrary elements of $K$.

Finally, let us successively display the rows of the v-component of the third family of solutions

> Row(SolObis[4][3],1);

$$ \left[ \begin{array}{c} \frac{1134}{97}yx_1 + (5x_1^2 + 12x_1x_2) y_{1,1} \\ \frac{1044}{97}yx_1 + (5x_1^2 + 12x_1x_2) y_{1,2} \\ \frac{954}{97}yx_1 + (5x_1^2 + 12x_1x_2) y_{1,3} \end{array} \right] $$

> Row(SolObis[4][3],2);

$$ \left[ \begin{array}{c} \frac{15}{97}y(38x_1 + 33x_2) \\ \frac{24}{97}y(23x_1 - 3x_2) \\ \frac{14}{97}y(38x_1 + 33x_2) \\ \frac{20}{97}y(23x_1 - 3x_2) \\ \frac{13}{97}y(38x_1 + 33x_2) \\ \frac{16}{97}y(23x_1 - 3x_2) \\ \frac{-3}{97}x_1^2 + 5x_1x_2 + 6x_2^2 \end{array} \right] y_{1,1} + \left[ \begin{array}{c} \frac{-3}{97}x_1^2 + 5x_1x_2 + 6x_2^2 \end{array} \right] y_{1,2} + \left[ \begin{array}{c} \frac{-3}{97}x_1^2 + 5x_1x_2 + 6x_2^2 \end{array} \right] y_{1,3} $$

> Row(SolObis[4][3],3);

$$ \left[ \begin{array}{c} \frac{15}{97}y(7x_1 + 22x_2) \\ \frac{24}{97}y(17x_1 - 2x_2) \\ \frac{14}{97}y(7x_1 + 22x_2) \\ \frac{20}{97}y(17x_1 - 2x_2) \\ \frac{13}{97}y(7x_1 + 22x_2) \\ \frac{16}{97}y(17x_1 - 2x_2) \\ \frac{-2}{97}x_1^2 - 4x_2^2 \end{array} \right] y_{1,1} + \left[ \begin{array}{c} \frac{-2}{97}x_1^2 - 4x_2^2 \end{array} \right] y_{1,2} + \left[ \begin{array}{c} \frac{-2}{97}x_1^2 - 4x_2^2 \end{array} \right] y_{1,3} $$

where the y's are arbitrary elements of $K$. Using the option "reduced", we thus get shorter expressions for the v-components of the solutions. We find again the solutions obtained in Example 2.

### 6.2.5 Computation of the solutions of the rank factorization for Example 4

Let us consider again Example 4, i.e., the rank factorization problem for the following matrices:

> M := Matrix([[30,0$2],[0$3],[12,0$2],[12,0$2]]);

$$ \begin{bmatrix} 30 & 0 & 0 \\ 0 & 0 & 0 \\ 12 & 0 & 0 \\ 12 & 0 & 0 \end{bmatrix} $$

> D1 := Matrix([[0$3,2],[3,0$2,1],[0$4],[0$3,2]]);

$$ \begin{bmatrix} 0 & 0 & 0 & 2 \\ 3 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 2 \end{bmatrix} $$
$$
> D2 := \text{Matrix([[5,3,0$2$],[0$4$],[0,5,2,0],[0,3,2,0]]);
$$
$$
\begin{bmatrix}
5 & 3 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 5 & 2 & 0 \\
0 & 3 & 2 & 0
\end{bmatrix}
$$

Let us compute the solutions of the corresponding rank factorization for $k = 0$:

> $\text{Sol0} := \text{Solutions}(M, [\text{D1}, \text{D2}], 0, \text{"reduced"})$;

> for i from 1 to 3 do print(Sol0[i]) od;

$$
[2 x_4 x_1 - 3 x_2 x_4 - 2 x_3 x_4, 3 x_1 x_2 + x_2 x_4, 2 x_1^2 - 2 x_1 x_3 + x_2 x_4, \\
9 x_2^2 x_4 + 6 x_3 x_2 x_4 + 2 x_2 x_4^2], [5 x_2 x_4 + 2 x_3 x_4, 3 x_1 x_3 + x_3 x_4],
$$

$$
\begin{bmatrix}
2x_4 & 5x_1 + 3x_2 \\
3x_1 + x_4 & 0 \\
0 & 5x_2 + 2x_3 \\
2x_4 & 3x_2 + 2x_3
\end{bmatrix}
$$

> nops(Sol0[4]);

2

Thus, we have two families of solutions. Let us display the v-component of the first family of solutions

> $\text{Sol0[4][1]}$;

$$
\begin{aligned}
& [3 x_2 y_{1,1} + (2 x_1 - 2 x_3) (4 \_y - y_{1,1} + (24 \_y x_3 x_4 + 20 \_y x_4^2 + 18) y_{2,1}) \\
& \quad 3 x_2 y_{1,2} + (2 x_1 - 2 x_3) (-y_{1,2} + (24 \_y x_3 x_4 + 20 \_y x_4^2 + 18) y_{2,2}) \\
& \quad 3 x_2 y_{1,3} + (2 x_1 - 2 x_3) (-y_{1,3} + (24 \_y x_3 x_4 + 20 \_y x_4^2 + 18) y_{2,3}) ]
\end{aligned}
$$

where the y's are arbitrary elements of $K$.

Let us now display the v-component of the second family of solutions

> $\text{Sol0[4][2]}$;

$$
\begin{aligned}
& [3 x_4 y_{1,1} + 3 x_4 (4 \_y - y_{1,1} + (24 \_y x_3 x_4 + 20 \_y x_4^2 + 18) y_{2,1}) - 60 (3 x_1 + x_4) \_y x_4^2 y_{2,1} \\
& \quad 3 x_4 y_{1,2} + 3 x_4 (-y_{1,2} + (24 \_y x_3 x_4 + 20 \_y x_4^2 + 18) y_{2,2}) - 60 (3 x_1 + x_4) \_y x_4^2 y_{2,2} \\
& \quad 3 x_4 y_{1,3} + 3 x_4 (-y_{1,3} + (24 \_y x_3 x_4 + 20 \_y x_4^2 + 18) y_{2,3}) - 60 (3 x_1 + x_4) \_y x_4^2 y_{2,3} ]
\end{aligned}
$$

where the y's are arbitrary elements of $K$.

The last element of Sol0 is the ring $\mathcal{R}[y]$:

> $\text{Sol0[5]}$;

$$
\text{table}([1 = [\text{Ore\_algebra}, [\text{"diff"}, \text{"diff"}, \text{"diff"}, \text{"diff"}, \text{"diff"}], [t_1, t_2, t_3, t_4, \_t], [x_1, x_2, x_3, x_4, \_y], [t_1, t_2, t_3, t_4, \_t], [y_{1,1}, y_{1,2}, y_{1,3}, y_{2,1}, y_{2,2}, y_{2,3}], 0, []], []], [t_1, t_2, t_3, t_4, \_t], []], [\_diff = [x_1, t_1], \_diff = [x_2, t_2], \_diff = [x_3, t_3], \_diff = [x_4, t_4], \_diff = [\_y, \_t]],
$$

$$
\left[
\begin{array}{l}
- a \rightarrow - a * x_1 - \left( \frac{\partial}{\partial t_1} - a \right), \quad - a \rightarrow - a * x_2 - \left( \frac{\partial}{\partial t_2} - a \right), \quad - a \rightarrow - a * x_3 - \left( \frac{\partial}{\partial t_3} - a \right), \\
- a \rightarrow - a * x_4 - \left( \frac{\partial}{\partial t_4} - a \right), \quad - a \rightarrow - a * \_y - \left( \frac{\partial}{\partial \_t} - a \right)
\end{array}
\right]
$$

We can check again that the above two expressions are solutions to the rank factorization problem:

> $\text{IsSolution}(\text{Sol0})$;

$$
\text{table}([1 = [true], 2 = [true]])
$$

Finally, let us compute the solutions for $k = 1$:

> $\text{Sol1} := \text{Solutions}(M, [\text{D1}, \text{D2}], 1)$;

"No solutions"

No solutions thus exist for $k = 1$.
### 6.2.6 Computation of the solutions of the rank factorization for Example 7

Let us consider again Example 7 studying the rank factorization problem eq. (4) for the following matrices:

```R
> M := Matrix([[0$3], [0$3]]);

> D1 := DiagonalMatrix([1$2]);

> D2 := Matrix([[0,1], [1,0]]);

> D3 := Matrix([[2,1], [1,2]]);
```

Let us compute a parametrization of the solutions of the rank factorization problem for $k = 0$:

```R
> Sol0 := Solutions(M, [D1,D2,D3], 0);
> for i from 1 to 4 do print(Sol0[i]) od;
```

$$ [0], [0], \begin{bmatrix} x_1 & x_2 & 2x_1 + x_2 \\ x_2 & x_1 & x_1 + 2x_2 \end{bmatrix}, \text{table} \left( \begin{bmatrix} 1 & \begin{bmatrix} 2y_{1,1} & 2y_{1,2} & 2y_{1,3} \\ y_{1,1} & y_{1,2} & y_{1,3} \\ -y_{1,1} & -y_{1,2} & -y_{1,3} \end{bmatrix} \end{bmatrix} \right) $$

The $y$'s are arbitrary elements of $\mathbb{K}$. Sol0[5] corresponds to the following polynomial ring:

```R
> Sol0[5];
[Ore_algebra, ["diff", "diff"], [t_1, t_2, t_3], [x_1, x_2], [t_1, t_2], [y_{1,1}, y_{1,2}, y_{1,3}], 0, [], [], [t_1, t_2], [], [], [diff = [x_1, t_1],
  diff = [x_2, t_2]], [-a -> -a * x_1 - (\partial/\partial t_1 - a), -a -> -a * x_2 - (\partial/\partial t_2 - a)]]
```

Let us now check again that Sol0 defines a family of solutions to the rank factorization problem:

```R
> IsSolution(Sol0);

  table ([1 = [true]])
```

Let us now compute a parametrization of the solutions for $k = 1$:

```R
> Sol1 := Solutions(M, [D1,D2,D3], 1);
> for i from 1 to 3 do print(Sol1[i]) od;
```

$$ [x_1^2 - x_2^2], [0], \begin{bmatrix} x_1 & x_2 & 2x_1 + x_2 \\ x_2 & x_1 & x_1 + 2x_2 \end{bmatrix} $$

```R
table(\*
  1 = \*
  \begin{bmatrix}
    2 y_{1,1} & 2 y_{1,2} & 2 y_{1,3} \\
    y_{1,1} - 3 x_2 y_{2,1} + (2 x_1 + x_2) y_{3,1} & y_{1,2} - 3 x_2 y_{2,2} + (2 x_1 + x_2) y_{3,2} & y_{1,3} - 3 x_2 y_{2,3} + (2 x_1 + x_2) y_{3,3} \\
    -y_{1,1} + (2 x_1 - x_2) y_{2,1} - x_2 y_{3,1} & -y_{1,2} + (2 x_1 - x_2) y_{2,2} - x_2 y_{3,2} & -y_{1,3} + (2 x_1 - x_2) y_{2,3} - x_2 y_{3,3}
  \end{bmatrix}
\*
)
```

The $y$'s are arbitrary elements of $\mathbb{K}$. Sol1[5] corresponds to the following polynomial ring:

```R
> Sol1[5];
[Ore_algebra, ["diff", "diff"], [t_1, t_2, t_3], [x_1, x_2], [t_1, t_2], [y_{1,1}, y_{1,2}, y_{1,3}, y_{2,1}, y_{2,2}, y_{2,3}, y_{3,1}, y_{3,2}, y_{3,3}],
  0, [], [], [t_1, t_2], [], [], [diff = [x_1, t_1], diff = [x_2, t_2]],
  [-a -> -a * x_1 - (\partial/\partial t_1 - a), -a -> -a * x_2 - (\partial/\partial t_2 - a)]
```

Inria
Let us now check again that `Sol1` defines a family of solutions to the rank factorization problem:

> `IsSolution(Sol1);`

table ([1 = [true]])

Finally, let us now compute a parametrization of the solutions for $k = 2$:

> `Sol2 := Solutions(M, [D1,D2,D3], 2);`

> `for i from 1 to 4 do print(Sol2[i]) od;`

$$[x_2, x_1], [0], \begin{bmatrix} x_1 & x_2 & 2x_1 + x_2 \\ x_2 & x_1 & x_1 + 2x_2 \end{bmatrix}, \text{table} \left( \begin{bmatrix} y_{1,1} & y_{1,2} & y_{1,3} \\ y_{2,1} & y_{2,2} & y_{2,3} \\ y_{3,1} & y_{3,2} & y_{3,3} \end{bmatrix} \right)$$

> `Sol2[5];`

$$[\text{Ore\_algebra}, [\text{"diff"}, \text{"diff"}], [t_1, t_2, t_3], [x_1, x_2], [t_1, t_2], [y_{1,1}, y_{1,2}, y_{1,3}, y_{2,1}, y_{2,2}, y_{2,3}, y_{3,1}, y_{3,2}, y_{3,3}], 0, [], [], [t_1, t_2], [], [], [diff = [x_1, t_1], diff = [x_2, t_2]],$$

$$[-a \rightarrow -a * x_1 - \left(\frac{\partial}{\partial t_1} - a\right), -a \rightarrow -a * x_2 - \left(\frac{\partial}{\partial t_2} - a\right)]$$

Let us now check again that `Sol2` defines a family of solutions to the rank factorization problem:

> `IsSolution(Sol2);`

table ([1 = [true]])

We find again the results given in Example 7.

## 6.3 Demodulation functions

We briefly describe a few more functions of the `RankFactorization` package which are useful for the study of the demodulation problems (which are associated with the rank factorization problem) listed in Table 3. For more details, see Section 1, [18], and the references therein.

The applications of the results obtained in this paper to the demodulation problems will be developed in a forthcoming paper. Therefore, more functions dedicated to the study of the demodulation problems will be added to the `RANKFACTORIZATION` package in the future.

The `AntiDiagonal` function computes the antidiagonal matrix of a given size (see Section 1).

The `LeeMatrix` function defines a Lee matrix $M$ of a given size $n$, namely, a matrix $M \in \mathbb{C}^{n \times n}$ that is $J$-real, i.e., $J_n \overline{M} = M$, where $J_n$ is the antidiagonal matrix of size $n$. Lee matrices are used to define Lee's transformations which map sets of centrohermitian matrices to sets of real matrices. For more details, see Section 1, [18], and the references therein.

The `IsCentroHermitian` function tests whether or not a complex matrix $M \in \mathbb{C}^{m \times n}$ is centrohermitian, namely, satisfies $\overline{M} = J_m M J_n$ (see Section 1).

The `CentroHermitian` function maps a matrix $M \in \mathbb{C}^{m \times n}$ to the centrohermitian $(M + J_m \overline{M} J_n)/2$. Let us illustrate these functions with simple examples.

Let us first compute the antidiagonal matrix of sizes 1 and 4:

> `AntiDiagonal(1);`

```
[ 1 ]
```

> `AntiDiagonal(4);`

$$\begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix}$$

Now, let us define a Lee matrix of size 2:

> `L := LeeMatrix(2);`
$$ \begin{bmatrix} 1 & I \\ 1 & -I \end{bmatrix} $$

Let us check whether or not the matrix $L$ is centrohermitian:

> IsCentroHermitian(L);

false

The matrix $L$ is not centrohermitian. We can then define the centrohermitian $(L + J_2 L J_2)/2$ defined by:

> H := CentroHermitian(L);

$$ H := \begin{bmatrix} \frac{1}{2} + \frac{I}{2} & \frac{1}{2} + \frac{I}{2} \\ \frac{1}{2} - \frac{I}{2} & \frac{1}{2} - \frac{I}{2} \end{bmatrix} $$

We can check again that the matrix $H$ is centrohermitian:

> IsCentroHermitian(H);

true

Let us now define a Lee matrix of size 3:

> LeeMatrix(3);

$$ \begin{bmatrix} 1 & 0 & I \\ 0 & 1 & 0 \\ 1 & 0 & -I \end{bmatrix} $$

Using the option "unitary", the LeeMatrix function then returns a unitary Lee matrix:

> M := LeeMatrix(3, "unitary");

$$ M := \begin{bmatrix} \frac{\sqrt{2}}{2} & 0 & \frac{I}{2}\sqrt{2} \\ 0 & 1 & 0 \\ \frac{\sqrt{2}}{2} & 0 & -\frac{I}{2}\sqrt{2} \end{bmatrix} $$

We can check again that $M$ is unitary, i.e., $M^* M = I_3$:

> simplify(Transpose(conjugate(M)).M);

$$ \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} $$

If we prefer to work with an algebraic expression for $\sqrt{2}$, i.e., if we want to use a symbol $u$ satisfying the equation $u^2 = 2$, then we can use the option "unitary_symbolic":

> R := LeeMatrix(3, "unitary_symbolic", u);

$$ R := \left[ \begin{bmatrix} \frac{1}{u} & 0 & \frac{I}{u} \\ 0 & 1 & 0 \\ \frac{1}{u} & 0 & -\frac{I}{u} \end{bmatrix} , u, u^2 - 2 \right] $$

We can work algebraically with the symbol $u$ as, for instance:

> assume(R[2], real);

> S := CentroHermitian(R[1]);
$$ S := \begin{bmatrix} \frac{1}{2u} + \frac{1}{2u} & 0 & \frac{1}{2u} + \frac{1}{2u} \\ 0 & 1 & 0 \\ \frac{1}{2u} - \frac{1}{2u} & 0 & \frac{1}{2u} - \frac{1}{2u} \end{bmatrix} $$

> IsCentroHermitian(S);

true

Finally, the next two examples show how Lee's transformations can be used to bijectively transform centrohermitian matrices onto real matrices. Such transformations play a central role in the study of the demodulation problems as briefly explained in Section 1.

Let us first consider the following square centrohermitian matrix:

> M := Matrix([[9+18*I, -225, 9+198*I], [0, 0, 0], [9-198*I, -225, 9-18*I]]);

$$ M := \begin{bmatrix} 9+18I & -225 & 9+198I \\ 0 & 0 & 0 \\ 9-198I & -225 & 9-18I \end{bmatrix} $$

We can check again that $M$ is centrohermitian:

> IsCentroHermitian(S);

true

Let us now define a Lee Matrix of size 3

> U := LeeMatrix(3);

$$ U := \begin{bmatrix} 1 & 0 & I \\ 0 & 1 & 0 \\ 1 & 0 & -I \end{bmatrix} $$

which is, by construction, invertible. Let us compute its inverse:

> U_inv := MatrixInverse(U);

$$ U_{inv} := \begin{bmatrix} \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 1 & 0 \\ -\frac{1}{2} & 0 & \frac{1}{2} \end{bmatrix} $$

We can now introduce the matrix $M_ρ = U^{-1} M U$ defined by:

> M_rho := U_inv.M.U;

$$ M_{rho} := \begin{bmatrix} 18 & -225 & 180 \\ 0 & 0 & 0 \\ 216 & 0 & 0 \end{bmatrix} $$

We can check that $M_ρ \in \mathbb{R}^{3 \times 3}$. Hence, the centrohermitian $M$ is sent to the real matrix $M_ρ = U^{-1} M U$.
Of course, this transformation is invertible:

> U.M_rho.U_inv;

$$ \begin{bmatrix} 9+18I & -225 & 9+198I \\ 0 & 0 & 0 \\ 9-198I & -225 & 9-18I \end{bmatrix} $$

Therefore, the set $CH_{3,3}$ of the 3 × 3 centrohermitian matrices is bijectively maps onto $\mathbb{R}^{3 \times 3}$.

Let us consider the non-square centrohermitian matrix, i.e., the following 2 × 5 centrohermitian matrix:

> M := Matrix(2, 5, [[-29, 0, -26, -6*I, -56*I], [56*I, 6*I, -26, 0, -29]]);

$$ M := \begin{bmatrix} -29 & 0 & -26 & -6I & -56I \\ 56I & 6I & -26 & 0 & -29 \end{bmatrix} $$
<table><tr><td><b>3</b></td><td><b>General solutions</b></td><td><b>12</b></td></tr><tr><td>3.1</td><td>Case of a full row rank matrix <i>M</i></td><td>13</td></tr><tr><td>3.2</td><td>General case</td><td>16</td></tr><tr><td>3.2.1</td><td>Necessary conditions on <i>u</i></td><td>17</td></tr><tr><td>3.2.2</td><td>Study of the kernel of the matrix <i>Q</i></td><td>18</td></tr><tr><td>3.2.3</td><td>General solutions for the case <i>M</i> = 0</td><td>21</td></tr><tr><td>3.2.4</td><td>Construction of the matrix <i>B</i> as a pullback</td><td>25</td></tr><tr><td>3.2.5</td><td>Characterization of the existence of a right inverse of <i>B</i></td><td>28</td></tr><tr><td>3.2.6</td><td>Solutions of the rank factorization problem</td><td>30</td></tr><tr><td><b>4</b></td><td><b>Getting all the solutions of the rank factorization problem</b></td><td><b>37</b></td></tr><tr><td>4.1</td><td>The solutions of the rank factorization problem</td><td>37</td></tr><tr><td>4.2</td><td>A few final remarks on the solution space</td><td>40</td></tr><tr><td><b>5</b></td><td><b>Conclusion</b></td><td><b>43</b></td></tr><tr><td><b>6</b></td><td><b>Appendix: The RANKFACTORIZATION package</b></td><td><b>45</b></td></tr><tr><td>6.1</td><td>Low-level functions</td><td>47</td></tr><tr><td>6.1.1</td><td><i>FittingIdeal</i></td><td>47</td></tr><tr><td>6.1.2</td><td><i>Saturation</i></td><td>48</td></tr><tr><td>6.1.3</td><td><i>IsNilpotent &amp; IsInvertible</i></td><td>49</td></tr><tr><td>6.1.4</td><td><i>Syzygies, ReducedSygyzies, Factorization &amp; Simplification</i></td><td>50</td></tr><tr><td>6.2</td><td>Main commands for solving the rank factorization problem</td><td>58</td></tr><tr><td>6.2.1</td><td>Description of the main functions of the <i>RankFactorization</i> package</td><td>58</td></tr><tr><td>6.2.2</td><td>Computation of the solutions of the rank factorization for Example 1 &amp; Example 13</td><td>58</td></tr><tr><td>6.2.3</td><td>Computation of the solutions of the rank factorization for Example 2</td><td>72</td></tr><tr><td>6.2.4</td><td>Computation of the solutions of the rank factorization for Example 3</td><td>73</td></tr><tr><td>6.2.5</td><td>Computation of the solutions of the rank factorization for Example 4</td><td>76</td></tr><tr><td>6.2.6</td><td>Computation of the solutions of the rank factorization for Example 7</td><td>78</td></tr><tr><td>6.3</td><td>Demodulation functions</td><td>79</td></tr></table>
Inria

RESEARCH CENTRE
PARIS

2 rue Simone Iff - CS 42112
75589 Paris Cedex 12

Publisher
Inria
Domaine de Voluceau - Rocquencourt
BP 105 - 78153 Le Chesnay Cedex
inria.fr

ISSN 0249-6399