# On the general solutions of a rank factorization problem

Roudy Dagher, Elisa Hubert, Alban Quadrat

► To cite this version:

Roudy Dagher, Elisa Hubert, Alban Quadrat. On the general solutions of a rank factorization problem. [Research Report] RR-9438, Sobonne Université, IMJ - PRG, Inria Paris; Inria Lille - Nord Europe; Laboratoire d'Analyse des Signaux et Processus Industriels. 2021, pp.57. hal-03479643v2

HAL Id: hal-03479643

https://inria.hal.science/hal-03479643v2

Submitted on 28 Sep 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Ínria

# On the general solutions of a rank factorization problem

Roudy Dagher, Elisa Hubert, Alban Quadrat

## RESEARCH REPORT

### N° 9438

December 2021

Project-Teams Ouragan
<figure><img src="image_2.png" /></figure>
<figure><img src="image_3.png" /></figure>

# On the general solutions of a rank factorization problem

Roudy Dagher*, Elisa Hubert†, Alban Quadrat‡

Project-Teams Ouragan

Research Report n° 9438 — version 2 — initial version December 2021 —
revised version September 2023 § — 83 pages

The authors would like to thank Axel Barrau for motivating discussions on the general rank factorization problem, the Safran Tech company for its scientific and financial support, and anonymous referees for their comments on the first version of the paper that helped us to improve its form and quality.

This paper is dedicated to Orion, our bright new constellation. With all our love!

RESEARCH CENTRE
PARIS

2 rue Simone Iff - CS 42112
75589 Paris Cedex 12

<footnote>* Inria Lille - Nord Europe (roudy.dagher@inria.fr)</footnote>

<footnote>† University of Lyon, UJM-St-Etienne, LASPI, France (elisa.hubert@wanadoo.fr)</footnote>

<footnote>‡ Sorbonne Université and Université de Paris, CNRS, Inria Paris, IMJ-PRG, F-75005 Paris, France (al-ban.quadrat@inria.fr, https://who.rocq.inria.fr/Alban.Quadrat/)</footnote>

<footnote>§ The revised version of the research report improves the form and the readability of the previous version by adding more mathematical details and more precisely describing the computational aspects, as well as by illustrating the RANK-FACTORIZATION package – dedicated to the rank factorization problem – in the Appendix.</footnote>
**Abstract:** Vibration analysis aims to identify a rotating machinery's potential failures by monitoring its vibration levels, i.e., by measuring the vibrations and comparing them to known failure vibration signals. New demodulation methods have recently been introduced in acoustic and signal processing to diagnose gearboxes. This new approach put forward the mathematical problem of decomposing a given complex matrix $M$ as $\sum_{i=1}^{r} D_i u v_i$, where $D_1, \dots, D_r$ are fixed matrices and $u$ (resp., $v_1, \dots, v_r$) a row vector (resp., column vectors) to be determined. This problem is equivalent to factoring $M$ as $M = (D_1 u \dots D_r u) (v_1^T \dots v_r^T)^T$, where the integer $r$ is larger than or equal to the rank of $M$. Using methods of algebraic geometry, module theory, homological algebra, and computer algebra, we study this particular rank factorization problem. We characterize the general solutions of the corresponding polynomial system. The results we develop are effective in the sense of computer algebra, i.e., algorithms are obtained that can be implemented in a computer algebra system that effectively handles polynomial systems (Gröbner bases). The symbolic package RANKFACTORIZATION has thus been developed to effectively study this particular rank factorization problem and the corresponding demodulation problems.

**Key-words:** Rank factorization problem, polynomial systems, computer algebra, module theory, homological algebra, demodulation, gearbox fault detection/surveillance, vibration analysis
Sur les solutions générales d'un problème de factorisation de rang

**Résumé** : L'analyse vibratoire a pour but l'identification de potentiels défauts d'une machine tour-
nante par la surveillance de ses niveaux de vibration, c'est-à-dire par la mesure de ses vibrations et la
comparaison avec des signaux de défauts connus. Pour le diagnostic d'engrenages, de nouvelles méth-
odes de démodulation ont récemment été introduites en acoustique et en traitement du signal. Cette
nouvelle approche a mis en avant le problème mathématique consistant à écrire une matrice M sous la
forme de $\sum_{i=1}^{r} D_i u v_i$, où $D_1, \dots, D_r$ sont des matrices fixées et $u$ (resp., $v_1, \dots, v_r$) un vecteur colonne
данной лини) à déterminer. Ce problème est équivalent à factoriser M sous la forme de
$M = (D_1 u \dots D_r u) (v_1^T \dots v_r^T)^T$, où l'entier r est supérieur ou égal au rang de M. En utilisant des
méthodes de géométrie algébrique, de théorie des modules, d'algèbre homologique et de calcul formel,
nous étudions ce problème particulier de factorisation de rang. Nous caractérisons les solutions générales
du système polynomial associé. Les résultats obtenus sont effectifs au sens du calcul formel, c'est-à-dire
nous proposons des algorithmes implantables dans un système de calcul formel permettant l'étude effec-
tive des systèmes polynomiaux (bases de Gröbner). La librairie symbolique RANKFACTORIZATION a ainsi
été développée pour l'étude effective du problème de factorisation de rang précédent et des problèmes de
démodulation correspondants.

**Mots-clés** : Problème de factorisation de rang, systèmes polynomiaux, théorie des modules, algèbre homologique, démodulation, détection et surveillance des défauts d'engrenages, analyse vibratoire
# 1 Introduction

The mathematical problem studied in this paper has recently been introduced in the acoustic, vibration analysis, and signal processing literature. Let us briefly explain the context in which it was introduced.

Within the frequency domain [24], the toothed gearbox vibration [22] can be interpreted as a modulation process of a high-frequency periodic carrier with a low-frequency periodic modulation [3, 4, 14, 15]. For gearbox fault surveillance, one has to separate these two time-domain signals and compare them to known failure vibration signals. The deviation of the signals can arise from a change in the tooth's shape due to a damaging effect. Detecting the appearance of these defects is an important issue in vibration analysis and for different industrial applications<fnref n="1" />. To study this problem, demodulation methods [24] were used and generalized in [14, 15]. Let us briefly state the main ideas of the approach developed in [14].

In practice, the toothed gearbox vibration is measured and some of the Fourier coefficients of this periodic real-valued time signal are stored into a so-called centrohermitian matrix $M \in \mathbb{C}^{m \times n}$ [13, 21], namely, a complex matrix of size $m \times n$ which satisfies the identity $\bar{M} = J_m M J_n$, where $\bar{M}$ stands for the complex conjugate of $M$ and $J_m$ (resp., $J_n$) denotes the anti-diagonal matrix of size $m \times m$ (resp., $n \times n$). More precisely, if $s$ is the T-periodic real-valued signal of the toothed gearbox vibration, then $s$ can be expressed by its Fourier series $s(t) = \sum_{j \in \mathbb{Z}} c_j(s) e^{-\frac{2\pi i j t}{T}}$, where the Fourier coefficients of $s$, defined by $c_j(s) = \frac{1}{T} \int_0^T s(t) e^{-\frac{2\pi i j t}{T}} dt$ for $j \in \mathbb{Z}$, then satisfy the identity $\overline{c_j(s)} = c_{-j}(\bar{s}) = c_{-j}(s)$ for all $j \in \mathbb{Z}$. The vectors $C_l = (c_{-l}(s) \dots c_0(s) \dots c_l(s))^T \in \mathbb{C}^{(2l+1) \times 1}$ for $l \ge 0$ and the following matrix

$$ M = \begin{pmatrix} c_q(2p+1)+p & \dots & c_p & \dots & c_{-q}(2p+1)+p \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ c_q(2p+1) & \dots & c_0 & \dots & c_{-q}(2p+1) \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ c_q(2p+1)-p & \dots & c_{-p} & \dots & c_{-q}(2p+1)-p \end{pmatrix} \in \mathbb{C}^{(2p+1) \times (2q+1)}, \quad p, q \ge 0, $$

respectively satisfy the identities $\overline{C_l} = J_{2l+1} C_l J_1$ and $\overline{M} = J_{2p+1} M J_{2q+1}$, which shows that $C_l$ and $M$ are both centrohermitian matrices. Fixing $r+1$ centrohermitian matrices $D_1, \dots, D_r \in \mathbb{C}^{(2p+1) \times (2p+1)}$ (which depend on the demodulation problem under study) and $M \in \mathbb{C}^{(2p+1) \times (2q+1)}$ (coming from the measurement of the signal $s$), the demodulation problem introduced in [14, 15] aims at determining – if they exist – a centrohermitian column vector $u \in \mathbb{C}^{(2p+1) \times 1}$ and $r$ centrohermitian row vectors $v_1, \dots, v_r \in \mathbb{C}^{1 \times (2q+1)}$ satisfying the following identity:

$$ M = \sum_{i=1}^{r} D_i u v_i. \qquad (1) $$

The computation of $u$ and $v_1, \dots, v_r$ yields the reconstruction of the different signals, and thus of their separation. The mathematical formulation eq. (1) encompasses standard demodulation problems [24]: the amplitude demodulation problem corresponds to $r=1$ and $D_1 = I_{2p+1}$, and the amplitude and phase demodulation problem corresponds to $r=2$, $D_1 = I_{2p+1}$, and $D_2 = 2\pi i f_c \operatorname{diag}(-p, \dots, 0, \dots, p)$, where $f_c > 0$, $p \in \mathbb{Z}_{>0}$, and $\operatorname{diag}(c_1, \dots, c_m)$ denotes the diagonal matrix with $c_1, \dots, c_m$ on the principal diagonal [14, 15]. Note that eq. (1) bores resemblance to the Singular Value Decomposition (SVD) of $M$, namely, $M = \sum_{i=1}^r \sigma_i u_i v_i^*$, for which we have $u_i = \sigma_i D_i u$ for $i=1, \dots, r$, where $r$ is the rank of $M$. Finally, eq. (1) corresponds to the SVD of $M$ in the case of the amplitude demodulation problem [14, 15].

The demodulation problem eq. (1) can be generalized as follows. Let $\mathbb{K}$ denote a field, $\mathbb{K}^{m \times n}$ the $\mathbb{K}$-vector space formed by all the $m \times n$ matrices with entries in $\mathbb{K}$, $r \in \mathbb{Z}_{>0}$, $D_1, \dots, D_r \in \mathbb{K}^{m \times m}$, and $M \in \mathbb{K}^{m \times n}$. Find – if they exist – a column vector $u \in \mathbb{K}^{m \times 1}$ and $r$ row vectors $v_1, \dots, v_r \in \mathbb{K}^{1 \times n}$ satisfying eq. (1). This last problem will be called the rank factorization problem because if a solution of eq. (1) exists, the matrix $M$ can then be factorized as follows

$$ M = (D_1 u \dots D_r u) \begin{pmatrix} v_1 \\ \vdots \\ v_r \end{pmatrix}, \qquad (2) $$

<footnote n="1">¹This work was motivated by a problem investigated by the Safran company.</footnote>
where the rank of $M$ must be less than or equal to $r$.

For fixed matrices $D_1, \dots, D_r$ and $M$, eq. (2) defines a system of $mn$ quadratic equations in $m+r^n$ unknowns – the entries of the vectors $u$ and $v_i$ for $i=1, \dots, r$. Hence, for $\mathbb{K}=\mathbb{Q}, \mathbb{R}, \mathbb{C}$, different algebraic geometry methods can be used to study the solutions of the rank factorization problem eq. (2) over the algebraic closure $\overline{\mathbb{K}}$ of $\mathbb{K}$. For more details on these methods, see, e.g., [10, 12, 20, 26].

The main goal of this paper is to characterize the solutions to the rank factorization problem eq. (2). Note that the study of the rank factorization problem was initiated in [2, 17, 18]. The particular set of solutions $(u, v)$ of eq. (2), where the matrix $v = (v_1^T \dots v_r^T)^T$ is assumed to have full row rank, were characterized in [17, 18] using linear algebra, and further studied in [2] using module theory. In this paper, we shall characterize the set of all the solutions of the rank factorization problem eq. (2). To do that, we shall exploit the *bilinear structure* of eq. (2) in $u$ and $v = (v_1^T \dots v_r^T)^T$ to explicitly characterize the general solutions of eq. (2) over $\overline{\mathbb{K}}$ in terms of *quasi-affine varieties* and explicit parametrizations. Our approach uses standard algebraic geometry, module theory, and homological algebra [10, 12, 25]. For $\mathbb{K}=\mathbb{Q}$, the general solutions over $\overline{\mathbb{K}}$ can be explicitly characterized using standard computer algebra systems that handle both elimination theory for polynomial systems (e.g., *Gröbner basis methods*) and basic homological methods such as, e.g., *Singular* [12], the *GAP library CapAndHomalg* [1], or the *Maple package OREMODULES* [6]. The different results presented in this paper are implemented in the *RANKFACTORIZATION* package [9] built upon the *OREMODULES* package.

Characterizing the solutions of a polynomial system is known to be a difficult issue in algebraic geometry and computer algebra especially when its affine algebraic set of complex solutions is not simply formed by a finite number of complex points. As we shall explain in this paper, the special structure of the class of polynomial systems defined by eq. (2) (i.e., its bilinear structure) allows us to characterize its solution space, particularly when $\mathbb{Q} \subseteq \mathbb{K}$, using methods of module theory, homological algebra, and computer algebra. Thus, the rank factorization problem provides an interesting class of polynomial systems for which their solution spaces can be explicitly characterized. Hence, we hope that this paper will draw the (effective) algebraic geometry community's attention to the rank factorization problem and that further investigations will be done on this problem (e.g., its intrinsic geometric characterization).

Finally, note that the demodulation problem eq. (1) corresponds to the rank factorization problem eq. (2) for $\mathbb{K}=\mathbb{C}$, where the solution $(u, v)$ are sought to be centrohermitian vectors. Hence, solving the rank factorization problem eq. (2) for $\mathbb{K}=\mathbb{C}$ does not solve the demodulation problem eq. (1). But a result of [21] shows that the set of centrohermitian matrices is bijectively mapped onto the set of real matrices by an explicit and simple *unitary* transformation $\rho$. Hence, the demodulation problem eq. (1) is equivalent to solving the rank factorization problem eq. (2) for $\mathbb{K}=\mathbb{R}$. More precisely, the demodulation problem eq. (1), arising in vibration analysis and studied in [14, 15], can be transformed into a rank factorization problem eq. (2) over $\mathbb{K}=\mathbb{R}$ for the transformed real matrices $\rho(M), \rho(D_1), \dots, \rho(D_r)$. The real solutions $u_\rho$ and $\{v_{i\rho}\}_{i=1,\dots,r}$, of the latter problem can then be transformed back to obtain the centrohermitian solutions $u = \rho^{-1}(u_\rho)$ and $\{v_i = \rho^{-1}(v_{i,\rho})\}_{i=1,\dots,r}$ of eq. (1). For more details, see [18, 19], where structured matrices (e.g., *coninvolutory* and *involutory* matrices) play an important role. To completely solve the demodulation problem eq. (1), we are finally led to understand how the solutions of eq. (2), obtained in this paper over $\overline{\mathbb{K}}$, can then be used to characterize the real solutions of eq. (2). This last mathematical problem is out of the scope of the present paper and it will be studied in a forthcoming publication dedicated to the application of the results of this paper to the demodulation problem eq. (1).

## Plan

This introductory section introduces the demodulation problem, the rank factorization problem, and the notations. In section 2, we state again the results obtained in [16, 17, 18, 19] which characterize all the solutions $(u, v)$ of the rank factorization problem eq. (2) for which $v = (v_1^T \dots v_r^T)^T$ has full row rank. These results use linear algebra and module theory. In section 3, using algebraic geometry, module theory, homological algebra, and computer algebra, we show how the results obtained in section 2 can be extended to characterize all the solutions of the rank factorization problem over $\overline{\mathbb{K}}$, where $\mathbb{K}=\mathbb{Q}, \mathbb{R}, \mathbb{C}$. Explicit examples, computed with the *RANKFACTORIZATION* package [9], illustrate the main results of the paper. In section 5, we end the paper by stating problems that will be studied in the future.
## Notation

In what follows, $\mathbb{K}$ will denote a field of characteristic 0, $\mathcal{R}$ a commutative unital ring, and $\mathcal{R}^{m \times n}$ the $\mathcal{R}$-module formed by all the $m \times n$ matrices with entries in $\mathcal{R}$. If $M \in \mathcal{R}^{m \times n}$, then we can consider the $\mathcal{R}$-homomorphisms $M: \mathcal{R}^{n \times 1} \to \mathcal{R}^{m \times 1}$ and $M: \mathcal{R}^{1 \times m} \to \mathcal{R}^{1 \times n}$ respectively defined by $(M)(\eta) = M\eta$ for all $\eta \in \mathcal{R}^{n \times 1}$ and $(M)(\lambda) = \lambda M$ for all $\lambda \in \mathcal{R}^{1 \times m}$. Their kernels, images, and cokernels $\mathcal{R}$-modules are respectively denoted by $ker_{\mathcal{R}}(M)$, $im_{\mathcal{R}}(M)$, coker$_{\mathcal{R}}(M)$, $ker_{\mathcal{R}}(M)$, $im_{\mathcal{R}}(M)$, and coker$_{\mathcal{R}}(M)$ [25]. A matrix $M$ is said to have full column rank (resp., full row rank) if $ker_{\mathcal{R}}(M) = 0$ (resp., $ker_{\mathcal{R}}(M) = 0$). If $M \in \mathbb{K}^{m \times n}$, then the rank of $M$, i.e., $dim_{\mathbb{K}}(im_{\mathbb{K}}(M))$, is denoted by rank$_{\mathbb{K}}(M)$. Let $I_n$ denote the identity matrix, i.e., the $n \times n$ matrix with 1 on the first diagonal and 0 elsewhere, and $J_n$ the exchange $n \times n$ matrix, i.e., the $n \times n$ matrix with 1 on the second diagonal and 0 elsewhere. Moreover, $diag(d_1, \dots, d_r)$ denotes the matrix with $d_1, \dots, d_r$ on the first diagonal. If $M \in \mathbb{C}^{m \times n}$, then $\overline{M}$ (resp., $M^*$) stands for the conjugate matrix (resp., the adjoint matrix, i.e., $\overline{M}^T \in \mathbb{C}^{n \times m}$). If $M \in \mathbb{K}^{m \times n}$, then we shall denote by $l$ the rank of $M$, i.e., $l = rank_{\mathbb{K}}(M) = dim_{\mathbb{K}}(im_{\mathbb{K}}(M))$. If $M$ is a matrix whose entries are functions of the vector variable $x = (x_1 \dots x_n)^T$, then $M(\psi)$ denotes the evaluation of $M$ at $\psi = (\psi_1 \dots \psi_n)^T \in \mathbb{K}^{n \times 1}$. Finally, if $\mathcal{I}$ is an ideal of the ring $\mathcal{R}$ generated by the elements $g_1, \dots, g_t \in \mathcal{R}$, then we shall note $\mathcal{I} = \langle g_1, \dots, g_t \rangle_{\mathcal{R}}$ or $\mathcal{I} = \sum_{i=1}^t \mathcal{R} g_i$.

# 2 Characterization of a particular set of solutions

## 2.1 A few preliminary remarks

In this section, we state of few remarks on the rank factorization problem eq. (1).

As stated in section 1, the rank factorization problem eq. (1) corresponds to a system of $mn$ quadratic equations in $m+r n$ unknowns (namely, the entries of the vectors $u \in \mathbb{K}^{m \times 1}$ and $v_i \in \mathbb{K}^{1 \times n}$ for $i = 1, \dots, r$). Thus, this problem belongs to the realm of (effective) algebraic geometry (see, e.g., [10, 12, 20] and the references therein).

For $n = 1$, using $r \ge 1$, we note that $m+r > m$, which shows that eq. (1) defines a system with more unknowns than algebraic equations.

For $n \ge 2$, the sign of $mn - (m+r n) = m(n-1) - nr$ is the sign of the function $\Psi(m, n, r) = m - \left(1 + \frac{1}{n-1}\right) r$, which satisfies $m - 2r \le \Psi(m, n, r) \le m - r$. Hence, if $m \ge 2r$ (resp., $m \le r$), then eq. (1) defines a polynomial system with more (resp., less) equations than unknowns. Thus, it is expected that the corresponding polynomial system becomes over-determined for large $m$ and $n$. But nothing can be said about the dimension of the corresponding polynomial system without having computed the Hilbert series of the corresponding polynomial ideal, and thus, without having first computed a Gröbner/Janet basis (or an equivalent normal form) for this polynomial system (see, e.g., [10, 12]). Using a computer algebra system, this can be done for fixed matrices $D_1, \dots, D_r$, and $M$ with rather small $m$ and $n$. However, this approach does not seem to be useful for the study of the general problem.

In what follows, we shall suppose that $D_1, \dots, D_r$ are not 0 and we use the following notations:

$$A(u) = (D_1 u \dots D_r u) \in \mathbb{K}^{m \times r}, \quad v = \begin{pmatrix} v_1 \\ \vdots \\ v_r \end{pmatrix} \in \mathbb{K}^{r \times n}. \qquad (3)$$

The rank factorization problem eq. (1) can then be rewritten as follows:

$$A(u) v = M. \qquad (4)$$

The bilinear structure in $u$ and $v$ is emphasized in eq. (4). Under the form eq. (4), eq. (1) corresponds to a factorization problem for the matrix $M \in \mathbb{K}^{m \times n}$.

It is important to note that the existence of $u \in \mathbb{K}^{m \times 1}$ and $v_i \in \mathbb{K}^{1 \times n}$ for $i = 1, \dots, r$ satisfying eq. (4) is equivalent to the existence of $u \in \mathbb{K}^{m \times 1}$ satisfying the following inclusion of $\mathbb{K}$-vector spaces:

$$\mathrm{im}_{\mathbb{K}}(M) \subseteq \mathrm{im}_{\mathbb{K}}(A(u)). \qquad (5)$$
Indeed, eq. (5) implies that each column $M_{\bullet i}$'s of $M$ belongs to $\mathrm{im}_K(A(u))$, i.e., the existence of $v_{\bullet i} \in \mathbb{K}^{r \times 1}$ such that $A(u) v_{\bullet i} = M_{\bullet i}$ for $i = 1, \dots, n$, which yields $A(u) v = M$ with $v = (v_{\bullet 1} \dots v_{\bullet n}) \in \mathbb{K}^{r \times n}$. Conversely, eq. (4) yields eq. (5).

Note that eq. (5) shows that a necessary condition on $M$ for the solvability of eq. (1) is:

$$l = \mathrm{rank}_K(M) \le \mathrm{rank}_K(A(u)) \le \min\{m, r\}. \qquad (6)$$

Therefore, if $l$ is not less than or equal to $\min\{m, r\}$, no solution of eq. (4) exists.

The choice of the terminology for Problem eq. (4), namely, the *rank factorization problem*, comes from the factorization condition eq. (4) and the rank condition eq. (6).

Finally, the approach that will be developed in the rest of the paper is based on the characterization of the set of all the vectors $u$'s such that the inclusion eq. (5) holds. In particular, $u$ must be chosen so that not all the $l \times l$ minors of the matrix $A(u)$ vanish.

## 2.2 Review on the characterization of particular set of solutions

We briefly state again results obtained in [2, 16, 17] which characterize a particular class of solutions of eq. (4). These results use linear algebra and module theory. In section 3, using also homological algebra and computer algebra, this approach will be generalized to characterize all the solutions of eq. (4). Since the approach will be extended in section 3, we now state again the main arguments.

The next lemma gives two necessary conditions for a solution $(u, v)$ of eq. (4) to be such that the matrix $v$ has full row rank (i.e., the rows of $v$ are $\mathbb{K}$-linearly independent).

**Lemma 1.** If there exists a solution $(u, v)$ of eq. (4) such that $v$ has full row rank, then:

1. $D_i u \in \mathrm{im}_K(M.)$ for $i = 1, \dots, r$.

2. $\mathrm{rank}_K(A(u)) = \mathrm{rank}_K(M) = l$, i.e., $\dim_K(\mathrm{span}_K\{D_i u\}_{i=1,\dots,r}) = l$.

*Proof.* Recall that the matrix $v$ has full row rank if and only if it admits a right inverse $t \in \mathbb{K}^{n \times r}$, i.e., $vt = I_r$. Hence, if a solution $(u, v)$ of eq. (4) exists with a full row rank matrix $v$, then eq. (4) yields $A(u) = Mt$, which, using eq. (5), shows that $\mathrm{im}_K(A(u)) = \mathrm{im}_K(M.)$. Hence, $u \in \mathbb{K}^{m \times 1}$ must satisfy Conditions 1 and 2. $\square$

In this section, we shall characterize the solutions of eq. (4) satisfying Conditions 1 and 2 of Lemma 1. Since these two conditions are usually not sufficient for $v$ to have full row rank, among the solutions $(u, v)$ of eq. (4) satisfying Conditions 1 and 2 are the solutions of eq. (4) with full rank matrices $v$. Note also that these two conditions depend only on $u$, i.e., no conditions on $v$ appear, which simplifies the search for such solutions as explained below.

Let us first study Condition 1 of Lemma 1.

**Lemma 2.** If $l < m$, let $p = m - l$ and $L \in \mathbb{K}^{p \times m}$ be a full row matrix whose rows define a basis of $\mathrm{ker}_K(\cdot, M)$, i.e., are such that $\mathrm{ker}_K(\cdot, M) = \mathrm{im}_K(\cdot, L)$. If $m = l$, then we set $L = (0 \dots 0) \in \mathbb{K}^{1 \times m}$.

Then, we have:

1. $\mathrm{ker}_K(L.) = \mathrm{im}_K(M.)$.

2. Condition 1 of Lemma 1 is equivalent to the fact that $u \in \mathbb{K}^{m \times 1}$ satisfies the $\mathbb{K}$-linear system $Nu = 0$, where:

$$N = \begin{pmatrix} L & D_1 \\ \vdots & \vdots \\ L & D_r \end{pmatrix} \in \mathbb{K}^{p \times m}. \qquad (7)$$

3. If $Z \in \mathbb{K}^{m \times d}$ is a full column matrix whose columns define a basis of $\mathrm{ker}_K(N.)$, where $d = \dim_K(\mathrm{ker}_K(N.))$ (if $l = m$, then $d = m$ and we can take $Z = I_m$), then Condition 1 of Lemma 1 is equivalent to $u = Z \psi$ for a certain $\psi \in \mathbb{K}^{d \times 1}$.
Proof. Let us first suppose that $\mathrm{im}_{\mathbb{K}}(M.) \neq \mathbb{K}^{m \times 1}$. Set $p = m - l > 0$. Let $L \in \mathbb{K}^{p \times m}$ be a full row rank matrix whose rows define a basis of $\mathrm{ker}_{\mathbb{K}}(M.)$, i.e., $\mathrm{ker}_{\mathbb{K}}(M.) = \mathrm{im}_{\mathbb{K}}(L.)$. Then, we get $LM = 0$, which shows that $\mathrm{im}_{\mathbb{K}}(M.) \subseteq \mathrm{ker}_{\mathbb{K}}(L.)$. Now, $\mathrm{dim}_{\mathbb{K}}(\mathrm{ker}_{\mathbb{K}}(L.)) = m - p = l$ yields $\mathrm{ker}_{\mathbb{K}}(L.) = \mathrm{im}_{\mathbb{K}}(M.)$. Hence, Condition 1 of Lemma 1 is equivalent to $D_i u \in \mathrm{ker}_{\mathbb{K}}(L.)$ for $i = 1, \dots, r$, i.e., $u \in \mathrm{ker}_{\mathbb{K}}(N.)$, where $N$ is given by eq. (7). Now, if $\mathrm{im}_{\mathbb{K}}(M.) = \mathbb{K}^{m \times 1} = \mathrm{ker}_{\mathbb{K}}(L.)$, i.e., $p = 0$, then $D_i u \in \mathbb{K}^{m \times 1} = \mathrm{im}_{\mathbb{K}}(M.)$ for $i = 1, \dots, r$, i.e., Condition 1 of Lemma 1 is equivalent to $u \in \mathbb{K}^{m \times 1}$, which is coherent with the fact that $N = 0$ and $\mathrm{ker}_{\mathbb{K}}(N.) = \mathbb{K}^{m \times 1}$. Finally, the third point is a direct consequence of the second point and the definition of $Z$. $\square$

According to 3 of Lemma 2, Condition 1 is equivalent to $u = Z \psi$ for a certain $\psi \in \mathbb{K}^{d \times 1}$. Condition 2 is then equivalent to $\psi \in \mathcal{P}$, where the set $\mathcal{P}$ is defined by:

$$ \mathcal{P} = \{ \psi \in \mathbb{K}^{d \times 1} \mid \mathrm{rank}_{\mathbb{K}}(A(Z \psi)) = l \}. $$

We have just shown that Conditions 1 and 2 of Lemma 1 are equivalent to $u = Z \psi$, where $\psi \in \mathcal{P}$.

Let us briefly treat the case of $M = 0$. We then have $l = 0$, $p = m$, $L = I_m$, $N = (D_1^T \dots D_r^T)^T$, $A(Z \psi) = (D_1 Z \psi \dots D_r Z \psi) = (0 \dots 0)$ for all $\psi \in \mathbb{K}^{d \times 1}$, where $\mathrm{ker}_{\mathbb{K}}(N.) = \mathrm{im}_{\mathbb{K}}(Z.)$ for a certain matrix $Z \in \mathbb{K}^{m \times d}$, i.e., $\mathcal{P} = \mathbb{K}^{d \times 1}$. Therefore, all the solutions $(u, v)$ of eq. (4) are of the form $(Z \psi, v)$ for all $\psi \in \mathbb{K}^{d \times 1}$ and for all $v \in \mathbb{K}^{r \times n}$.

In the rest of the section, we shall suppose that $M \neq 0$.

**Remark 1.** If $d = 0$, i.e., $\mathrm{ker}_{\mathbb{K}}(N.) = 0$, then $Z = 0$, and thus, $A(Z \psi) = A(0) = 0$. Since $M \neq 0$, then $\mathrm{im}_{\mathbb{K}}(A(u.)) = \{0\} \subset \mathrm{im}_{\mathbb{K}}(M.)$ and eq. (4) has no solution satisfying Conditions 1 and 2 of Lemma 1, and thus, no solution $(u, v)$ with a full row rank matrix $v$ exists.

**Remark 2.** Note that $\mathcal{P}$ is a linear cone, namely, $\lambda \psi \in \mathcal{P}$ for all $\lambda \in \mathbb{K}^{\times} = \mathbb{K} \setminus \{0\}$ and $\psi \in \mathcal{P}$.

The next lemma gives an equivalent characterization of the linear cone $\mathcal{P}$.

**Lemma 3.** Let $X \in \mathbb{K}^{m \times l}$ be a full column rank whose columns define a basis of $\mathrm{im}_{\mathbb{K}}(M.)$, i.e., $\mathrm{im}_{\mathbb{K}}(M.) = \mathrm{im}_{\mathbb{K}}(X.)$, where $l \ge 1$. Then, we have the following results:

1. There exists a unique matrix $Y \in \mathbb{K}^{l \times n}$ such that $M = XY$.

2. For $i = 1, \dots, r$, there exists a unique matrix $W_i \in \mathbb{K}^{l \times d}$ such that $D_i Z = X W_i$, where $Z$ is defined in Lemma 3.

3. Let $B(\psi) = (W_1 \psi \dots W_r \psi) \in \mathbb{K}^{l \times r}$ for all $\psi \in \mathbb{K}^{d \times 1}$. Then, the linear cone $\mathcal{P}$ satisfies:

$$ \mathcal{P} = \{ \psi \in \mathbb{K}^{d \times 1} \mid \mathrm{rank}_{\mathbb{K}}(B(\psi)) = l \}. \qquad (8) $$

Finally, the linear cone $\mathcal{P}$ does not depend on the choice of the bases of the $\mathbb{K}$-vector spaces $\mathrm{ker}_{\mathbb{K}}(M.)$, $\mathrm{ker}_{\mathbb{K}}(N.)$, where $N$ is defined by eq. (7), and $\mathrm{im}_{\mathbb{K}}(M.)$.

Proof. 1. Let $X \in \mathbb{K}^{m \times l}$ be a full column rank whose columns define a basis of $\mathrm{im}_{\mathbb{K}}(M.)$, i.e., $\mathrm{im}_{\mathbb{K}}(M.) = \mathrm{im}_{\mathbb{K}}(X.)$. Let $M_{\bullet i}$ denote the $i$th column of $M$ for $i = 1, \dots, n$. Then, there exist unique vector $Y_{\bullet i} \in \mathbb{K}^{l \times 1}$ such that $M_{\bullet i} = X Y_{\bullet i}$ for $i = 1, \dots, n$, which yields $M = XY$, where $Y = (Y_{\bullet 1} \dots Y_{\bullet n}) \in \mathbb{K}^{l \times n}$.

2. We have $D_i Z \psi \in \mathrm{ker}_{\mathbb{K}}(L.) = \mathrm{im}_{\mathbb{K}}(M.) = \mathrm{im}_{\mathbb{K}}(X.)$ for all $\psi \in \mathbb{K}^{d \times 1}$, which shows that there exists a unique matrix $W_i \in \mathbb{K}^{l \times d}$ such that $D_i Z = X W_i$ for $i = 1, \dots, r$. We then get:

$$ \forall \psi \in \mathbb{K}^{d \times 1}, \quad A(Z \psi) = (D_1 Z \psi \dots D_r Z \psi) = X (W_1 \psi \dots W_r \psi). \qquad (9) $$

3. The first part of the result is a direct consequence of the identity $A(Z \psi) = X B(\psi)$ for all $\psi \in \mathbb{K}^{d \times 1}$, where $X$ has full column rank. Finally, if the rows $L' \in \mathbb{K}^{(m-l) \times m}$ define another basis of $\mathrm{ker}_{\mathbb{K}}(M.)$, then there exists an invertible $T \in \mathbb{K}^{(m-l) \times (m-l)}$ such that $L' = T L$. If $N'$ is the matrix defined by eq. (7) where $L$ is replaced by $L'$, then $N' = T N$, and thus, $\mathrm{ker}_{\mathbb{K}}(N') = \mathrm{ker}_{\mathbb{K}}(N.)$. If $Z' \in \mathbb{K}^{m \times d}$ (resp., $X' \in \mathbb{K}^{m \times l}$) is another basis of $\mathrm{ker}_{\mathbb{K}}(N.)$ (resp., $\mathrm{im}_{\mathbb{K}}(M.)$), then there exists an invertible matrix $U \in \mathbb{K}^{d \times d}$ (resp., $V \in \mathbb{K}^{l \times l}$) such that $Z = Z' U$ (resp., $X = X' V$). Then, $D_i Z = X W_i$ yields $D_i Z' = X' (V W_i U^{-1})$, i.e., $W'_i = V W_i U^{-1}$ satisfies $D_i Z' = W'_i X'$ for $i = 1, \dots, r$. Finally, using the invertibility of $U$ and $V$, the matrix $B'(\psi) = (W'_1 \psi \dots W'_r \psi) = V B(U^{-1} \psi)$ has the same rank as $B(\psi)$ for all $\psi \in \mathbb{K}^{d \times 1}$, which shows that the linear cone $\mathcal{P}$ is independent of the choice of the different intermediate bases. $\square$
**Remark 3.** If a $l \times l$ minor of $B(\psi)$ is not 0, then $\mathcal{P}$ is not empty. Since the columns $W_i \psi$ of $B(\psi)$ are linear forms in $\psi = (\psi_1 \dots \psi_d)^T$, the $l \times l$ minors of $B(\psi)$ are either 0 or homogeneous polynomials in $\psi$ of total degree $l$. In particular, we find again that $\mathcal{P}$ is a linear cone.

**Remark 4.** If $\text{im}_K(M.) = \mathbb{K}^{m \times 1}$, i.e., $l = m$, then Condition 1 of Lemma 1 is always satisfied for all $u \in \mathbb{K}^{m \times 1}$ since $D_i u \in \mathbb{K}^{m \times 1}$ for all $u \in \mathbb{K}^{m \times 1}$ and $i = 1, \dots, r$. Equivalently, using Lemma 2, $L = (0 \dots 0) \in \mathbb{K}^{1 \times m}$, $N = 0$ (see eq. (7)), and thus, we can take $Z = I_m$, and $X = I_m$. Therefore, we have $W_i = D_i$, which yields $B(\psi) = (D_1 \psi \dots D_r \psi)$ and $u = \psi \in \mathcal{P} = \{\psi \in \mathbb{K}^{m \times 1} | \text{rank}_K(A(\psi)) = m\}$.

Let us state the characterization of the solutions of eq. (4) satisfying Conditions 1 and 2 of Lemma 1.

**Theorem 1 ([16]).** Let $D_i \in \mathbb{K}^{m \times m}$ for $i = 1, \dots, r$ and $M \in \mathbb{K}^{m \times n}$ be such that:

$$1 \le l = \text{rank}_K(M) \le \min\{m, r\}.$$

With the notations of Lemma 2 and Lemma 3, if the linear cone $\mathcal{P}$, defined by eq. (8), is not empty, then

$$\forall \psi \in \mathcal{P}, \quad \forall Y' \in \mathbb{K}^{(r-l) \times n}, \quad \left\{ \begin{array}{l} u = Z \psi, \\ v = (E_{\psi} \quad C_{\psi}) \begin{pmatrix} Y \\ Y' \end{pmatrix}, \end{array} \right. \qquad (10)$$

are the solutions of eq. (4) satisfying Conditions 1 and 2 of Lemma 1, where:

* The matrix $E_{\psi} \in \mathbb{K}^{r \times l}$ is a right inverse of $B(\psi)$, i.e., $B(\psi) E_{\psi} = I_l$,

* The columns of the matrix $C_{\psi} \in \mathbb{K}^{r \times (r-l)}$ define a basis of $\text{ker}_K(B(\psi).)$, i.e., $C_{\psi} \in \mathbb{K}^{r \times (r-l)}$ has full column matrix and satisfies $\text{ker}_K(B(\psi).) = \text{im}_K(C_{\psi}).$

In particular, if $l = r$, then $C_{\psi} = 0$ and the solution eq. (10) is unique.

Moreover, the matrix $v$ defined by eq. (10) has full row rank if and only if $Y' \in \mathbb{K}^{(r-l) \times n}$ is chosen so that $(Y^T \quad Y'^T)^T \in \mathbb{K}^{r \times n}$ has full row rank.

Finally, the results do not depend on the choice of bases for the different intermediate $\mathbb{K}$-vector spaces.

*Proof.* Using eq. (6), i.e., $0 < l \le r$, $\mathcal{P}$ characterizes the $\psi$'s which are so that $B(\psi)$ admits a right inverse $E_{\psi} \in \mathbb{K}^{r \times l}$, i.e., $B(\psi) E_{\psi} = I_l$. Using that $X$ has full column rank, we get:

$$\forall \psi \in \mathbb{K}^{d \times 1}, \quad A(Z \psi) v = M \iff X B(\psi) v = X Y \iff B(\psi) v = Y.$$

Hence, if $\psi \in \mathcal{P}$, then $v_* = E_{\psi} Y \in \mathbb{K}^{r \times n}$ is a particular solution of the linear inhomogeneous system $B(\psi) v = Y$. Let $C_{\psi} \in \mathbb{K}^{r \times (r-l)}$ be a full column matrix whose columns define a basis of $\text{ker}_K(B(\psi).)$, i.e., $\text{ker}_K(B(\psi).) = \text{im}_K(C_{\psi}).$ Then, all the solutions of eq. (1) satisfying Conditions 1 and 2 of Lemma 1 are of the form eq. (10). Note that $(E_{\psi} \quad C_{\psi}) \in \mathbb{K}^{r \times r}$ is invertible. Thus, $v$ has full row rank if and only if so has the matrix $(Y^T \quad Y'^T)^T$. Finally, let us prove that eq. (10) does not depend on the choice of the different intermediate bases. According to 3 of Lemma 3, $\mathcal{P}$ does not depend on them. Using the notations of the proof of 3 of Lemma 3, setting $\psi' = U \psi$, we have $u = Z \psi = Z' \psi'$ and, using the identity $B'(\psi') = V B(\psi)$ (see the proof of 3 of Lemma 3), $B(\psi) E_{\psi} = I_l$ yields $B'(\psi') (E_{\psi} V^{-1}) = I_l$, i.e., $E'_{\psi'} = E_{\psi} V^{-1}$ is a right inverse of $B'(\psi')$. Using $M = X'Y'$, where $X' = X V^{-1}$ and $Y' = VY$ (see the proof of 3 of Lemma 3), we get $E'_{\psi} Y' = E_{\psi} Y$. Finally, we clearly have $\text{ker}_K(B'(\psi').) = \text{ker}_K(B(\psi).). \quad \square$

**Remark 5.** For the demodulation problem eq. (1) studied in vibration analysis, as explained in Section 1, the matrices $M$ and $D_i$'s are then centrohermitian and the solutions $u$ and $v_i$ for $i = 1, \dots, r$ are also sought to be centrohermitian. We refer the readers to [18, 19] for the extensions of Theorem 1 to the demodulation problem. See also [17]. Note that structured matrices (e.g., *coninvolutory* and *involutory* matrices) then play an important role in the algebraic structure of the corresponding solutions.

Let us now study $\mathcal{P}$ in more detail. We first introduce a few more notations.

Let $\mathcal{R} = \mathbb{K}[x_1, \dots, x_d]$ be the commutative polynomial ring in $x_1, \dots, x_d$ with coefficients in $\mathbb{K}$, $x = (x_1 \dots x_d)^T$, and $B = (W_1 x \dots W_r x) \in \mathcal{R}^{l \times r}$. According to eq. (6), we have $1 \le l \le r$, i.e.,
B is a wide matrix. If $\mathcal{I}$ is the ideal of $\mathcal{R}$ generated by all the $l \times l$ minors of $B$, then $\mathcal{I}$ is either reduced to $\langle 0 \rangle$ or it can be generated by homogeneous polynomials $g_1, \dots, g_t$ of total degree $l$. Finally, if $V_{\mathcal{I}}(\mathcal{I}) = \{\psi \in \mathbb{K}^{d \times 1} | \forall P \in \mathcal{I}: P(\psi) = 0\}$ is the affine algebraic set associated with $\mathcal{I}$ [10, 12], then the linear cone $\mathcal{P}$, defined by eq. (8), satisfies $\mathcal{P} = \mathbb{K}^{d \times 1} \setminus V_{\mathcal{I}}(\mathcal{I})$.

Let us consider the finitely presented $\mathcal{R}$-module $\mathcal{B} = \text{coker}_{\mathcal{R}}(B.) = \mathcal{R}^{l \times 1} / (B \mathcal{R}^{r \times 1})$. Note that the $0^{\text{th}}$-Fitting ideal $\text{Fitt}_0(\mathcal{B})$ of $\mathcal{B}$ is the ideal of $\mathcal{R}$ generated by all the $l \times l$ minors of $B$ [10, 23], i.e., $\mathcal{I} = \text{Fitt}_0(\mathcal{B})$. See the forthcoming Definition 1 for the general definition of Fitting ideals. Moreover, if $\text{ann}_{\mathcal{R}}(\mathcal{B}) = \{a \in \mathcal{R} | \forall b \in \mathcal{B}: ab = 0\}$ is the annihilator of $\mathcal{B}$, then we have

$$ \text{ann}_{\mathcal{R}}(\mathcal{B})^l \subseteq \text{Fitt}_0(\mathcal{B}) \subseteq \text{ann}_{\mathcal{R}}(\mathcal{B}) \implies \sqrt{\text{ann}_{\mathcal{R}}(\mathcal{B})} = \sqrt{\text{Fitt}_0(\mathcal{B})}, \quad (11) $$

where $\sqrt{\mathcal{I}} = \{a \in \mathcal{R} | \exists k \in \mathbb{Z}: a^k \in \mathcal{I}\}$ denotes the radical of $\mathcal{I}$. If $\mathbb{K}$ is an algebraically closed field (e.g., $\mathbb{K} = \overline{\mathbb{Q}}$ is the algebraic closure of $\mathbb{Q}$ or $\mathbb{K} = \mathbb{C}$), then $V_{\mathbb{K}}(\mathcal{I}) = V_{\mathbb{K}}(\text{ann}_{\mathcal{R}}(\mathcal{B}))$. For more details, see [10, 23].

**Corollary 1** ([2]). Let $W_1, \dots, W_r \in \mathbb{K}^{l \times d}$ be the matrices defined in Theorem 1, $\mathcal{R} = \mathbb{K}[x_1, \dots, x_d]$, $x = (x_1 \dots x_d)^T$, $B = (W_1 x \dots W_r x) \in \mathcal{R}^{l \times r}$, $\mathcal{B} = \text{coker}_{\mathcal{R}}(B.)$, $\mathcal{I} = \text{Fitt}_0(\mathcal{B})$, and $\text{ann}_{\mathcal{R}}(\mathcal{B})$ the annihilator of the $\mathcal{R}$-module $\mathcal{B}$. Then, the linear cone $\mathcal{P}$, defined in Theorem 1, is the complementary of the algebraic set $V_{\mathbb{K}}(\mathcal{I})$ in the affine space $\mathbb{K}^{d \times 1}$, and thus, $\mathcal{P}$ is a quasi-affine variety. Finally, if $\mathbb{K}$ is an algebraically closed field, then we have $V_{\mathbb{K}}(\mathcal{I}) = V_{\mathbb{K}}(\text{ann}_{\mathcal{R}}(\mathcal{B}))$.

We summarize the above results in Algorithm 1 and illustrate this algorithm with an explicit example.

**Algorithm 1** PreRankFactorizationProblem

1: **procedure** PRERANKFACTORIZATIONPROBLEM($D_1, \dots, D_r \in \mathbb{K}^{m \times m}, 0 \neq M \in \mathbb{K}^{m \times n}$)

2: Compute a basis of $\text{ker}_{\mathbb{K}}(M)$ to get a full row rank matrix $L \in \mathbb{K}^{(m-l) \times m}$ satisfying $\text{ker}_{\mathbb{K}}(M) = \text{im}_{\mathbb{K}}(L)$, where $l = \text{rank}_{\mathbb{K}}(M)$

3: Set the matrix $N \in \mathbb{K}^{p \times r \times m}$ defined by eq. (7) and compute a basis of $\text{ker}_{\mathbb{K}}(N.)$, i.e., a full column rank matrix $Z \in \mathbb{K}^{m \times d}$ such that $\text{ker}_{\mathbb{K}}(N.) = \text{im}_{\mathbb{K}}(Z.)$, where $d = \text{dim}_{\mathbb{K}}(\text{ker}_{\mathbb{K}}(N.))$

4: Compute a basis of $\text{im}_{\mathbb{K}}(M.)$ to get a full column rank matrix $X \in \mathbb{K}^{m \times l}$ satisfying $\text{im}_{\mathbb{K}}(M.) = \text{im}_{\mathbb{K}}(X.)$

5: Factorize $M$ as $M = XY$, where $Y \in \mathbb{K}^{l \times n}$

6: For $i = 1, \dots, r$, compute the unique matrix $W_i \in \mathbb{K}^{l \times d}$ satisfying $D_i Z = X W_i$

7: Define $\mathcal{R} = \mathbb{K}[x_1, \dots, x_d]$, $x = (x_1 \dots x_d)^T$, $B = (W_1 x \dots W_r x) \in \mathcal{R}^{l \times r}$, and $\mathcal{I} = \text{Fitt}_0(\mathcal{B})$ the ideal of $\mathcal{R}$ generated by all the $l \times l$ minors of $B$

8: **return** $Z$, $Y$, $\mathcal{I}$, $\mathcal{R}$, and $B$ which are such that eq. (10) defines solutions of eq. (4) satisfying Conditions 1 and 2 of Lemma 1 for all $\psi \notin V_{\mathbb{K}}(\mathcal{I})$ and for all $Y' \in \mathbb{K}^{(r-l) \times n}$ (where $E_\psi \in \mathbb{K}^{r \times l}$ is a right inverse of $B(\psi) = (W_1 \psi \dots W_r \psi)$ and the columns of $C_\psi \in \mathbb{K}^{r \times (r-l)}$ define a basis of $\text{ker}_{\mathbb{K}}(B(\psi).)$)

9: **end procedure**

**Example 1.** Let us consider the following matrices:

$$ D_1 = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & -1 \end{pmatrix}, \quad D_2 = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix}, \quad D_3 = \begin{pmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ -1 & 0 & 0 & 0 \end{pmatrix}, $$

$$ D_4 = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & -1 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix}, \quad M = \begin{pmatrix} 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \end{pmatrix}. $$
Then, we have $m = n = r = 4$. We can easily check that $l = \mathrm{rank}_\mathbb{K}(M) = 1$ and:

$$L = \begin{pmatrix} 1 & 0 & 0 & -1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix}, \quad Z = \begin{pmatrix} -1 \\ 0 \\ 0 \\ 1 \end{pmatrix}, \quad X = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 1 \end{pmatrix}, \quad Y = \begin{pmatrix} 1 & 0 & 0 & 1 \end{pmatrix}, \\ W_1 = -1, \quad W_2 = 0, \quad W_3 = 1, \quad W_4 = 0.$$

Hence, we have $d = 1$, $\psi = \psi_1 \in \mathbb{K}$, $\mathcal{R} = \mathbb{K}[x_1]$, and $B = (-x_1 \ 0 \ x_1 \ 0) \in \mathcal{R}^{1 \times 4}$. Considering the $\mathcal{R}$-module $\mathcal{B} = \mathcal{R}/(B\mathcal{R}^{4 \times 1}) = \mathcal{R}/\mathcal{I}$, where $\mathcal{I} = \mathrm{Fitt}_0(\mathcal{B}) = \mathrm{ann}_{\mathcal{R}}(\mathcal{B}) = \langle x_1 \rangle_{\mathcal{R}}$ denotes the principal ideal of $\mathcal{R}$ generated by $x_1$, $\mathcal{V}_{\mathbb{K}}(\mathcal{I}) = \{0\}$, and $\mathcal{P} = \mathbb{K} \setminus \{0\}$. If we set $W = (-1 \ 0 \ 1 \ 0)$, then $B = x_1 W$, $F = 1/2(-1 \ 0 \ 1 \ 0)^T$ is a right inverse of $W$, and thus, for $\psi \in \mathcal{P}$, $E_\psi = \psi_1^{-1}F$ is a right inverse of the matrix $B(\psi)$. Computing a basis of $\mathrm{ker}_{\mathbb{K}}(W)$, we get $\mathrm{ker}_{\mathbb{K}}(W) = \mathrm{im}_{\mathbb{K}}(C)$, where $C$ is defined by

$$C = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} \in \mathbb{K}^{4 \times 3}, \qquad (12)$$

and thus, we have $\mathrm{ker}_{\mathbb{K}}(B(\psi)) = \mathrm{im}_{\mathbb{K}}(C)$ for all $\psi \in \mathcal{P}$. Then, eq. (10) defines solutions of eq. (4), i.e.:

$$\forall \psi \in \mathbb{K} \setminus \{0\}, \quad \forall Y' \in \mathbb{K}^{3 \times 4}, \quad \left\{ \begin{array}{l} u = Z \psi = (-\psi \ 0 \ 0 \ \psi)^T, \\ v = \frac{1}{2\psi} \begin{pmatrix} -1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix} + \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} Y'. \end{array} \right. \qquad (13)$$

Finally, all the solutions $(u, v)$ of eq. (4) with full row rank matrices $v$ can be written as eq. (13) for all $Y' \in \mathbb{K}^{3 \times 4}$ satisfying the condition $\det((Y^T \ Y'^T)^T) \neq 0$.

Let us state a few comments on Theorem 1 and Corollary 1. Let us suppose that $\mathcal{I} \neq \langle 0 \rangle$ and $g_1, \dots, g_t$ are homogeneous polynomials that generate the ideal $\mathcal{I}$, i.e., $\mathcal{I} = \langle g_1, \dots, g_t \rangle_{\mathcal{R}}$. If $D(g_i) = \{\psi \in \mathbb{K}^{d \times 1} | g_i(\psi) \neq 0\}$ denotes the distinguished open Zariski set defined by $g_i$ [10, 20], then we have $\mathcal{P} = \mathbb{K}^{d \times 1} \setminus \mathcal{V}_{\mathbb{K}}(\langle g_1, \dots, g_t \rangle) = \bigcup_{i=1}^t D(g_i)$. For instance, if $l = r$, then $B \in \mathcal{R}^{l \times l}$, and thus, $g_1 = \det(B)$, $t = 1$, and $\mathcal{P} = D(g_1)$. For every $\psi \in D(g_i)$, eq. (10) characterizes a set of solutions of eq. (4) satisfying Conditions 1 and 2 of Lemma 1, where $E_\psi$ is a right inverse of the matrix $B(\psi) \in \mathbb{K}^{l \times r}$ and $C_\psi \in \mathbb{K}^{r \times (r-l)}$ is a matrix whose columns define a basis of $\mathrm{ker}_{\mathbb{K}}(B(\psi))$. Note that this set of solutions is defined only for the points $\psi$ in $D(g_i)$, and thus, it is only a local solution. Moreover, this set of solutions varies with $\psi \in D(g_i)$ because the matrices $E_\psi$ and $C_\psi$ change with $\psi$ in $D(g_i)$. Using effective module theory (see, e.g., [1, 6, 12]), in [2], it is shown how to “glue” these local solutions together to get a global solution on the whole open set $D(g_i)$ of $\mathbb{K}^d$, namely, to get a regular closed-form solution on $D(g_i)$. To do that, we use the existence of a right inverse $E_{g_i} \in \mathcal{R}_{g_i}^{l \times r}$ of $B$, where $\mathcal{R}_{g_i} = \{a/g_i^k | a \in \mathcal{R}, k \in \mathbb{Z}_{\ge 0}\}$ denotes the localization of the integral domain $\mathcal{R}$ at the multiplicatively closed set $\{g_i^k\}_{k \in \mathbb{Z}_{\ge 0}}$ [10], and the existence of a matrix $C_{g_i} \in \mathcal{R}_{g_i}^{r \times s_i}$, where $s_i \ge r-l$, whose columns generate the $\mathcal{R}_{g_i}$-module $\mathrm{ker}_{\mathcal{R}_{g_i}}(B)$, i.e., satisfying $\mathrm{ker}_{\mathcal{R}_{g_i}}(B) = \mathrm{im}_{\mathcal{R}_{g_i}}(C_{g_i}(\psi))$. We then have $\mathrm{ker}_{\mathbb{K}}(B(\psi)) = \mathrm{im}_{\mathbb{K}}(C_{g_i}(\psi))$ for all $\psi \in D(g_i)$.

**Remark 6.** The matrices $E_{g_i}$ and $C_{g_i}$ can be computed using methods of computer algebra [2, 5]. For more details, see Remark 9 in the next section. For instance, they can be computed using the OREMODULES package [6], the CapAndHomalg library [1], and the Singular system [12].

In Algorithm 2, we sum up the computation of the set of all the solutions of eq. (4) satisfying Conditions 1 and 2 of Lemma 1.

**Remark 7.** The fact that $s_i \ge r-l$, where $r-l = \mathrm{dim}_{\mathbb{K}}(\mathrm{ker}_{\mathbb{K}}(B(\psi)))$ for $\psi \in D(g_i)$ comes from the fact that the identity $\mathrm{ker}_{\mathbb{K}}(B(\psi)) = \mathrm{im}_{\mathbb{K}}(C_{g_i}(\psi))$ holds for all $\psi \in D(g_i)$ and not only for a particular $\psi \in D(g_i)$. More generators than $r-l$ is usually needed for generating the $\mathcal{R}_{g_i}$-module $\mathrm{ker}_{\mathcal{R}_{g_i}}(B)$. We have $s_i = r-l$ when $\mathrm{ker}_{\mathcal{R}_{g_i}}(B)$ is a free $\mathcal{R}_{g_i}$-module.
**Algorithm 2 RankFactorizationProblemWithConditions**

1: **procedure** RANKFACTORIZATIONPROBLEMWITHCONDs(D₁, ..., Dₜ ∈ K^{m×m}, M ∈ K^{m×n})

2: PRE RANKFACTORIZATIONPROBLEM(D₁, ..., Dₜ, M) = {Z, Y, I, R, B}

3: Let {$g_i$}$_{i=1,...,t}$ be a set of generators of I, i.e., $I = \langle g_1, ..., g_t \rangle_R$

4: For i = 1, ..., t, compute a right inverse $E_{g_i} \in \mathcal{R}_{g_i}^{l \times r}$ of B

5: For i = 1, ..., t, compute a matrix $C_{g_i} \in \mathcal{R}_{g_i}^{r \times s_i}$ satisfying $\ker_{\mathcal{R}_{g_i}}(B.) = \text{im}_{\mathcal{R}_{g_i}}(C_{g_i}.)$

6: **return** Z, $\mathcal{I} = \langle g_1, ..., g_t \rangle$, {($E_{g_i}$, $C_{g_i}$)}$_{i=1,...,t}$, which are such that

$$ \forall \psi \in D(g_i), \forall Y' \in K^{s_i \times m}, \left\{ \begin{array}{l} u = Z \psi, \\ v = (E_{g_i}(\psi) \quad C_{g_i}(\psi)) \begin{pmatrix} Y \\ Y' \end{pmatrix}, \end{array} \right. \quad (14) $$

is a regular solution of eq. (4) on $D(g_i)$ satisfying Conditions 1 and 2 of Lemma 1, where $E_{g_i}(\psi)$ (resp., $C_{g_i}(\psi)$) denotes the evaluation of the matrix $E_{g_i}$ (resp., $C_{g_i}$) at the point $x = \psi$

7: **end procedure**

In [2], it is shown that the $\mathcal{R}_{g_i}$-module $\ker_{\mathcal{R}_{g_i}}(B.)$ is stably free of rank $r-l$, i.e., locally free [10, 25]. Hence, the study of these regular closed-form solutions on each $D(g_i)$ advocates for the study of the following well-known difficult problems in module theory:

1. Recognizing whether or not a finitely generated stably free $\mathcal{R}_{g_i}$-module is free.

2. Effective computation of bases of finitely generated free $\mathcal{R}_{g_i}$-modules (i.e., study possible effective extensions of the well-known Quillen-Suslin theorem) [10, 11, 25].

3. Effective computation of a minimal set of generators for $\mathcal{I} = \text{Fitt}_0(B)$ [10].

Points 1 and 2 are related to the possibility of considering $s_i = r-l$ in eq. (14). For instance, the first two points can be effectively solved in the following particular cases:

* $g_i \in K \setminus \{0\}$, i.e., $\mathcal{R}_{g_i} = \mathcal{R}$, by an effective version of the Quillen-Suslin theorem [10, 11].

* $g_i = x_i$ by an extension of the Quillen-Suslin theorem to generalized Laurent polynomial ring. See [11] and the references therein.

* $r = l + 1$ since a stably free module of rank 1 over a commutative ring is free [10, 11].

* $d = 1$ because $\mathcal{R} = K[x_1]$ is a principal ideal domain and stably free $\mathcal{R}$-modules (e.g., $\ker_{\mathcal{R}}(B.)$) are free [25]. Bases of free $\mathcal{R}$-modules can then be computed using Smith normal forms [11].

* $d = 2$ because $\ker_{\mathcal{R}}(B.)$ is then a projective $\mathcal{R} = K[x_1, x_2]$-module [10, 25], and thus, a free $\mathcal{R}$-module by the Quillen-Suslin theorem [10, 11, 25].

Point 3 is related to finding a minimal cover of $\mathcal{P} = \bigcup_{i=1}^l D(g_i)$ by distinguished open sets $D(g_i)$, i.e., to find a representation of the global solution space eq. (10) using a minimal number of regular closed-form solutions on distinguished open sets $D(g_i)$. We have the following facts:

* If $\mu(\mathcal{I})$ denotes the number of elements of a minimal set of generators of $\mathcal{I}$, then we know that $\mu(\mathcal{I}) = \mu(\mathcal{I}/\mathcal{I}^2)$, where $\mathcal{I}/\mathcal{I}^2$ is the so-called conormal $\mathcal{R}/\mathcal{I}$-module [2].

* $d = 1$ since $\mathcal{R} = K[x_1]$ is principal and $\mathcal{I}$ can then be generated by an element of $\mathcal{R}$. For instance, in Example 1, eq. (12) is the unique regular solution on $\mathcal{P} = D(x_1)$.

For more details, we refer the interested reader to [2].

## 3 General solutions

The goal of this section is to extend the approach of Section 2 to characterize the general solutions of the rank factorization problem eq. (4). In other words, we shall not assume Conditions 1 and 2 of Lemma 1 anymore. We shall use standard results of module theory and homological algebra [10, 12, 25].
## 3.1 Case of a full row rank matrix M

In this section, we focus on the case of a matrix M with full row rank.

**Lemma 4.** Let $M \in \mathbb{K}^{m \times n}$ be a full row rank matrix, i.e., $\ker_{\mathbb{K}}(M) = 0$, $D_1, \dots, D_r \in \mathbb{K}^{m \times m}$, and for $u \in \mathbb{K}^{m \times 1}$, $A(u) = (D_1 u \dots D_r u) \in \mathbb{K}^{m \times r}$.

1. The rank factorization problem eq. (4) has a solution if and only if the following linear cone

$$ \mathcal{U} = \{u \in \mathbb{K}^{m \times 1} \mid \mathrm{rank}_{\mathbb{K}}(A(u)) = m\} \qquad (15) $$

of $\mathbb{K}^{m \times 1}$ is not empty.

2. If $\mathcal{U} \neq \emptyset$, then for every $u \in \mathcal{U}$, all the solutions of the inhomogeneous linear system $A(u)v = M$ in $v \in \mathbb{K}^{r \times n}$ are then defined by $V_u = \{F_u M + C_u Y' \mid Y' \in \mathbb{K}^{(m-r) \times n}\}$, where $F_u \in \mathbb{K}^{r \times m}$ is a right inverse of $A(u)$ and the columns of the matrix $C_u \in \mathbb{K}^{r \times (m-r)}$ define a basis of $\ker_{\mathbb{K}}(A(u))$, i.e., $\ker_{\mathbb{K}}(A(u)) = \mathrm{im}_{\mathbb{K}}(C_u)$.

*Proof.* 1. M having full row rank, i.e., $\mathrm{im}_{\mathbb{K}}(M) = \mathbb{K}^{m \times 1}$, we have $m \le n$ and there exists $N \in \mathbb{K}^{n \times m}$ such that $MN = I_m$. Now, eq. (4) yields $A(u)(vN) = I_m$, which shows that $A(u)$ has full row rank and $m \le r$, i.e., $u \in \mathcal{U}$. Conversely, if there exists $u \in \mathbb{K}^{m \times 1}$ such that $A(u) \in \mathbb{K}^{m \times r}$ has full row rank, then there exists $F_u \in \mathbb{K}^{r \times m}$ such that $A(u)F_u = I_m$, which yields $A(u)(F_u M) = M$ and eq. (4) has a solution. Thus, eq. (4) is solvable if and only if $\mathcal{U} \neq \emptyset$. Finally, we have $\mathrm{rank}_{\mathbb{K}}(A(\lambda u)) = \mathrm{rank}_{\mathbb{K}}(A(u))$ for all $\lambda \in \mathbb{K} \setminus \{0\}$, i.e., $\mathcal{U}$ is a linear cone.

2. If $\mathcal{U} \neq \emptyset$, then the set of all the solutions of the inhomogeneous linear system $A(u)v = M$ in $v \in \mathbb{K}^{m \times 1}$ is clearly defined by $V_u$, where $E_u$ is a right inverse of $A(u)$ and the columns of the matrix $C_u$ defines a basis of $\ker_{\mathbb{K}}(A(u))$. $\square$

**Remark 8.** If M has full row rank, following the approach of Section 2.2 and using Remark 4, we have $u = \psi \in \mathbb{K}^{m \times 1}$, $B(\psi) = A(u)$, and $\mathcal{U} = \mathcal{P}$.

**Proposition 1.** Let $M \in \mathbb{K}^{m \times n}$ be a full row rank matrix and $D_1, \dots, D_r \in \mathbb{K}^{m \times m}$. Set $\mathcal{R} = \mathbb{K}[x_1, \dots, x_m]$, $x = (x_1 \dots x_m)^T$, $A = (D_1 x \dots D_r x) \in \mathcal{R}^{m \times r}$, $\mathcal{A} = \mathrm{coker}_{\mathcal{R}}(A.) = \mathcal{R}^{m \times 1}/(A \mathcal{R}^{r \times 1})$, and $\mathcal{I} = \mathrm{Fitt}_0(\mathcal{A})$ the ideal of $\mathcal{R}$ generated by all the $m \times m$ minors of the matrix A. Then, we have:

1. $\mathcal{U}$ is a quasi-affine variety of $\mathbb{K}^{m \times 1}$ defined by $\mathcal{U} = \mathbb{K}^{m \times 1} \setminus \mathcal{V}_{\mathbb{K}}(\mathcal{I})$.

2. If $\mathbb{K}$ is an algebraically closed field, then the rank factorization problem eq. (4) has a solution if and only if $\mathcal{I} \neq \langle 0 \rangle$.

3. Let us suppose that $\mathcal{I} \neq \langle 0 \rangle$ and let $h_1, \dots, h_s \in \mathcal{R} \setminus \{0\}$ be such that $\mathcal{I} = \langle h_1, \dots, h_s \rangle$. Then, $\mathcal{U} = \bigcup_{i=1}^s D(h_i)$, i.e., $\{D(h_i)\}_{i=1,\dots,s}$ is a cover of $\mathcal{U}$ by distinguished open subsets of $\mathbb{K}^{m \times 1}$.

4. For $i = 1, \dots, s$, if $\mathcal{R}_{h_i} = \{a/h_i^k \mid a \in \mathcal{R}, k \in \mathbb{Z}_{\ge 0}\}$ denotes the localization of the polynomial ring $\mathcal{R}$ at the multiplicatively closed set $\{h_i^k\}_{k \in \mathbb{Z}}$, then there exists a right inverse $F_{h_i} \in \mathcal{R}_{h_i}^{r \times m}$ of A, i.e., $AF_{h_i} = I_m$.

5. For $i = 1, \dots, s$, there exists a matrix $C_{h_i} \in \mathcal{R}_{h_i}^{r \times t_i}$ whose columns generate the $\mathcal{R}_{h_i}$-module $\ker_{\mathcal{R}_{h_i}}(A.)$, i.e., which is such that $\ker_{\mathcal{R}_{h_i}}(A.) = \mathrm{im}_{\mathcal{R}_{h_i}}(C_{h_i}.)$.

*Proof.* 1 is a direct consequence of eq. (15).

2. Using Point 1, eq. (4) has a solution if and only if $\mathcal{V}_{\mathbb{K}}(\mathcal{I}) \neq \mathbb{K}^{m \times 1}$, i.e., under the hypothesis that $\mathbb{K}$ is an algebraically closed field, if and only if $\mathcal{I} \neq \langle 0 \rangle$.

3. Let $h_1, \dots, h_s \in \mathcal{R} \setminus \{0\}$ be such that $\mathcal{I} = \langle h_1, \dots, h_s \rangle$. Then, we have $\mathcal{U} = \bigcup_{i=1}^s D(h_i)$, i.e., $\{D(h_i)\}_{i=1,\dots,s}$ is a cover of $\mathcal{U}$ by distinguished open subsets of $\mathbb{K}^{m \times 1}$.

4. If $u \in D(h_i) = \{\psi \in \mathbb{K}^{m \times 1} \mid h_i(\psi) \neq 0\}$, then we have $\mathrm{rank}_{\mathbb{K}}(A(u)) = m$, which shows that there exists a right inverse $F_{h_i} \in \mathbb{K}^{r \times m}$ of $A(u)$ on $D(h_i)$. More generally, to prove the existence of a right inverse of $A(u)$ which is globally well-defined in $D(h_i)$ (and not only at the point $u \in D(h_i)$), we first note that $\mathrm{ann}_{\mathcal{R}}(\mathcal{A})^m \subseteq \mathrm{Fitt}_0(\mathcal{A}) \subseteq \mathrm{ann}_{\mathcal{R}}(\mathcal{A})$ (see, e.g., [10, 20]). Thus, we have $h_i \mathcal{A} = 0$, and thus, $S_{h_i}^{-1} \mathcal{A} = 0$,
where $S_{h_i}^{-1} \mathcal{A} = \{m/h_i^k \mid m \in \mathcal{A}, k \in \mathbb{Z}\}$ is the localization of $\mathcal{A}$ at $S_{h_i}$ (see, e.g., [10, 20, 25]), i.e., we have $A \mathcal{R}_{h_i}^{r \times 1} = \mathcal{R}_{h_i}^{m \times 1}$, which shows the existence of a right inverse $F_{h_i} \in \mathcal{R}_{h_i}^{r \times m}$ of $A$, i.e., $AF_{h_i} = I_m$.

5. Since $\mathcal{R}_{h_i}$ is a noetherian ring (see, e.g., [10, 20, 25]), $\ker_{\mathcal{R}_{h_i}}(A.)$ is a finitely generated $\mathcal{R}_{h_i}$-module, and thus, there exists $C_{h_i} \in \mathcal{R}_{h_i}^{r \times t_i}$ which satisfies $\ker_{\mathcal{R}_{h_i}}(A.) = \mathrm{im}_{\mathcal{R}_{h_i}}(C_{h_i}).$ $\square$

Recall that if $P$ is a matrix whose entries are functions of the vector variable $x = (x_1 \dots x_m)^T$, then $P(u)$ denotes the evaluation of $P$ at the point $u = (u_1 \dots u_m) \in \mathbb{K}^{m \times 1}$.

**Theorem 2.** Let $M \in \mathbb{K}^{m \times n}$ be a full row rank matrix and $D_1, \dots, D_r \in \mathbb{K}^{m \times m}$. Set $\mathcal{R} = \mathbb{K}[x_1, \dots, x_m]$, $x = (x_1 \dots x_m)^T$, $A = (D_1 x \dots D_r x) \in \mathcal{R}^{m \times r}$, $A = \mathrm{coker}_{\mathcal{R}}(A.) = \mathcal{R}^{m \times 1}/(A \mathcal{R}^{r \times 1})$, and $\mathcal{I} = \mathrm{Fitt}_0(\mathcal{A})$ the ideal of $\mathcal{R}$ defined by all the $m \times m$ minors of the matrix $A$.

Let us suppose that $\mathcal{I} \neq \langle 0 \rangle$ and let $h_1, \dots, h_s \in \mathcal{R} \setminus \{0\}$ be such that $\mathcal{I} = \langle h_1, \dots, h_s \rangle$.

With the notations of 3 and 4 of Proposition 1, all the solutions of the rank factorization problem eq. (4) with $u \in D(h_i) = \{\psi \in \mathbb{K}^{m \times 1} \mid h_i(\psi) \neq 0\}$ are then defined by:

$$ \left\{ \begin{array}{ll} u \in D(h_i), & i = 1, \dots, s. \\ v(u, Y') = F_{h_i}(u) M + C_{h_i}(u) Y', & \forall Y' \in \mathbb{K}^{t \times n}, \end{array} \right. \qquad (16) $$

Finally, for $u \in \mathcal{U} = \bigcup_{i=1}^s D(h_i)$, there exists $i \in \{1, \dots, s\}$ such that $u \in D(h_i)$ and eq. (16) defines the set of all the solutions of eq. (4) in $D(h_i)$.

*Proof.* Using Proposition 1, we have $\mathcal{U} = \bigcup_{i=1}^s D(h_i)$ and there exist $F_{h_i} \in \mathcal{R}_{h_i}^{r \times m}$ and $C_{h_i} \in \mathcal{R}_{h_i}^{r \times t}$ such that $AF_{h_i} = I_m$ and $\ker_{\mathcal{R}_{h_i}}(A.) = \mathrm{im}_{\mathcal{R}_{h_i}}(C_{h_i}).$ for $i = 1, \dots, s$. Then, we get

$$ \forall u \in D(h_i), \quad \forall Y' \in \mathbb{K}^{t \times n}, \quad A(u) (F_{h_i}(u) M + C_{h_i}(u) Y') = (A(F_{h_i} M + C_{h_i} Y'))(u) = M, $$

which shows that eq. (16) are solutions of eq. (4) with $u \in D(h_i)$.

Let $(u, v)$ be a solution of eq. (4) with $u \in D(h_i)$. Then, $v - F_{h_i}(u) M$ satisfies $A(u) (v - F_{h_i}(u) M) = 0$, i.e., $v - F_{h_i}(u) M \in \ker_{\mathbb{K}}(A(u).)$. Evaluating the identity $A C_{h_i} = 0$ at $u$, we get $A(u) C_{h_i}(u) = 0$, i.e., $\mathrm{im}_{\mathbb{K}}(C_{h_i}(u).) \subseteq \ker_{\mathbb{K}}(A(u).)$. Let us prove the reverse inclusion. Applying the exact covariant functor $\mathcal{R}_{h_i} \otimes_{\mathcal{R}} \cdot$ (since $\mathcal{R}_{h_i}$ is a flat $\mathcal{R}$-module; see, e.g., [10, 25]) to the following exact sequence of $\mathcal{R}$-modules defining a finite presentation of $\mathcal{A}$

$$ \mathcal{R}^{r \times 1} \xrightarrow{A.} \mathcal{R}^{m \times 1} \xrightarrow{\sigma} \mathcal{A} \longrightarrow 0, $$

we obtain the following split exact sequence of $\mathcal{R}_{h_i}$-modules (see, e.g., [10, 25]):

$$ \mathcal{R}_{h_i}^{t_i \times 1} \xrightarrow{C_{h_i}} \mathcal{R}_{h_i}^{r \times 1} \xrightarrow{A.} \mathcal{R}_{h_i}^{m \times 1} \xrightarrow{\mathrm{id} \otimes \sigma} S_{h_i}^{-1} \mathcal{A} = 0. \qquad (17) $$

Setting $\Pi = I_r - F_{h_i} A \in \mathcal{R}_{h_i}^{r \times r}$ and using the identity $AF_{h_i} = I_m$, we obtain $A\Pi = 0$, i.e., we have $\mathrm{im}_{\mathcal{R}_{h_i}}(\Pi.) \subseteq \ker_{\mathcal{R}_{h_i}}(A.) = \mathrm{im}_{\mathcal{R}_{h_i}}(C_{h_i}),$ which proves the existence of $G_{h_i} \in \mathcal{R}_{h_i}^{t_i \times r}$ such that $\Pi = C_{h_i} G_{h_i}$, i.e., $C_{h_i} G_{h_i} + F_{h_i} A = I_r$. Evaluating this identity at $u$, we then obtain $C_{h_i}(u) G_{h_i}(u) + F_{h_i}(u) A(u) = I_r$. Now, if $\xi \in \ker_{\mathbb{K}}(A(u).)$, this last identity implies the identity $\xi = C_{h_i}(u) (G_{h_i}(u) \xi)$, which shows $\ker_{\mathbb{K}}(A(u).) \subseteq \mathrm{im}_{\mathbb{K}}(C_{h_i}(u).)$ and proves that $\ker_{\mathbb{K}}(A(u).) = \mathrm{im}_{\mathbb{K}}(C_{h_i}(u).)$. We then have $v - F_{h_i}(u) M \in \mathrm{im}_{\mathbb{K}}(C_{h_i}(u).)$, and thus, there exists $Y' \in \mathbb{K}^{t_i \times n}$ such that $v - F_{h_i}(u) M = C_{h_i}(u) Y'$, which proves that $(u, v)$ is of the form of eq. (16) with $u \in D(h_i)$, i.e., all the solutions of eq. (4) with $u \in D(h_i)$ are defined by eq. (16).

Finally, let $(u, v)$ be a solution of eq. (4). By 1 of Lemma 4, $u \in \mathcal{U} \neq \emptyset$, i.e., by 3 of Proposition 1, $u \in \mathcal{U} = \bigcup_{i=1}^s D(h_i)$. Then, there exists $i \in \{1, \dots, s\}$ such that $u \in D(h_i)$ and the last result holds. $\square$

**Remark 9.** A matrix $F_{h_i} \in \mathcal{R}_{h_i}^{r \times m}$ satisfying $AF_{h_i} = I_m$ can be computed as follows: $h_i A = 0$ (see the proof of 4 of Proposition 1), where $A = \mathcal{R}^{m \times 1}/(A \mathcal{R}^{r \times 1})$, yields the identity $h_i I_m = A G_{h_i}$ for a certain $G_{h_i} \in \mathcal{R}^{r \times m}$, and thus, $F_{h_i} = h_i^{-1} G_{h_i} \in \mathcal{R}_{h_i}^{r \times m}$. A matrix $G_{h_i}$ can be obtained using a factorization problem (see, e.g., [6]), i.e., by solving a standard membership problem in $\mathcal{R}^{m \times 1}$, where
$\mathcal{R} = \mathbb{K}[x_1, \dots, x_m]$. This matrix can be computed by, for instance, the `LocalLeftInverse` command of the `OREMODULES` package [6] or the `PreInverse` command of the `CapAndHomalg` library [1].

To compute a matrix $C_{h_i}$ satisfying $\ker_{\mathcal{R}_{h_i}}(A.) = \text{im}_{\mathcal{R}_{h_i}}(C_{h_i.})$, we can first compute $\ker_{\mathcal{R}}(A.)$ to get $C \in \mathcal{R}^{r \times t}$ such that $\ker_{\mathcal{R}}(A.) = \text{im}_{\mathcal{R}}(C.)$ (see, e.g., [5]). Then, the application of the exact functor $\mathcal{R}_{h_i} \otimes_{\mathcal{R}} \cdot$ to the exact sequence of $\mathcal{R}$-modules $\mathcal{R}^{t \times 1} \xrightarrow{C.} \mathcal{R}^{r \times 1} \xrightarrow{A.} \mathcal{R}^{m \times 1}$ yields the exact sequence of $\mathcal{R}_{h_i}$-modules $\mathcal{R}_{h_i}^{t \times 1} \xrightarrow{C.} \mathcal{R}_{h_i}^{r \times 1} \xrightarrow{A.} \mathcal{R}_{h_i}^{m \times 1}$. Thus, we have $\ker_{\mathcal{R}_{h_i}}(A.) = \text{im}_{\mathcal{R}_{h_i}}(C.)$, which shows that we can take $C_{h_i} = C$. Note that $t_i = t$. Finally, to reduce $t_i$, we can follow the next approach.

Considering $\mathcal{R}[y] = \mathbb{K}[x_1, \dots, x_m, y]$ and denoting by $\langle y h_i - 1 \rangle$ the ideal of $\mathcal{R}[y]$ generated by $y h_i - 1$, we then have $\mathcal{R}_{h_i} = \mathcal{R}[y]/\langle y h_i - 1 \rangle$. The following exact sequence of $\mathcal{R}[y]$-modules

$$0 \longrightarrow \mathcal{R}[y] \xrightarrow{\langle y h_i - 1 \rangle} \mathcal{R}[y] \xrightarrow{\vartheta} \mathcal{R}_{h_i} \longrightarrow 0$$

combined with eq. (17) seen as an exact sequence of $\mathcal{R}[y]$-modules, yields the commutative exact diagram of $\mathcal{R}[y]$-modules:

<figure><img src="image_4.png" /></figure>

Computing $\ker_{\mathcal{R}[y]}((A \ (y h_i - 1) I_m).)$, we obtain $U \in \mathcal{R}[y]^{r \times t}$ and $V \in \mathcal{R}[y]^{m \times t}$ such that:

$$\ker_{\mathcal{R}[y]}((A \ (y h_i - 1) I_m).) = \text{im}_{\mathcal{R}[y]}\left(\begin{pmatrix} U \\ V \end{pmatrix}\right).$$

Now, 1 of Proposition 3.1 of [7] yields $\ker_{\mathcal{R}_{h_i}}(A.) = \text{im}_{\mathcal{R}[y]}(U.)/\text{im}_{\mathcal{R}[y]}((y h_i - 1) I_r.) = \text{im}_{\mathcal{R}_{h_i}}(C_{h_i.})$, where $C_{h_i}$ is the matrix obtained by setting $y h_i$ to 1 (which corresponds to substituting $y$ by $h_i^{-1}$) in $U$. A matrix $U$ can be computed by using, e.g., the `SyzygyModule` command of `OREMODULES` or the `WeakKernelEmbedding` command of `CapAndHomalg`.

The different computations are implemented in the `RANKFACTORIZATION` package [9].

**Example 2.** Let us consider the following matrices:

$$M = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \quad D_1 = \begin{pmatrix} -1 & -2 \\ 1 & 2 \end{pmatrix}, \quad D_2 = \begin{pmatrix} -3 & -4 \\ 3 & 4 \end{pmatrix}.$$

Then, we have $m = n = r = 2$, $x = (x_1 \ x_2)^T$, and:

$$A = \begin{pmatrix} -x_1 - 2x_2 & -3x_1 - 4x_2 \\ x_1 + 2x_2 & 3x_1 + 4x_2 \end{pmatrix} \implies \det(A) = 0 \implies \mathcal{I} = \langle 0 \rangle \implies \mathcal{U} = \emptyset.$$

Hence, the corresponding rank factorization problem eq. (4) has no solutions.

**Example 3.** Let us consider the following matrices:

$$M = \begin{pmatrix} 15 & 14 & 13 \\ 24 & 20 & 16 \end{pmatrix}, \quad D_1 = \begin{pmatrix} 1 & -1 \\ 1 & 1 \end{pmatrix}, \quad D_2 = \begin{pmatrix} 1 & 2 \\ -1 & 2 \end{pmatrix}, \quad D_3 = \begin{pmatrix} 1 & 3 \\ 4 & 3 \end{pmatrix}.$$

Then, we have $l = \text{rank}_{\mathbb{K}}(M) = 2 = m < r = 3 = n$. In particular, $M$ has full row rank. Let us consider $\mathcal{R} = \mathbb{K}[x_1, x_2]$ and the $\mathcal{R}$-module $\mathcal{A} = \mathcal{R}^{2 \times 1}/(\mathcal{A} \mathcal{R}^{3 \times 1})$ finitely presented by the following matrix:

$$A = (D_1 x \ D_2 x \ D_3 x) = \begin{pmatrix} 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{pmatrix} \in \mathcal{R}^{2 \times 3}.$$
We can now check that $\mathcal{I} = \text{Fitt}_0(\mathcal{A}) = \langle x_1^2, x_1 x_2, x_2^2 \rangle$. Hence, we have:

$$ \mathcal{U} = \mathbb{K}^{2 \times 1} \setminus \mathcal{V}_{\mathbb{K}}(\mathcal{I}) = D(x_1^2) \cup D(x_1 x_2) \cup D(x_2^2) = \mathbb{K}^{2 \times 1} \setminus \{(0 \ 0)^T\}. $$

Moreover, we have:

$$ F_{x_1^2} = \begin{pmatrix} \frac{66}{97 x_1} & \frac{6}{97 x_1} \\ \frac{38}{97 x_1} + \frac{33 x_2}{97 x_1^2} & -\frac{23}{97 x_1} + \frac{3 x_2}{97 x_1^2} \\ -\frac{7}{97 x_1} - \frac{22 x_2}{97 x_1^2} & \frac{17}{97 x_1} - \frac{2 x_2}{97 x_1^2} \end{pmatrix} \in \mathcal{R}_{x_1^2}^{3 \times 2}, \quad R F_{x_1^2} = I_2, $$

$$ F_{x_1 x_2} = \begin{pmatrix} -\frac{55}{194 x_2} & -\frac{5}{194 x_2} \\ \frac{33}{194 x_2} + \frac{21}{194 x_1} & \frac{3}{194 x_2} - \frac{51}{194 x_1} \\ \frac{11}{97 x_2} - \frac{7}{97 x_1} & \frac{1}{97 x_2} + \frac{17}{97 x_1} \end{pmatrix} \in \mathcal{R}_{x_1 x_2}^{3 \times 2}, \quad R F_{x_1 x_2} = I_2, $$

$$ F_{x_2^2} = \begin{pmatrix} -\frac{35 x_1}{388 x_2^2} - \frac{1}{2 x_2} & \frac{85 x_1}{388 x_2^2} + \frac{1}{2 x_2} \\ \frac{21 x_1}{388 x_2^2} + \frac{31}{388 x_2} & -\frac{51 x_1}{388 x_2^2} + \frac{91}{388 x_2} \\ \frac{7 x_1}{194 x_2^2} + \frac{11}{97 x_2} & -\frac{17 x_1}{194 x_2^2} + \frac{1}{97 x_2} \end{pmatrix} \in \mathcal{R}_{x_2^2}^{3 \times 2}, \quad R F_{x_2^2} = I_2. $$

If we note

$$ C = \begin{pmatrix} 5 x_1^2 + 12 x_1 x_2 \\ -3 x_1^2 + 5 x_1 x_2 + 6 x_2^2 \\ -2 x_1^2 - 4 x_2^2 \end{pmatrix} \in \mathcal{R}^{3 \times 1}, $$

then we have $\ker_{\mathcal{R}_h}(A.) = \text{im}_{\mathcal{R}_h}(C.)$ for $h = x_1^2$, $x_1 x_2$, and $x_2^2$, which shows that all the solutions of eq. (4) are of the form of eq. (16):

$$ \left\{ \begin{array}{lll} \forall u \in D(x_1^2), & \forall Y'_{x_1^2} \in \mathbb{K}^{1 \times 3}, & v(u, Y'_{x_1^2}) = F_{x_1^2}(u) M + C(u) Y'_{x_1^2}, \\ \forall u \in D(x_1 x_2), & \forall Y'_{x_1 x_2} \in \mathbb{K}^{1 \times 3}, & v(u, Y'_{x_1 x_2}) = F_{x_1 x_2}(u) M + C(u) Y'_{x_1 x_2}, \\ \forall u \in D(x_2^2), & \forall Y'_{x_2^2} \in \mathbb{K}^{1 \times 3}, & v(u, Y'_{x_2^2}) = F_{x_2^2}(u) M + C(u) Y'_{x_2^2}. \end{array} \right. \quad (18) $$

For $h = x_1^2$, $x_1 x_2$, or $x_2^2$, the determinant of $U_h = (F_h C)$ is 1, i.e., $U_h$ is invertible. Hence, the matrix $v$ defined by eq. (18) has full row rank if and only if so has $(M^T Y_h^{T})^T \in \mathbb{K}^{3 \times 3}$, where $Y_h = (Y'_{h,1} \ Y'_{h,2} \ Y'_{h,3}) \in \mathbb{K}^{1 \times 3}$, i.e., if and only we have $Y'_{h,1} - 2 Y'_{h,2} + Y'_{h,3} \neq 0$.

## 3.2 General case

Let us now consider the case where the matrix $M$ is not full row rank, i.e., $\text{im}_{\mathbb{K}}(M.) \neq \mathbb{K}^{m \times 1}$. Set again $l = \text{rank}_{\mathbb{K}}(M)$ and $p = m - l > 0$. Moreover, let $L \in \mathbb{K}^{p \times m}$ be a full column rank matrix whose rows define a basis of the $\mathbb{K}$-vector space $\text{ker}_{\mathbb{K}}(M.)$, i.e., which satisfies $\text{ker}_{\mathbb{K}}(M.) = \text{im}_{\mathbb{K}}(L)$.

**Remark 10.** Note that the rows of the matrix $L$ define a generating set of compatibility conditions of the inhomogeneous linear system $M \eta = \zeta$, where $\zeta$ is a fixed vector of $\mathbb{K}^{m \times 1}$ and $\eta$ is sought in $\mathbb{K}^{m \times 1}$. Indeed, a necessary (and sufficient) condition on $\zeta$ for the solvability of $M \eta = \zeta$ is defined by $L \zeta = 0$.
### 3.2.1 Necessary conditions on u

Let us suppose that a solution $(u, v)$ of the rank factorization problem eq. (4) exists. If we set $Q(u) = LA(u) \in K^{p \times r}$, then combining $A(u)v = M$ with $LM = 0$, we obtain $Q(u)v = LM = 0$, which shows that all the columns of $v$ belong to $ker_K(Q(u))$. Thus, $u \in K^{m \times 1}$ must necessarily be such that:

$$ker_K(Q(u)) \neq 0.$$

In linear algebra, the rank-nullity theorem yields the index of $Q(u)$. is defined by

$$\dim_K(\ker_K(Q(u))) - \dim_K(\mathrm{coker}_K(Q(u))) = r - p,$$

which yields $\dim_K(\ker_K(Q(u))) \geq r - p$. Thus, we have:

1. If $r > p$, i.e., if the matrix $Q(u)$ is wide, then $ker_K(Q(u)) \neq 0$ for all $u \in K^{m \times 1}$.

2. If $r \leq p$, i.e., if the matrix $Q(u)$ is tall or square, then $ker_K(Q(u))$ can be reduced to 0 for almost all $u \in K^{m \times 1}$. The $u$'s for which $ker_K(Q(u)) \neq 0$ are the common zeros in $K^{m \times 1}$ of all the $r \times r$ minors of the matrix $Q(u) \in K^{p \times r}$.

Let us state again the definition of the Fitting ideals (see, e.g., [10, 23]).

**Definition 1.** Let $\mathcal{R} = K[x_1, \dots, x_m]$, $N \in \mathcal{R}^{s \times r}$, and $\mathcal{N} = \mathcal{R}^{1 \times r}/(\mathcal{R}^{1 \times s} N)$ be the $\mathcal{R}$-module finitely presented by the matrix $N$. The Fitting ideals $\mathrm{Fitt}_i(\mathcal{N})$'s of $\mathcal{N}$ are defined by:

* $\mathrm{Fitt}_i(\mathcal{N})$ is the ideal of $\mathcal{R}$ generated by all the $(r-i) \times (r-i)$ minors of the matrix $N$ for $1 \leq r-i \leq s$,

* $\mathrm{Fitt}_i(\mathcal{N}) = \langle 0 \rangle$ for $s < r-i$,

* $\mathrm{Fitt}_i(\mathcal{N}) = \mathcal{R}$ for $r-i \leq 0$.

We can now state a necessary condition on $u$ for the existence of a solution of eq. (4).

**Lemma 5.** Let $\mathcal{R} = K[x_1, \dots, x_m]$, $x = (x_1 \dots x_m)^T$, $A = (D_1 x \dots D_r x) \in \mathcal{R}^{m \times r}$, $Q = LA \in \mathcal{R}^{p \times r}$. Moreover, let $Q = \mathrm{coker}_{\mathcal{R}}(Q) = \mathcal{R}^{1 \times r}/(\mathcal{R}^{1 \times p} Q)$ be the $\mathcal{R}$-module finitely presented by the matrix $Q$. Equivalently, the $\mathcal{R}$-module $Q$ is defined by the following finite presentation:

$$\mathcal{R}^{1 \times p} \xrightarrow{\cdot, Q} \mathcal{R}^{1 \times r} \xrightarrow{\pi} Q \longrightarrow 0. \qquad (19)$$

A necessary condition for the solvability of eq. (4) is $u \in \mathcal{V}_K(\mathrm{Fitt}_0(Q))$, where $\mathrm{Fitt}_0(Q)$ is either $\langle 0 \rangle$ if $r > m-l$ or the ideal of $\mathcal{R}$ generated by all the $r \times r$ minors of $Q \in \mathcal{R}^{(m-l) \times r}$ if $r \leq m-l$. Finally, $\mathrm{Fitt}_0(Q)$ is either generated by homogeneous polynomials of total degree $r$ or by $0$.

*Proof.* By definition, for $r-p \leq i \leq r-1$, $\mathrm{Fitt}_i(Q)$ is the ideal of $\mathcal{R}$ generated by all the $(r-i) \times (r-i)$ minors of the matrix $Q = (LD_1 x \dots LD_r x)$. Thus, $\mathrm{Fitt}_0(Q)$ is either $\langle 0 \rangle$ if $r > p$, or the ideal generated by all the $r \times r$ minors of $Q \in \mathcal{R}^{p \times r}$ if $r \leq p$. Hence, if $r > p$, then $\mathrm{Fitt}_0(Q) = \langle 0 \rangle$ (which then yields $\mathcal{V}_K(\mathrm{Fitt}_0(Q)) = K^{m \times 1}$) or, if $r \leq p$, $\mathrm{Fitt}_0(Q)$ is generated by homogeneous polynomials of degree $r$ or $0$ if all the $r \times r$ minors of $Q(u)$ are reduced to $0$. Finally, the fact that $ker_K(Q(u)) \neq 0$ is equivalent to $u \in \mathcal{V}_K(\mathrm{Fitt}_0(Q))$ since the rank of the matrix $Q(u)$ is then strictly less than $r$. $\square$

More generally, for $i = 0, \dots, r-1$, if $i < r-m+l$, then $\mathrm{Fitt}_i(Q) = \langle 0 \rangle$, or if $i \geq r-m+l$, $\mathrm{Fitt}_i(Q) = \langle 0 \rangle$ is generated by homogeneous polynomials of degree $r-i$ or by $0$ if all the $(r-i) \times (r-i)$ minors of $Q(u)$ are reduced to $0$. Therefore, $1 \notin \mathrm{Fitt}_i(Q)$ for $i = 0, \dots, r-1$, which shows that $\mathrm{Fitt}_i(Q) \neq \mathcal{R}$ for $i = 0, \dots, r-1$. Finally, we have:

$$\mathcal{V}_K(\mathrm{Fitt}_i(Q)) = \{u \in K^{m \times 1} | \mathrm{rank}_K(Q(u)) < r-i\}, \quad i = 0, \dots, r-1.$$
**Remark 11.** We can easily check again that the following chain of Fitting ideals holds

$$ \langle 0 \rangle \subseteq \mathrm{Fitt}_0(\mathcal{Q}) \subseteq \mathrm{Fitt}_1(\mathcal{Q}) \subseteq \dots \subseteq \mathrm{Fitt}_{r-1}(\mathcal{Q}) \subseteq \mathrm{Fitt}_r(\mathcal{Q}) = \mathcal{R}, \quad (20) $$

(see, e.g., [10, 12, 20]), which yields the following chain of affine algebraic subsets of $\mathbb{K}^{m \times 1}$:

$$ \{0\} \subseteq \mathcal{V}_{\mathbb{K}}(\mathrm{Fitt}_{r-1}(\mathcal{Q})) \subseteq \mathcal{V}_{\mathbb{K}}(\mathrm{Fitt}_{r-2}(\mathcal{Q})) \subseteq \dots \subseteq \mathcal{V}_{\mathbb{K}}(\mathrm{Fitt}_0(\mathcal{Q})) \subseteq \mathcal{V}_{\mathbb{K}}(\langle 0 \rangle) = \mathbb{K}^{m \times 1}. \quad (21) $$

Note that $\mathrm{Fitt}_{r-1}(\mathcal{Q})$ is the ideal generated by all the entries of $Q = (L D_1 x \dots L D_r x)$, and thus, $\mathcal{V}_{\mathbb{K}}(\mathrm{Fitt}_{r-1}(\mathcal{Q})) = \{u \in \mathbb{K}^{m \times 1} | L D_i u = 0, i = 1, \dots, r\}$, i.e., $\mathcal{V}_{\mathbb{K}}(\mathrm{Fitt}_{r-1}(\mathcal{Q})) = \mathrm{ker}_{\mathbb{K}}(N.)$, where $N$ is defined by eq. (7). Therefore, the approach of Section 2 corresponds to the case of $u \in \mathcal{V}_{\mathbb{K}}(\mathrm{Fitt}_{r-1}(\mathcal{Q}))$.

**Example 4.** Let us consider the following matrices:

$$ D_1 = \begin{pmatrix} 0 & 0 & 0 & 2 \\ 3 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 2 \end{pmatrix}, \quad D_2 = \begin{pmatrix} 5 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 5 & 2 & 0 \\ 0 & 3 & 2 & 0 \end{pmatrix}, \quad M = \begin{pmatrix} 30 & 0 & 0 \\ 0 & 0 & 0 \\ 12 & 0 & 0 \\ 12 & 0 & 0 \end{pmatrix}. $$

We then have $m = 4$, $n = 3$, $l = 1 \le r = 2$, and $p = m - l = 3 > r$. Moreover, we get:

$$ L = \begin{pmatrix} 2 & 0 & 0 & -5 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & -1 \end{pmatrix}. $$

Now, set $\mathcal{R} = \mathbb{Q}[x_1, x_2, x_3, x_4]$, $x = (x_1 \dots x_4)^T$,

$$ A = (D_1 x \quad D_2 x) = \begin{pmatrix} 2 x_4 & 5 x_1 + 3 x_2 \\ 3 x_1 + x_4 & 0 \\ 0 & 5 x_2 + 2 x_3 \\ 2 x_4 & 3 x_2 + 2 x_3 \end{pmatrix} \in \mathbb{R}^{4 \times 2}, $$

$$ Q = L A = \begin{pmatrix} -6 x_4 & 10 x_1 - 9 x_2 - 10 x_3 \\ 3 x_1 + x_4 & 0 \\ -2 x_4 & 2 x_2 \end{pmatrix} \in \mathbb{R}^{3 \times 2}, $$

and let $Q = \mathcal{R}^{1 \times 2}/(\mathcal{R}^{1 \times 3} Q)$ be the $\mathcal{R}$-module finitely presented by $Q$. Then, we have:

$$ \mathrm{Fitt}_0(\mathcal{Q}) = \langle (10 x_1 - 9 x_2 - 10 x_3)(3 x_1 + x_4), (2 x_1 - 3 x_2 - 2 x_3) x_4, (3 x_1 + x_4) x_2 \rangle, $$

$$ \mathrm{Fitt}_1(\mathcal{Q}) = \langle x_1, x_2, x_3, x_4 \rangle. $$

A necessary condition for the existence of a solution of Problem eq. (4) is then $u \in \mathcal{V}_{\mathbb{K}}(\mathrm{Fitt}_0(\mathcal{Q}))$. We can check again that $\mathcal{V}_{\mathbb{K}}(\mathrm{Fitt}_0(\mathcal{Q}))$ is defined by $u = (u_1 \ u_2 \ u_1 - 3 u_2/2 \ - 3 u_1)^T$, $u = (u_1 \ 0 \ u_1 \ u_4)^T$, and $u = (0 \ u_2 \ u_3 \ 0)^T$ for all $u_1, u_2, u_3 \in \mathbb{K}$.

Finally, we have $\mathcal{V}_{\mathbb{K}}(\mathrm{Fitt}_1(\mathcal{Q})) = \{(0 \ 0 \ 0 \ 0)^T\} = \mathrm{ker}_{\mathbb{K}}(N.)$, where $N = ((L D_1)^T (L D_2)^T)$, which shows that the approach developed in Section 2 cannot be used to solve Problem eq. (4).

### 3.2.2 Study of the kernel of the matrix $Q$

As explained in Section 3.2.1, we must have $u \in \mathcal{V}_{\mathbb{K}}(\mathrm{Fitt}_0(\mathcal{Q}))$ and $v \in \mathrm{ker}_{\mathbb{K}}(Q(u))$. Hence, we now study the kernel of $Q$. We first set a few notations.

**Definition 2.** We note $\mathcal{J} = \mathrm{Fitt}_0(\mathcal{Q}) = \langle m_i \rangle_{i=1,...,\alpha}$, where, if $r \le p = m - l$, $\{m_i\}_{i=1,...,\alpha}$ is the set of all the $r \times r$ minors of $Q$ and $\alpha = p!/(r!(p-r)!)$, or $\alpha = 1$ and $m_i = 0$, i.e., $\mathcal{J} = \langle 0 \rangle$, else. If $\{e_i\}_{i=1,...,\gamma}$ is another set of generators of $\mathcal{J}$, where $e_i \in \mathcal{R}$ for $i = 1, \dots, \gamma$, then we shall write $\mathcal{J} = \langle e_1, \dots, e_\gamma \rangle_{\mathcal{R}}$.
To algebraically emulate the fact that $u$ belongs to $\mathcal{V}_K(\mathcal{J})$, we can work in the non-trivial factor noetherian ring $S = \mathcal{R}/\mathcal{J}$ of $\mathcal{R}$. Let $\chi : \mathcal{R} \to S$ be the canonical epimorphism of $\mathbb{K}$-algebras which maps $r \in \mathcal{R}$ onto its residue class $\chi(r) \in S$, simply denoted by $\bar{r}$. Note that the ring $S$ inherits a $\mathcal{R}$-module structure defined by $r'\bar{r} := \bar{r}'r = \bar{r}'\bar{r}$ for all $r, r' \in \mathcal{R}$.

For $k \in \mathbb{Z}_{>0}$, we can define the following $\mathcal{R}$-homomorphism:

$$ \begin{gathered} \mathcal{R}^{k \times 1} \to \mathcal{S}^{k \times 1} \\ \eta = (\eta_1 \dots \eta_k)^T \mapsto \bar{\eta} = (\bar{\eta}_1 \dots \bar{\eta}_k)^T. \end{gathered} \qquad (22) $$

More generally, if $C \in \mathcal{R}^{a \times b}$, then we shall use the following notations:

$$ \bar{C} = (\bar{C}_{ij})_{1 \le i \le a, 1 \le j \le b} = (\chi(C_{ij}))_{1 \le i \le a, 1 \le j \le b} = \chi(C) \in \mathcal{S}^{a \times b}. $$

Let $\mathcal{T}(Q) = \text{coker}_{\mathcal{R}}(Q) = \mathcal{R}^{p \times 1}/(Q\mathcal{R}^{r \times 1})$ be the so-called Auslander transpose of $Q = \text{coker}_{\mathcal{R}}(Q)$ [10] (i.e., the $\mathcal{R}$-module finitely presented by the transpose $Q^T$ of $Q$). Applying the right exact covariant functor $\mathcal{S} \otimes_{\mathcal{R}} \cdot$ [10, 25] to the exact sequence of $\mathcal{R}$-modules defining the following presentation of $\mathcal{T}(Q)$

$$ 0 \leftarrow \mathcal{T}(Q) \leftarrow \mathcal{R}^{p \times 1} \leftarrow \mathcal{R}^{r \times 1}, $$

and using $\mathcal{S} \otimes_{\mathcal{R}} \mathcal{R}^{t \times 1} \cong \mathcal{S}^{t \times 1}$, we then obtain the following exact sequence of $\mathcal{S}$-modules

$$ 0 \leftarrow \mathcal{S} \otimes_{\mathcal{R}} \mathcal{T}(Q) \leftarrow \mathcal{S}^{p \times 1} \leftarrow \mathcal{S}^{Q \times 1} \leftarrow \mathcal{S}^{r \times 1}, \qquad (23) $$

where, using both the $\mathcal{R}$-module and the ring structures of $\mathcal{S}$, $Q \in \text{hom}_{\mathcal{S}}(\mathcal{S}^{r \times 1}, \mathcal{S}^{p \times 1})$ is defined by $Q\bar{\eta} := \bar{Q}\bar{\eta} = \bar{Q}\bar{\eta}$ for all $\eta \in \mathcal{R}^{r \times 1}$. Hence, we have $Q = \bar{Q} \in \text{hom}_{\mathcal{S}}(\mathcal{S}^{r \times 1}, \mathcal{S}^{p \times 1})$. See, e.g., [10, 25]. Since $\mathcal{S}$ is a noetherian ring, $\text{ker}_{\mathcal{S}}(\bar{Q})$ is a finitely generated $\mathcal{S}$-module [10, 25]. Thus, if $\text{ker}_{\mathcal{S}}(\bar{Q}) \neq 0$, then there exists $\bar{K} \in \mathcal{S}^{r \times q}$ is such that $\text{ker}_{\mathcal{S}}(\bar{Q}) = \text{im}_{\mathcal{S}}(\bar{K})$.

To prove that $\text{ker}_{\mathcal{S}}(\bar{Q}) \neq 0$ (even when $\text{ker}_{\mathcal{R}}(Q) = 0$), we shall use *McCoy's theorem*.

**Theorem 3** (Theorem 6, p. 63, [23]). Let $Q \in \mathcal{R}^{p \times r}$ and $\mathcal{F}$ a non-zero $\mathcal{R}$-module. A necessary and sufficient for the existence of $0 \neq \eta \in \mathcal{F}^r$ satisfying $Q\eta = 0$ is that there exists a non-zero element $\zeta$ of $\mathcal{F}$ that is annihilated by the determinantal ideal $\mathfrak{U}_r(Q)$ — defined by all the $r \times r$ minors of $Q$ if $r \le p$, or $\langle 0 \rangle$ if $r > p$ — i.e., $P\zeta = 0$ for all $P \in \mathfrak{U}_r(Q)$.

**Corollary 2.** Let $M \in \mathbb{K}^{m \times n}$ be such that $\text{im}_{\mathcal{K}}(M) \neq \mathbb{K}^{m \times 1}$ and $L \in \mathbb{K}^{p \times m}$ a full row rank matrix satisfying $\text{ker}_{\mathcal{K}}(M) = \text{im}_{\mathcal{K}}(L)$, where $p = m - \text{rank}_{\mathcal{K}}(M)$. Moreover, let $D_i \in \mathbb{K}^{m \times m}$ for $i = 1, \dots, r$, $\mathcal{R} = \mathbb{K}[x_1, \dots, x_m]$, $x = (x_1 \dots x_m)^T$, $A = (D_1 x \dots D_r x) \in \mathcal{R}^{m \times r}$, $Q = L A \in \mathcal{R}^{p \times r}$, $Q = \text{coker}_{\mathcal{R}}(Q)$, $\mathcal{J} = \text{Fitt}_0(Q)$, and $\mathcal{S} = \mathcal{R}/\mathcal{J}$. Then, we have $\text{ker}_S(\bar{Q}) \neq 0$, and thus, there exists a non-zero matrix $K \in \mathcal{R}^{r \times q}$ such that $\text{ker}_S(\bar{Q}) = \text{im}_S(\bar{K})$.

*Proof.* By Remark 11, $\mathcal{J} = \text{Fitt}_0(Q)$ is a proper ideal of $\mathcal{R}$ so that $\mathcal{S} = \mathcal{R}/\mathcal{J} \neq 0$. McCoy's theorem, i.e., Theorem 3, shows that $\text{ker}_S(Q) = \text{ker}_S(\bar{Q}) \neq 0$ if and only if there exists $0 \neq s \in \mathcal{S}$ such that $Ps = 0$ for all $P \in \mathfrak{U}_r(Q)$.

If $r > p$, then $\mathcal{J} = \mathfrak{U}_r(Q) = \langle 0 \rangle$, and thus, $\mathcal{S} = \mathcal{R}$, $\bar{Q} = Q$, and $0 \neq 1 \in \mathcal{R}$ satisfies $0 \times 1 = 0$, which shows that $\text{ker}_{\mathcal{R}}(Q) \neq 0$.

If $r \le p$, then $\mathcal{J} = \langle m_i \rangle_{i=1,\dots,\alpha}$, where $\{m_i\}_{i=1,\dots,\alpha}$ denotes the set of all the $r \times r$ minors of $Q$ and $\alpha = p!/(r!(p-r)!)$.
The result holds because $\bar{0} \neq \bar{1} \in \mathcal{S} = \mathcal{R}/\mathcal{J}$ satisfies $m_i \times \bar{1} = \bar{m}_i = 0$ for $i = 1, \dots, \alpha$.

Finally, using the fact that $\mathcal{S} = \mathcal{R}/\mathcal{J}$ is a noetherian ring [10, 25] and $\text{ker}_S(\bar{Q}) \neq 0$, there exists a matrix $K \in \mathcal{R}^{r \times q}$ satisfying $\text{ker}_S(\bar{Q}) = \text{im}_S(\bar{K})$. $\square$

We now explain how a matrix $\bar{K}$ can be effectively computed using Gröbner basis methods [10, 12].

Using Definition 2, if $r > p$, then we have $\mathcal{J} = \langle 0 \rangle$ and $\mathcal{S} = \mathcal{R}$. A matrix $K$ can be computed by standard elimination theory (e.g., Gröbner basis methods) for the polynomial ring $\mathcal{R} = \mathbb{K}[x_1, \dots, x_m]$. Note the fact that $\text{ker}_{\mathcal{R}}(Q) \neq 0$ can also be proved by considering the *Euler-Poincaré characteristic* [10, 25] of the exact sequence of $\mathcal{R}$-modules $0 \leftarrow \mathcal{T}(Q) \leftarrow \mathcal{R}^{p \times 1} \leftarrow \mathcal{R}^{Q \times 1} \leftarrow \text{ker}_{\mathcal{R}}(Q) \leftarrow 0$,
i.e., $\mathrm{rank}_R(\mathrm{ker}_R(Q.)) - r + p - \mathrm{rank}_R(\mathcal{T}(Q)) = 0$, where $\mathrm{rank}_R(\mathcal{M})$ stands for the rank of a finitely generated $\mathcal{R}$-module $\mathcal{M}$ defined as the dimension of the finite-dimensional $\mathbb{K}(x_1, \dots, x_m)$-vector obtained by extending the coefficients of $\mathcal{M}$ from $\mathcal{R}$ to the field of fractions of $\mathcal{R}$, i.e., the field of rational functions $\mathbb{K}(x_1, \dots, x_m)$ in $x_1, \dots, x_m$ with coefficients in $\mathbb{K}$ [10, 25]. In other words, we have $\mathrm{rank}_R(\mathcal{M}) = \dim_{\mathbb{K}(x_1, \dots, x_m)} \mathbb{K}(x_1, \dots, x_m) \otimes_{\mathcal{R}} \mathcal{M}$. Hence, we have $\mathrm{rank}_R(\mathrm{ker}_R(Q.)) \ge r - p > 0$, which shows that $\mathrm{ker}_R(Q.) \ne 0$ and proves the existence of $K \in \mathcal{R}^{r \times q}$, where $q \ge r - p > 0$, satisfying $\mathrm{ker}_R(Q.) = \mathrm{im}_R(K.)$.

Now, if $r \le p$, using Definition 2, then let $\mathcal{J} = \mathrm{Fitt}_0(\mathcal{Q}) = \langle e_1, \dots, e_\gamma \rangle$. If $e = (e_1, \dots, e_\gamma)^T \in \mathcal{R}^{\gamma \times 1}$, then $\mathcal{J} = \mathrm{im}_R(.e)$ and we have the following exact sequence of $\mathcal{R}$-modules defining a finite presentation of $\mathcal{S}$ as a $\mathcal{R}$-module:

$$ \mathcal{R}^{1 \times \gamma} \xrightarrow{.e} \mathcal{R} \xrightarrow{\chi} \mathcal{S} \longrightarrow 0. \quad (24) $$

Combining eq. (23) and eq. (24), we obtain the following commutative exact diagram of $\mathcal{R}$-modules

<figure><img src="image_5.png" /></figure>

where $(\mathrm{id}_p \otimes \chi)(\mu_1 \dots \mu_p)^T = (\chi(\mu_1) \dots \chi(\mu_p))^T$ for all $(\mu_1 \dots \mu_p)^T \in \mathcal{R}^{p \times 1}$ and $I_p \otimes .e$ is defined by:

$$ \forall \Lambda = \begin{pmatrix} \lambda_1 \\ \vdots \\ \lambda_p \end{pmatrix} \in \mathcal{R}^{p \times \gamma}, \quad (I_p \otimes .e)(\Lambda) = \begin{pmatrix} \lambda_1 e \\ \vdots \\ \lambda_p e \end{pmatrix} = \Lambda e \in \mathcal{R}^{p \times 1}. \quad (25) $$

Similarly for $\mathrm{id}_r \otimes \sigma$ and $I_r \otimes .e$. Let us now characterize $\mathrm{im}_R(I_p \otimes .e)$. Let $\mathrm{col}(\Lambda) = (\lambda_1 \dots \lambda_p)^T \in \mathcal{R}^{p \gamma \times 1}$ be the vectorization of the matrix $\Lambda \in \mathcal{R}^{p \times \gamma}$ obtained by stacking the columns of $\Lambda$ into a single column vector, and $e^T \otimes I_p \in \mathcal{R}^{p \times p \gamma}$ the Kronecker product of $e^T$ by $I_p$, i.e., the diagonal matrix whose $p$ diagonal blocks are the row vector $e^T$ (see, e.g., [25]). Now, the “vec trick”, i.e., the standard identity $\mathrm{col}(\Lambda e) = (e^T \otimes I_p) \mathrm{col}(\Lambda)$ for all $\Lambda \in \mathcal{R}^{p \times \gamma}$ yields:

$$ (I_p \otimes .e)(\Lambda) = \Lambda e = \mathrm{col}(\Lambda e) = (e^T \otimes I_p) \mathrm{col}(\Lambda). \quad (26) $$

Note that eq. (26) shows that $\mathrm{im}_R(I_p \otimes .e)$ is exactly the image of the following $\mathcal{R}$-homomorphism

$$ (e^T \otimes I_l) : \mathcal{R}^{p \gamma \times 1} \longrightarrow \mathcal{R}^{p \times 1} \\ \gamma \longmapsto (e^T \otimes I_l) \gamma, $$

i.e., $\mathrm{im}_R(I_p \otimes .e) = \mathrm{im}_R((e^T \otimes I_p).)$. Now, using 1 of Proposition 3.1 of [7], we have

$$ \mathrm{ker}_S(\bar{Q.}) = \mathrm{im}_R(K.) / \mathrm{im}_R((e^T \otimes I_r).) = \mathrm{im}_S(\bar{K.}), \quad (27) $$

where the matrix $K \in \mathcal{R}^{r \times q}$ is defined by:

$$ \mathrm{ker}_R((Q \quad e^T \otimes I_p).) = \mathrm{im}_R\left(\begin{pmatrix} K \\ K' \end{pmatrix}\right). \quad (28) $$

The matrices $K \in \mathcal{R}^{r \times q}$ and $K' \in \mathcal{R}^{r \times p \gamma}$ can be computed using, for instance, the SyzygyModule command of the OREMODULES package, the Ker (resp., WeakKernelEmbedding) command of Singular [12] (resp., CapAndHomalg [1]). The computation of $\mathrm{ker}_S(\bar{Q.})$ and of a matrix $\bar{K}$ are available in the RANKFACTORIZATION package [9] dedicated to the rank factorization problem and its applications.
**Remark 12.** Considering $\mathcal{S}$ as a $\mathcal{R}$-module and applying the left exact contravariant functor $\operatorname{hom}_{\mathcal{R}}(\cdot, \mathcal{S})$ to the finite presentation of $\mathcal{Q}$ defined by eq. (19), we obtain the exact sequence of $\mathcal{R}$-modules

$$ \mathcal{S}^{p \times 1} \leftarrow \bar{\mathcal{Q}}. \quad \mathcal{S}^{r \times 1} \leftarrow \operatorname{hom}_{\mathcal{R}}(\mathcal{Q}, \mathcal{S}) \leftarrow 0, $$

i.e., $\ker_S(\bar{\mathcal{Q}}.) \cong \operatorname{hom}_{\mathcal{R}}(\mathcal{Q}, \mathcal{S})$, where the $\mathcal{R}$-module $\operatorname{hom}_{\mathcal{R}}(\mathcal{Q}, \mathcal{S})$ inherits a $\mathcal{S}$-module structure defined by $(f s)(q) = f(q) s$ for all $s \in \mathcal{S}$, $q \in \mathcal{Q}$, and $f \in \operatorname{hom}_{\mathcal{R}}(\mathcal{Q}, \mathcal{S})$ [10, 25]. Note that the finitely presented $\mathcal{R}$-module $\operatorname{hom}_{\mathcal{R}}(\mathcal{Q}, \mathcal{S})$ can be effectively characterized (see, e.g., [12, 7]) and $\bar{\mathcal{K}}$ can be computed using, e.g., OREMORPHISMS [8], Singular [12], or CapAndHomalg [1].

**Example 5.** We continue Example 4. We note $\mathcal{J} = \operatorname{Fitt}_0(\mathcal{Q}) = \langle e_1, e_2, e_3 \rangle_{\mathcal{R}}$, where

$$ e_1 = (10 x_1 - 9 x_2 - 10 x_3) (3 x_1 + x_4), \quad e_2 = (2 x_1 - 3 x_2 - 2 x_3) x_4, \quad e_3 = (3 x_1 + x_4) x_2, $$

$e = (e_1 \ e_2 \ e_3)^T$, and $\mathcal{S} = \mathcal{R}/\mathcal{J}$. Computing the left-hand side of eq. (28) with $p = 3$, we obtain:

$$ \ker_S(\bar{\mathcal{Q}}.) = \operatorname{im}_S(\bar{\mathcal{K}}.), \quad K = \begin{pmatrix} x_2 & 0 & 2(x_1 - x_3) \\ x_4 & 3x_1 + x_4 & 3x_4 \end{pmatrix} \in \mathcal{R}^{2 \times 3}. $$

The non-zero entries of $K$ are homogeneous polynomials of total degree 1 in $x_1, \dots, x_4$.

By construction of $\bar{\mathcal{K}}$, we have $\ker_S(\bar{\mathcal{Q}}.) = \operatorname{im}_S(\bar{\mathcal{K}}.)$, and thus, $\bar{\mathcal{Q}}\bar{\mathcal{K}} = 0$, i.e., $\mathcal{Q}K \in \mathcal{J}^{p \times q}$, which yields $\mathcal{Q}(u)K(u) = 0$ for all $u \in \mathcal{V}_{\mathcal{K}}(\mathcal{J})$, i.e.: $\operatorname{im}_{\mathcal{K}}(K(u).) \subseteq \ker_{\mathcal{K}}(\mathcal{Q}(u).)$ for all $u \in \mathcal{V}_{\mathcal{K}}(\mathcal{J})$.

**Remark 13.** If $0 \neq \bar{\eta} \in \ker_S(\bar{\mathcal{Q}}.)$, where $\eta \in \mathcal{R}^{r \times 1}$, then $\mathcal{Q}\eta \in \mathcal{J}^{p \times 1}$ and $\eta \notin \mathcal{J}^{r \times 1}$, i.e., $\mathcal{Q}(u)\eta(u) = 0$, i.e., $\eta(u) \in \ker_{\mathcal{K}}(\mathcal{Q}(u).)$ for all $u \in \mathcal{V}_{\mathcal{K}}(\mathcal{J})$, where $\eta$ is not identically zero as a polynomial map from $\mathcal{V}_{\mathcal{K}}(\mathcal{J})$ to $\mathcal{K}^{r \times 1}$. Using $\ker_S(\bar{\mathcal{Q}}.) \subseteq \operatorname{im}_S(\bar{\mathcal{K}}.)$, there exists $\bar{\xi} \in \mathcal{S}^{q \times 1}$ such that $\bar{\eta} = \bar{\mathcal{K}}\bar{\xi}$, i.e., $\eta - K\xi \in \mathcal{J}^{r \times 1}$. Thus, we have $\eta(u) = K(u)\xi(u) \in \operatorname{im}_{\mathcal{K}}(K(u).)$ for all $u \in \mathcal{V}_{\mathcal{K}}(\mathcal{J})$. But it is important to note that $\zeta \in \ker_{\mathcal{K}}(\mathcal{Q}(u).)$, at a fixed $u \in \mathcal{V}_{\mathcal{K}}(\mathcal{J})$, is not necessarily of the form $\zeta = \eta(u)$ for a certain $\bar{\eta} \in \ker_S(\bar{\mathcal{Q}}.)$, i.e., for a certain polynomial vector $\eta \in \mathcal{R}^{r \times 1} : \mathcal{V}_{\mathcal{K}}(\mathcal{J}) \to \mathcal{K}^{r \times 1}$. Indeed, $\zeta \in \mathcal{K}^{r \times 1}$ can result from a drop of the rank of the matrix $\mathcal{Q}$ at a particular $u \in \mathcal{V}_{\mathcal{K}}(\mathcal{J})$. For an explicit example, see Example 6 below.

A complete description of $\ker_{\mathcal{K}}(\mathcal{Q}(u).)$ will be given in the next section (see Theorem 4).

### 3.2.3 General solutions for the case $M = 0$

The following result will play an important role in what follows.

**Theorem 4.** Let $\mathcal{Q} = \operatorname{coker}_{\mathcal{R}}(\cdot, \mathcal{Q})$ be the $\mathcal{R}$-module finitely presented by the matrix $\mathcal{Q} \in \mathcal{R}^{p \times r}$ defined in Corollary 2, $\mathcal{J}_k = \operatorname{Fitt}_k(\mathcal{Q})$ for $k = 0, \dots, r-1$, $\mathcal{J}_r = \mathcal{R}$, $\mathcal{J} = \mathcal{J}_0$, $S_k = \mathcal{R}/\mathcal{J}_k$ for $k = 0, \dots, r-1$, $S = S_0 = \mathcal{R}/\mathcal{J}$, and $\chi_k : \mathcal{R} \to S_k$ the canonical ring epimorphisms for $k = 0, \dots, r-1$. Then, for $k = 0, \dots, r-1$, there exists a matrix $K_k \in \mathcal{R}_k^{r \times q_k}$ such that:

$$ \ker_{S_k}(\chi_k(\mathcal{Q}.)). = \operatorname{im}_{S_k}(\chi_k(K_k).). $$

In particular, we have $\operatorname{im}_{S_k}(K_k(u).) \subseteq \ker_{\mathcal{K}}(\mathcal{Q}(u).)$ for all $u \in \mathcal{V}_{\mathcal{K}}(J_k)$ and $k = 0, \dots, r-1$.

Finally, for $k = 0, \dots, r-1$, we have:

$$ \forall u \in \mathcal{V}_{\mathcal{K}}(J_k) \setminus \mathcal{V}_{\mathcal{K}}(J_{k+1}), \quad \ker_{\mathcal{K}}(\mathcal{Q}(u).) = \operatorname{im}_{\mathcal{K}}(K_k(u).). \qquad (29) $$

*Proof.* Let $\chi_k : \mathcal{R} \to S_k = \mathcal{R}/\mathcal{J}_k$ be the epimorphism of $\mathcal{K}$-algebras for $k = 0, \dots, r-1$ and note $\chi_k(\mathcal{Q}) = (\chi_k(Q_{ij}))_{1 \le r, 1 \le j \le p} \in \mathcal{S}_k^{p \times r}$ and similarly for any matrix with entries in $\mathcal{R}$. Note that we have $\chi_0 = \chi$, where $\chi$ is defined by eq. (22), i.e., $\chi_0(r) = \chi(r) = \bar{\tau}$ for all $r \in \mathcal{R}$. Note that $S_k$ has a $\mathcal{R}$-module structure defined by $r' \chi_k(r) := \chi_k(r') = \chi_k(r') \chi_k(r)$ for all $r, r' \in \mathcal{R}$.

Using both the $\mathcal{R}$-module structure and the ring structure of $S_k$, we first have:

$$ \ker_{S_k}(\mathcal{Q}.) = \{\chi_k(\eta) \mid \eta \in \mathcal{R}^{r \times 1} : \mathcal{Q} \chi_k(\eta) = \chi_k(\mathcal{Q} \eta) = \chi_k(\mathcal{Q}) \chi_k(\eta) = 0\} = \ker_{S_k}(\chi_k(\mathcal{Q}.)). $$
Using the fact that $\mathcal{J}_k \neq \mathcal{R}$ for $k=0, \dots, r-1$, $S_k$ is a non-trivial ring. Then, Theorem 3 shows that $\ker_{S_k}(\chi_k(Q)) \neq 0$ since, by construction of $S_k = \mathcal{R}/\mathcal{J}_k$, all the $(r-k) \times (r-k)$ minors of $\chi_k(Q)$ vanish in $S_k$, and thus, so do all the $r \times r$ minors of $\chi_k(Q)$ (see eq. (20)). Using the fact that $S_k$ is a noetherian ring, there exists a non-zero matrix $K_k \in \mathcal{R}_k^{r \times q_k}$ such that $\ker_{S_k}(\chi_k(Q)) = \operatorname{im}_{S_k}(\chi_k(K_k))$. Thus, we have the following exact sequence of $S_k$-modules:

$$S_k^{q_k \times 1} \xrightarrow{\chi_k(K_k)} S_k^{r \times 1} \xrightarrow{\chi_k(Q)} S_k^{p \times 1}. \qquad (30)$$

Note that $\mathcal{J}_{r-1}$ is the ideal generated by all the entries of $Q$, which yields $\chi_{r-1}(Q) = 0$, i.e., $\ker_{S_{r-1}}(\chi_{r-1}(Q)) = S_{r-1}^{r \times 1}$, i.e., $K_{r-1} = I_r$. This case corresponds to Section 2.2.

Now, we have $\chi_k(Q)\chi_k(K_k) = \chi_k(QK_k) = 0$, and thus, we have $QK_k \in \mathcal{J}_k^{p \times q_k}$ and $K_k \notin \mathcal{J}_k^{r \times q_k}$, which yields $Q(u)K_k(u) = 0$ for all $u \in \mathcal{V}(\mathcal{J}_k)$, where $K_k : \mathcal{V}(\mathcal{J}_k) \to \mathcal{K}^{r \times q_k}$ is not identically zero, and then proves that $\operatorname{im}_{\mathcal{K}}(K_k(u)) \subseteq \ker_{\mathcal{K}}(Q(u))$ for all $u \in \mathcal{V}(\mathcal{J}_k)$.

Finally, let us prove that $\ker_{\mathcal{K}}(Q(u)) = \operatorname{im}_{\mathcal{K}}(K_k(u))$ for all $u \in \mathcal{V}_{\mathcal{K}}(\mathcal{J}_k) \setminus \mathcal{V}_{\mathcal{K}}(\mathcal{J}_{k+1})^2$. Let us consider $u \in \mathcal{V}_{\mathcal{K}}(\mathcal{J}_k) \setminus \mathcal{V}_{\mathcal{K}}(\mathcal{J}_{k+1})$ so that $\operatorname{rank}_{\mathcal{K}}(Q(u)) = r-k+1$. Hence, there exists a $(r-k-1) \times (r-k-1)$ minor of $Q$, denoted by $\mathfrak{m}$, such that $\mathfrak{m}(u) \neq 0$. Note that $\mathfrak{m} \in \mathcal{J}_{k+1}$ and $f = \chi_k(\mathfrak{m})$ is not a nilpotent element of $S_k$, i.e., $\mathfrak{m} \notin \sqrt{\mathcal{J}_k}$ (since $\mathfrak{m} \in \sqrt{\mathcal{J}_k}$ yields $\mathfrak{m}(u) = 0$). We can consider the non-trivial ring $S_{k,f} = \{s/f^k \mid s \in S, k \in \mathbb{Z}_{\ge 0}\}$ defined as the localization of $S_k$ at the multiplicatively closed set $\{f^k\}_{k \in \mathbb{Z}_{\ge 0}}$ and the canonical ring homomorphism $j_f : S_k \to S_{k,f}$ defined by $j_f(s) = s/1$ for all $s \in S_k$, whose kernel is given by $\ker j_f = \{s \in S_k \mid \exists c \in \mathbb{Z}_{\ge 0} : f^c s = 0\}$ [10, 25]. Note $K_{k,f} = j_f(\chi_k(K_k))$ and $Q_f = j_f(\chi_k(Q))$. Using the fact that $S_{k,f}$ is a flat $S_k$-module [10, 25], applying the covariant exact functor $S_{k,f} \otimes_{S_k} \cdot$ to eq. (30), we obtain the following exact sequence of $S_{k,f}$-modules:

$$S_{k,f}^{q_k \times 1} \xrightarrow{K_{k,f}} S_{k,f}^{r \times 1} \xrightarrow{Q_f} S_{k,f}^{p \times 1} \longrightarrow \ker_{S_{k,f}}(Q_f) \longrightarrow 0. \qquad (31)$$

Using the fact that $f$ is invertible in $S_{k,f}$, the matrix $Q_f$ is then equivalent to the following matrix:

$$\left( \begin{array}{cc} I_{r-k-1} & 0 \\ 0 & 0 \end{array} \right) \in S_{k,f}^{p \times r}.$$

Thus, we have $\ker_{S_{k,f}}(Q_f) \cong S_{k,f}^{(p-r+k+1) \times 1}$, i.e., $\ker_{S_{k,f}}(Q_f)$ is a free $S_{k,f}$-module, which yields that eq. (31) splits [10, 25]. Therefore, there exist $U \in \mathcal{R}^{r \times p}$, $V \in \mathcal{R}^{q_k \times r}$, $\alpha, \beta \in \mathbb{Z}_{\ge 0}$ such that $U_f = f^{-\alpha} \chi_k(U) \in S_{k,f}^{r \times p}$ and $V_f = f^{-\beta} \chi_k(V) \in S_{k,f}^{q_k \times r}$ satisfy $K_{k,f}V_f + U_fQ_f = I_r$. Let $\delta = \operatorname{lcm}(\alpha, \beta)$. Using the characterization of $\ker j_f$, the last identity is equivalent to the existence of $\gamma \in \mathbb{Z}_{\ge 0}$ satisfying

$$f^{\gamma} (f^{\delta-\beta} \chi_k(K_k V) + f^{\delta-\alpha} \chi_k(U Q) - f^{\delta} I_r) = 0,$$

i.e., to $\mathfrak{m}^{\gamma}(\mathfrak{m}^{\delta-\beta} K_k V + \mathfrak{m}^{\delta-\alpha} U Q - \mathfrak{m}^{\delta} I_r) \in \mathcal{J}_k^{r \times r}$. Now, using $u \in \mathcal{V}_{\mathcal{K}}(\mathcal{J}_k)$ and $\mathfrak{m}(u) \neq 0$, we then have $\mathfrak{m}(u)^{\gamma}(\mathfrak{m}(u)^{\delta-\beta} K_k(u) V(u) + \mathfrak{m}(u)^{\delta-\alpha} U(u) Q(u) - \mathfrak{m}(u)^{\delta} I_r) = 0$, and thus:

$$K_k(u) (\mathfrak{m}(u)^{-\beta} V(u)) + (\mathfrak{m}(u)^{-\alpha} U(u)) Q(u) = I_r.$$

Finally, if $v \in \ker_{\mathcal{K}}(Q(u))$, then the last identity yields $v = K_k(u)(\mathfrak{m}(u)^{-\beta}V(u)) \in \operatorname{im}_{\mathcal{K}}(K_k(u))$ and shows that $\ker_{\mathcal{K}}(Q(u)) = \operatorname{im}_{\mathcal{K}}(K_k(u))$, which concludes the proof. $\square$

Let us illustrate eq. (29) with an explicit example.

**Example 6.** Let $Q = \ker_{\mathcal{R}}(Q)$ be the $\mathcal{R} = \mathbb{K}[x_1, x_2]$-module finitely presented by the following matrix:

$$Q = \left( \begin{array}{ccc} x_1 & x_2 & 0 \\ x_2 & x_1 & 0 \end{array} \right) \in \mathcal{R}^{2 \times 3}.$$

Then, we have:

$$\begin{align*} \mathcal{J}_0 &= \mathrm{Fitt}_0(Q) = \langle 0 \rangle, & \mathcal{J}_1 &= \mathrm{Fitt}_1(Q) = \langle (x_1 - x_2)(x_1 + x_2) \rangle, & \mathcal{J}_2 &= \mathrm{Fitt}_2(Q) = \langle x_1, x_2 \rangle, \\ \mathcal{V}_{\mathcal{K}}(\mathcal{J}_0) &= \mathbb{K}^{2 \times 1}, & \mathcal{V}_{\mathcal{K}}(\mathcal{J}_1) &= \{(1 \quad 1)^T u_1 \mid u_1 \in \mathbb{K}\} \cup \{(1 \quad -1)^T u_1 \mid u_1 \in \mathbb{K}\}, & \mathcal{V}_{\mathcal{K}}(\mathcal{J}_2) &= \{0\}. \end{align*}$$

<footnote>$^2$The proof of this point was communicated to us by Prof. David Eisenbud (University of California Berkeley). We are grateful to him for authorizing its reproduction here.</footnote>
We can check that $\mathrm{rank}_{\mathbb{K}}(Q(u)) = 2$ if $u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_0) \setminus \mathcal{V}_{\mathbb{K}}(\mathcal{J}_1)$, $\mathrm{rank}_{\mathbb{K}}(Q(u)) = 1$ if $u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_1) \setminus \mathcal{V}_{\mathbb{K}}(\mathcal{J}_2)$, and $\mathrm{rank}_{\mathbb{K}}(Q(u)) = 0$ if $u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_2)$.

Let us now characterize $\ker_{\mathbb{K}}(Q(u).)$ for $u \in \mathbb{K}^{2 \times 1}$. If $u \in \mathbb{K}^{2 \times 1}$, then we have:

$$ \ker_{\mathbb{K}}(Q(u).) = \{ \xi = (\xi_1 \ \xi_2 \ \xi_3)^T \in \mathbb{K}^{3 \times 1} \mid u_1 \xi_1 + u_2 \xi_2 = 0, u_2 \xi_1 + u_1 \xi_2 = 0 \}. $$

If we set $K = (0 \ 0 \ 1)^T$, $K' = (1 \ -1 \ 0)^T$, and $K'' = (1 \ 1 \ 0)^T$, then we can check that:

$$ \ker_{\mathbb{K}}(Q(u).) = \left\{ \begin{array}{ll} \mathrm{im}_{\mathbb{K}}(K.) = K \mathbb{K}, & u \in \mathbb{K}^{2 \times 1} \setminus \mathcal{V}_{\mathbb{K}}(\mathcal{J}_1), \\ \mathrm{im}_{\mathbb{K}}((K \ K').) = K \mathbb{K} + K' \mathbb{K}, & u_2 = u_1 \neq 0, \\ \mathrm{im}_{\mathbb{K}}((K \ K'').) = K \mathbb{K} + K'' \mathbb{K}, & u_2 = -u_1 \neq 0, \\ \mathrm{im}_{\mathbb{K}}(I_3.), & u_1 = u_2 = 0. \end{array} \right. $$

Let now we first consider $S_0 = \mathcal{R}$. We can check again that $\ker_{\mathcal{R}}(Q.) = \mathrm{im}_{\mathcal{R}}(K.)$.

Let us now consider the ring $S_1 = \mathcal{R}/\mathcal{J}_1$ and $\chi_1 : \mathcal{R} \to S_1$ the canonical ring epimorphism. Then, we have $\ker_{S_1}(\chi_1(Q.)) = \mathrm{im}_{S_1}(\chi_1(K_1.))$, where:

$$ K_1 = \begin{pmatrix} 0 & -x_2 & x_1 \\ 0 & x_1 & -x_2 \\ 1 & 0 & 0 \end{pmatrix} \in \mathcal{R}^{3 \times 3}. $$

Let us finally consider the ring $S_2 = \mathcal{R}/\mathcal{J}_2$ and $\chi_2 : \mathcal{R} \to S_2$ the canonical ring epimorphism. Then, we have $\chi_2(Q) = 0$ and $\ker_{S_2}(\chi_2(Q)) = S_2^{3 \times 3}$, i.e., $K_2 = I_3$ satisfies $\ker_{S_2}(\chi_2(Q)) = \mathrm{im}_{S_2}(\chi_2(K_2.))$.

Finally, let us check again that:

$$ \ker_{\mathbb{K}}(Q(u).) = \left\{ \begin{array}{ll} \mathrm{im}_{\mathbb{K}}(K(u).), & u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_0) \setminus \mathcal{V}_{\mathbb{K}}(\mathcal{J}_1), \\ \mathrm{im}_{\mathbb{K}}(K_1(u).), & u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_1) \setminus \mathcal{V}_{\mathbb{K}}(\mathcal{J}_2), \\ \mathrm{im}_{\mathbb{K}}(K_2(u).), & u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_2). \end{array} \right. $$

It is clear for $i=0$ and $i=2$. Thus, if we consider $i=1$, then we have

$$ \forall u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_1) \setminus \mathcal{V}_{\mathbb{K}}(\mathcal{J}_2), \quad \mathrm{im}_{\mathbb{K}}(K_1(u.)) = \begin{cases} K \mathbb{K} + K' \mathbb{K}, & u_2 = u_1 \neq 0, \\ K \mathbb{K} + K'' \mathbb{K}, & u_2 = -u_1 \neq 0, \end{cases} $$

which finally illustrates Theorem 4 on a simple example.

Let us now study the connections between the matrices $K_k$'s for $k=0, \dots, r-1$, where $K_0 = K$.

Using $\mathcal{J}_r = \mathcal{R}$, for $k=0, \dots, r-1$, we have the following exact sequence of ring homomorphisms:

$$ 0 \longrightarrow \mathcal{J}_{k+1}/\mathcal{J}_k \longrightarrow S_k \xrightarrow{\delta_k} S_{k+1} \longrightarrow 0. $$

Thus, $S_{k+1}$ inherits a $S_k$-module structure and we have $\chi_{k+1} = \delta_k \circ \chi_k$, where $\chi_k : \mathcal{R} \to S_k$ is the canonical ring epimorphism. Applying the covariant functor $S_{k+1} \otimes_{S_k} \cdot$ to the exact sequence

$$ S_k^{p \times 1} \xleftarrow{\chi_k(Q).} S_k^{r \times 1} \xleftarrow{\chi_k(K_k).} S_k^{q_k \times 1} \text{ of } S_k\text{-modules, we obtain the complex of } S_{k+1}\text{-modules} $$

$$ S_{k+1}^{p \times 1} \xleftarrow{\chi_{k+1}(Q).} S_{k+1}^{r \times 1} \xleftarrow{\chi_{k+1}(K_k).} S_{k+1}^{q_k \times 1}, $$

which yields

$$ \mathrm{im}_{S_{k+1}}(\chi_{k+1}(K_k).) \subseteq \ker_{S_{k+1}}(\chi_{k+1}(Q).) = \mathrm{im}_{S_{k+1}}(\chi_{k+1}(K_{k+1}).), $$

and proves the existence of a matrix $L_{k,k+1} \in \mathcal{R}^{q_{k+1} \times q_k}$ such that:

$$ \chi_{k+1}(K_k) = \chi_{k+1}(K_{k+1}) \chi_{k+1}(L_{k,k+1}), \quad k = 0, \dots, r-2. \qquad (32) $$

The next result gives the solutions of the rank factorization problem eq. (4) when $M=0$.
**Corollary 3.** If $M = 0$, then all the solutions of the rank factorization problem eq. (4) are defined by

$$ \forall k = 0, \dots, r-1, \forall u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_k) \setminus \mathcal{V}_{\mathbb{K}}(\mathcal{J}_{k+1}), \forall Y' \in \mathbb{K}^{q_k \times n}, (u, v_k(u, Y')) = K_k(u) Y'), $$

where the matrix $K_k$ is defined in Theorem 4. Moreover, we have

$$ \forall u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_{k+1}), \forall Y' \in \mathbb{K}^{q_k \times n}, v_k(u, Y') = K_{k+1}(u) (L_{k,k+1}(u) Y') = v_{k+1}(u, L_{k,k+1}(u) Y'), $$

and thus, all the solutions of the rank factorization problem eq. (4) are defined, up to redundancy, by:

$$ \forall k = 0, \dots, r-1, \forall u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_k), \forall Y' \in \mathbb{K}^{q_k \times n}, (u, v_k(u, Y')) = K_k(u) Y'). $$

*Proof.* If $M = 0$, then we have $L = I_m$, $Q = A$, and $A(u)v = 0$ shows that the each column of $v \in \mathbb{K}^{r \times n}$ must belong to $\ker_{\mathbb{K}}(A(u))$. Using Theorem 4, for $k = 0, \dots, r-1$, $(u, v(u) = K_k(u) Y')$ for all $u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_k)$ and for all $Y' \in \mathbb{K}^{q_k \times n}$ are all the solutions of eq. (4).

Using eq. (32), we have $K_k - K_{k+1} L_{k,k+1} \in \mathcal{J}_{k+1}^{r \times q_k}$, and thus, $K_k(u) = K_{k+1}(u) L_{k,k+1}(u)$ for all $u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_{k+1})$, which finally shows $v_k(u, Y') = v_{k+1}(u, L_{k,k+1}(u) Y')$ for all $u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_{k+1})$. $\square$

The computation of all the solutions of the rank factorization problem for $M = 0$, characterized in Corollary 3, are implemented in the RANKFACTORIZATION package [9].

**Example 7.** Let us consider the following matrices:

$$ D_1 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \quad D_2 = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \quad D_3 = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix} \quad M = \begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}. $$

Then, $\mathcal{R} = \mathbb{K}[x_1, x_2]$, $L = I_2$, and $\mathcal{Q} = \text{coker}_{\mathcal{R}}(\mathcal{Q})$ is the $\mathcal{R}$-module finitely presented by:

$$ Q = A = \begin{pmatrix} x_1 & x_2 & 2x_1 + x_2 \\ x_2 & x_1 & x_1 + 2x_2 \end{pmatrix} \in \mathcal{R}^{2 \times 2}. $$

We have $\mathcal{J}_0 = \text{Fitt}_0(\mathcal{Q}) = \langle 0 \rangle$, $\mathcal{J}_1 = \text{Fitt}_1(\mathcal{Q}) = \langle (x_1 - x_2)(x_1 + x_2) \rangle$, $\mathcal{J}_2 = \text{Fitt}_2(\mathcal{Q}) = \langle x_1, x_2 \rangle$, $\mathcal{V}_{\mathbb{K}}(\mathcal{J}_0) = \mathbb{K}^{2 \times 1}$, $\mathcal{V}_{\mathbb{K}}(\mathcal{J}_1) = \{(u_1 \quad u_1)^T, (u_1 \quad -u_1)^T \mid u_1 \in \mathbb{K}\}$, and $\mathcal{V}_{\mathbb{K}}(\mathcal{J}_2) = \{(0 \quad 0)^T\}$.

If we note $S_k = \mathcal{R}/\mathcal{J}_k$, for $k = 0, 1, 2$, then we have $\ker_{S_k}(\mathcal{Q}) = \text{im}_{S_k}(K_k)$, where:

$$ K_0 = \begin{pmatrix} 2 \\ 1 \\ -1 \end{pmatrix}, \quad K_1 = \begin{pmatrix} 2 & 0 & 0 \\ 1 & -3x_2 & 2x_1 + x_2 \\ -1 & 2x_1 - x_2 & -x_2 \end{pmatrix}, \quad K_2 = I_3. $$

Moreover, we have $K_0 = K_1 L_{0,1}$ and $K_1 = K_2 L_{1,2}$, where $L_{0,1} = (1 \quad 0 \quad 0)^T$ and $L_{1,2} = K_1$. All the solutions to the rank factorization problem are then defined by:

$$ \left\{ \begin{array}{lll} \forall u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_0) \setminus \mathcal{V}_{\mathbb{K}}(\mathcal{J}_1), & \forall Y' \in \mathbb{K}^{1 \times 3}, & v_0(u, Y') = K_0 Y', \\ \forall u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_1) \setminus \mathcal{V}_{\mathbb{K}}(\mathcal{J}_2), & \forall Y' \in \mathbb{K}^{3 \times 3}, & v_1(u, Y') = K_1(u) Y', \\ \forall u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_2), & \forall Y' \in \mathbb{K}^{3 \times 3}, & v_2(u, Y') = Y'. \end{array} \right. \quad (33) $$

We can check again that $(u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_1), v_0(u, Y') = K_0 Y')$ and $(u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_2), v_1(u, Y') = K_1 Y')$ are also solutions, which are respectively contained in the second and third set of eq. (33). Therefore, up to redundancy, all the solutions are also defined by:

$$ \left\{ \begin{array}{lll} \forall u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_0), & \forall Y' \in \mathbb{K}^{1 \times 3}, & v_0(u, Y') = K_0 Y', \\ \forall u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_1), & \forall Y' \in \mathbb{K}^{3 \times 3}, & v_1(u, Y') = K_1(u) Y', \\ \forall u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_2), & \forall Y' \in \mathbb{K}^{3 \times 3}, & v_2(u, Y') = Y'. \end{array} \right. $$

Finally, note that, e.g., $u = (1 \quad 1)^T$ and

$$ v = \begin{pmatrix} 0 & 0 & 0 \\ 0 & -3 & 3 \\ 0 & 1 & -1 \end{pmatrix} $$

define a solution of eq. (4) which is not of the form $v_0(u, Y') = K_0 Y'$ for $Y' \in \mathbb{K}^{1 \times 3}$. It shows that we also have to consider the solutions of eq. (4) over $S_1$ and $S_2$ to get the complete set of solutions.
Combining $Q = LA$ and $\overline{Q}\overline{K} = 0$, we get $\overline{L}(\overline{A}\overline{K}) = 0$, i.e., $\mathrm{im}_S((\overline{A}\overline{K}).) \subseteq \mathrm{ker}_S(\overline{L}.) = \mathrm{im}_S(\overline{X}.)$, which using $\mathrm{ker}_S(\overline{X}.) = 0$ shows that there exists a unique matrix $\overline{B} \in S^{l \times q}$, where $B \in \mathcal{R}^{l \times q}$, satisfying $\overline{A}\overline{K} = \overline{X}\overline{B}$, and we have the commutative exact diagram of $S$-modules:

$$ \begin{tikzcd} & & S^{p \times 1} \arrow[r, "\overline{L}."] \arrow[d, "\overline{M}."] & S^{m \times 1} \arrow[d, "\overline{M}."] & S^{n \times 1} \arrow[d, "\overline{Y}."] \\ 0 \arrow[r] & S^{p \times 1} \arrow[d, "\overline{L}."] & S^{m \times 1} \arrow[r, "\overline{X}.", "\uparrow"] \arrow[d, "\overline{A}.", "\uparrow"] & S^{l \times 1} \arrow[r, "0.", "\downarrow"] & 0 \arrow[r] \\ 0 \arrow[r] & S \otimes_R \mathcal{T}(Q) \arrow[r, "\mathrm{id}_S \otimes \kappa"] \arrow[d, "\overline{Q}.", "\downarrow"] & S^{p \times 1} \arrow[r, "\overline{K}.", "\uparrow"] \arrow[d, "\overline{K}.", "\uparrow"] & S^{q \times 1} \arrow[r, "\overline{B}.", "\uparrow"] & 0 \arrow[r] \arrow[d, "\overline{B}.", "\downarrow"'] \arrow[r] & 0 \end{tikzcd} \quad (38) $$

Using the identity $V X = I_l$ (see eq. (37)), eq. (34) then yields eq. (35).

Finally, the identity eq. (35) does not depend on a particular left inverse $V$ of $X$. This can be checked again by considering a second left inverse $V'$ of $X$, i.e., $V' X = I_l$. Then, we have $(V' - V) X = 0$, which shows that the rows of $V' - V$ belong to $\mathrm{ker}_{\mathbb{K}}(\overline{X}) = \mathrm{im}_{\mathbb{K}}(\overline{L})$, and thus, that there exists $L' \in \mathbb{K}^{l \times p}$ such that $V' = V + L' L$, which using $Q = LA$ and $\overline{Q}\overline{K} = 0$, yields $\overline{V'}\overline{A}\overline{K} = \overline{V}\overline{A}\overline{K} + \overline{L'}(\overline{L}\overline{A})\overline{K} = \overline{V}\overline{A}\overline{K}$. $\square$

Proposition 2 shows that there exists a unique matrix $\overline{B} \in S^{l \times q}$ satisfying $\overline{A}\overline{K} = \overline{X}\overline{B}$ defined by $\overline{B} = \overline{V}\overline{A}\overline{K}$. But the pre-image $B \in \mathcal{R}^{l \times q}$ of $\overline{B}$ is not uniquely defined. It is defined by any matrix $B \in \mathcal{R}^{l \times q}$ satisfying $B - V A K \in \mathcal{J}^{l \times q}$. To simplify, we shall thus set $B = V A K$.

**Remark 14.** Note that the construction of the commutative exact diagram eq. (38) corresponds to finding an $\mathcal{R}$-algebra $S$ for which the pullback (see, e.g., [10, 25]) of the $S$-homomorphisms $\overline{A} : S^{r \times 1} \to S^{m \times 1}$ and $\overline{X} : S^{l \times 1} \to S^{m \times 1}$ is non-trivial, i.e., such that $\mathrm{ker}_S((\overline{A} \ \overline{X}).) \neq 0$.

**Example 8.** We continue Example 5. We can first check that:

$$ X = (5 \ 0 \ 2 \ 2)^T, \quad Y = (6 \ 0 \ 0), \quad V = \frac{1}{2} (0 \ 0 \ 0 \ 1), \quad V X = 1. $$

Let $\overline{x_i}$ be the residue class of $x_i$ in $S = \mathcal{R}/\mathcal{J}$ for $i = 1, \dots, 4$. Computing $\overline{B} = \overline{V}\overline{A}\overline{K}$, we get:

$$ \overline{B} = \left( \overline{x_4} \left( \frac{5}{2} \overline{x_2} + \overline{x_3} \right) \quad \overline{x_3} \left( 3 \overline{x_1} + \overline{x_4} \right) \quad 3 \overline{x_4} \left( \frac{5}{2} \overline{x_2} + \overline{x_3} \right) \right) \in S^{1 \times 3}. $$

Finally, we can check again that the identity of matrices $\overline{A}\overline{K} = \overline{X}\overline{B}$ with entries in $S$.

Let $\mathcal{B} = \mathrm{coker}_S(\overline{B}.) = S^{l \times 1}/(\overline{B} S^{q \times 1})$ be the $S$-module finitely presented by $\overline{B}$, i.e., defined by the following finite presentation:

$$ S^{q \times 1} \xrightarrow{\overline{B}.} S^{l \times 1} \xrightarrow{\sigma} \mathcal{B} \longrightarrow 0. \quad (39) $$

The next lemma shows that $\mathcal{B}$ depends only on the rank factorization problem eq. (2).

**Lemma 6.** With the above notations, the $S$-module $\mathcal{B} = \mathrm{coker}_S(\overline{B}.)$ does not depend on the choice of the bases defining $L$ and $X$, and on the choice of a generating set of $\mathrm{ker}_S(\overline{Q}.)$ defining $\overline{K}$. Hence, the Fitting ideals of $\mathcal{B}$ defined by

$$ \mathrm{Fitt}_i(\mathcal{B}) = \mathrm{Fitt}_i(\mathrm{coker}_S(\overline{B}.)), \quad i = 0, \dots, l. \quad (40) $$

depend only on the matrices $M$ and $D_1, \dots, D_r$.

*Proof.* Let $L' \in \mathbb{K}^{p \times m}$ be a matrix whose rows define another basis of $\mathrm{ker}_{\mathbb{K}}(\overline{M}.)$. Then, there exists an invertible matrix $T \in \mathbb{K}^{p \times p}$ such that $L' = T L$. Similarly, let $X' \in \mathbb{K}^{m \times l}$ be a matrix whose columns define another basis of $\mathrm{im}_{\mathbb{K}}(\overline{M}.)$. Then, there exists an invertible matrix $W \in \mathbb{K}^{l \times l}$ such that $X' = X W$. Finally, let $Q' = L' A = T Q$, where $Q = LA$, and $\overline{K}' \in S^{r \times q'}$ be such that $\mathrm{ker}_S(\overline{Q}'). = \mathrm{im}_S(\overline{K}').$. Using the invertibility of $T$, we clearly have $\mathrm{ker}_S(\overline{Q}'). = \mathrm{ker}_S(\overline{Q}.)$, and thus, $\mathrm{im}_S(\overline{K}'). = \mathrm{im}_S(\overline{K}.)$, which
shows that there exists $\Lambda \in \mathcal{R}^{q \times q'}$ such that $\overline{K}' = \overline{K} \Lambda$. Let $\overline{B}' \in \mathcal{S}^{l \times q'}$ be the unique matrix such that $\overline{A K}' = \overline{X}' \overline{B}'$. Using $\overline{A K} = \overline{X} \overline{B}$ and the fact that $X$ has full column rank, we then get:

$$ \overline{X} \overline{W} \overline{B}' = \overline{X}' \overline{B}' = \overline{A K}' = \overline{A K} \Lambda = \overline{X} \overline{B} \Lambda \implies \overline{W} \overline{B}' = \overline{B} \Lambda. $$

If $\mathcal{B}' = \text{coker}_{\mathcal{S}}(\mathcal{B}')$, then we have the following commutative exact diagram of $\mathcal{S}$-modules

$$ \begin{tikzcd} \mathcal{S}^{q' \times 1} \arrow[r, "\overline{B}'"] \arrow[d, "\overline{\Lambda}."] & \mathcal{S}^{l \times 1} \arrow[r, "\sigma'"] \arrow[d, "\overline{W}."] & \mathcal{B}' \arrow[r, "\gamma"] \arrow[d, "\overline{\Lambda}."] & 0 \\ \mathcal{S}^{q \times 1} \arrow[r, "\overline{B}'"] \arrow[d, "\overline{\Lambda}."] & \mathcal{S}^{l \times 1} \arrow[r, "\sigma"] \arrow[d, "\overline{W}."] & \mathcal{B} \arrow[r, "\gamma"] \arrow[d, "\overline{\Lambda}."] & 0, \end{tikzcd} $$

where $\gamma \in \text{hom}_{\mathcal{S}}(\mathcal{B}', \mathcal{B})$ is the $\mathcal{S}$-homomorphism defined by $\gamma(\sigma'(\bar{\mu})) = \sigma(\overline{W}\bar{\mu})$ for all $\bar{\mu} \in \mathcal{S}^{l \times 1}$. Since $W \in \mathbb{K}^{l \times l}$ is an invertible matrix, $\gamma$ is an isomorphism and $\gamma^{-1}(\sigma(\bar{\nu})) = \sigma'(\overline{W}^{-1}\bar{\nu})$ for all $\bar{\nu} \in \mathcal{S}^{l \times 1}$, i.e., $\mathcal{B}' \cong \mathcal{B}$, which yields $\text{Fitt}_i(\mathcal{B}') = \text{Fitt}_i(\mathcal{B})$ for $i = 0, \dots, l$ (see, e.g., [10, 25]), where, using Definition 1, the $\text{Fitt}_i(\mathcal{B})$'s are defined by eq. (40). Hence, these ideals depend only on the matrices $M, D_1, \dots, D_r$, and not particular choices in the construction of the matrix $\overline{B}$. $\square$

Finally, using eq. (40), let us introduce a few more notations that will be used in the next section.

**Definition 3.** We note $\mathcal{I} = \text{Fitt}_0(\mathcal{B})$, i.e., if $l < q$, $\mathcal{I} = \langle 0 \rangle_{\mathcal{S}}$ or if $l \ge q$, $\mathcal{I} = \text{Fitt}_0(\mathcal{B}) = \langle n_1, \dots, n_{\rho} \rangle_{\mathcal{S}}$, where $\{n_i\}_{i=1,\dots,\rho}$ denotes the set formed by all the $l \times l$ minors of the matrix $\overline{B}$ and $\rho = l!(q!(l-q)!)$.

If $\{h_1, \dots, h_\beta\}$ is another set of generators of $\mathcal{I}$, then we shall note $\mathcal{I} = \langle h_1, \dots, h_\beta \rangle_{\mathcal{S}}$, where according to the notation eq. (22), we can write $h_i = \overline{g}_i$ for $g_i \in \mathcal{R}$ and $i = 1, \dots, \beta$.

**Remark 15.** $\mathcal{J}$ is generated by all the $r \times r$ minors of $Q = (L D_1 x \dots L D_r x) \in \mathcal{R}^{p \times r}$, i.e., $\mathcal{J} = \langle 0 \rangle$ if $r > p$ or $\mathcal{J} = \langle e_1, \dots, e_\gamma \rangle$ if $r \le p$, where the $e_i$'s are either homogeneous polynomials of total degree $r$ in the $x_i$'s or all 0. The non-zero entries of $K$ can then be chosen to be homogeneous polynomials. Using $V \in \mathcal{K}^{l \times m}$, the non-zero entries of the matrix $\overline{B} = \overline{V} \overline{A} K$ are then homogeneous polynomials. Finally, if $l < q$, then $\mathcal{I} = \langle 0 \rangle_{\mathcal{S}}$ or if $l \ge q$, $\mathcal{I} = \langle h_1, \dots, h_\beta \rangle_{\mathcal{S}}$, where the $h_i$'s are either homogeneous polynomials in the $\overline{x}_i$'s (and thus, the $g_i$'s are homogeneous polynomials in the $x_i$'s) or all 0.

**Example 9.** We continue Example 8. Let us denote by $\mathcal{B}$ the $\mathcal{S}$-module finitely presented by $\overline{B}$, i.e., $\mathcal{B} = \mathcal{S}/(\overline{B} \mathcal{S}^{3 \times 1}) = \mathcal{S}/(\langle \overline{B}_1, \overline{B}_2, \overline{B}_3 \rangle_{\mathcal{S}})$ where $\overline{B}_i$ stands for the $i^{\text{th}}$ entry of $\overline{B}$. Using $\overline{B}_3 = 3 \overline{B}_1$, we then have $\mathcal{I} = \text{Fitt}_0(\mathcal{B}) = \langle \overline{B}_1, \overline{B}_2 \rangle_{\mathcal{S}}$.

**Remark 16.** Using eq. (11), i.e., $\text{ann}_{\mathcal{S}}(\mathcal{B})^l \subseteq \text{Fitt}_0(\mathcal{B}) \subseteq \text{ann}_{\mathcal{S}}(\mathcal{B})$, we then have $h_i \mathcal{B} = 0$ for $i = 1, \dots, \beta$. Note that $\text{ann}_{\mathcal{S}}(\mathcal{B}) = \langle 0 \rangle$ if and only if $\text{Fitt}_0(\mathcal{B}) = \langle 0 \rangle$ since $\text{ann}_{\mathcal{S}}(\mathcal{B}) \subseteq \sqrt{\text{ann}_{\mathcal{S}}(\mathcal{B})} = \sqrt{\text{Fitt}_0(\mathcal{B})}$.

**Remark 17.** Combining eq. (24) and eq. (39), we get the commutative exact diagram of $\mathcal{R}$-modules

$$ \begin{tikzcd} 0 \arrow[r] & \ker_{\mathcal{S}}(\overline{B}.) \arrow[r, "\overline{B."}'] & \mathcal{S}^{q \times 1} \arrow[r, "\overline{\Lambda."}'] & \mathcal{S}^{l \times 1} \arrow[r, "\sigma."'] & \mathcal{B} \arrow[r, "\overline{\Lambda."}'] & 0, \\ 0 \arrow[r] & \ker_{\mathcal{S}}(\overline{B.}) \arrow[r, "\overline{\Lambda."}'] & \mathcal{S}^{q \times 1} \arrow[r, "\overline{\Lambda."}'] & \mathcal{S}^{l \times 1} \arrow[r, "\sigma."'] & \mathcal{B} \arrow[r, "\overline{\Lambda."}'] & 0, \end{tikzcd} $$

where $I_l \otimes .e$ and $I_q \otimes .e$ are defined by eq. (25). Now, using 4 of Proposition 3.1 of [7]), we have $\mathcal{B} \cong \mathcal{R}^{l \times 1}/(B \mathcal{R}^{q \times 1} + \mathcal{R}^{l \times \gamma}(I_l \otimes .e))$. Using eq. (26), we have $\text{im}_{\mathcal{R}}(I_l \otimes .e) = \text{im}_{\mathcal{R}}((e^T \otimes I_l).)$ (see Section 3.2.2). Thus, as a $\mathcal{R}$-module, $\mathcal{B}$ has the following finite presentation:

$$ \mathcal{B} \cong \mathcal{R}^{l \times 1} / (B \mathcal{R}^{q \times 1} + (e^T \otimes I_l) \mathcal{R}^{l \times \gamma}) = \mathcal{R}^{l \times 1} / ((B \quad e^T \otimes I_l) \mathcal{R}^{(q+l\gamma)\times 1}). \quad (41) $$
Doing similarly as in Section 3.2.2 for the computation of a matrix $\bar{K}$ satisfying $ker_S(\bar{Q}_.) = im_S(\bar{K}_.)$ (see eq. (27)), using 1 of Proposition 3.1 of [7], we then have

$$ker_S(\bar{B}_.) = im_R(C_.)/im_R((e^T \otimes I_q)_.) = im_S(\bar{C}_.),$$

where $C \in \mathbb{R}^{q \times t}$ is such that:

$$ker_R((B \quad e^T \otimes I_l)_.) = im_R\left(\begin{pmatrix} C \\ C' \end{pmatrix}\right).$$

The matrices $C \in \mathbb{R}^{q \times t}$ and $C' \in \mathbb{R}^{l \times t}$ can be computed using, e.g., the **SyzygyModule** command of the **OREMODULES** package. The matrix $\bar{C}$ can also be computed by the **Ker** (resp., **WeakKernelEmbedding**) command of **Singular** (resp., **CapAndHomalg**). Finally, the effective characterization eq. (41) of $\mathcal{B}$ and the computation of $ker_S(\bar{B}_.)$ are implemented in the **RANKFACTORIZATION** package.

Finally, using the notations of Theorem 4, instead of considering $\mathcal{J} = \mathcal{J}_0$, we can repeat the same construction as above with $\mathcal{J}_k, S_k = \mathbb{R}/\mathcal{J}_k$, and $K_k \in \mathbb{R}^{r \times q}$ satisfying $ker_S(\chi_k(Q)) = im_S(\chi_k(K_k))$ for $k = 0, \dots, r-1$ to obtain a matrix $B_k \in \mathbb{R}^{l \times q_k}$ satisfying:

$$\chi_k(A) \chi_k(K_k) = \chi_k(X) \chi_k(B_k) \Leftrightarrow A K_k - X B_k \in \mathcal{J}_k^{m \times q}. \quad (42)$$

Combining this last identity with $V X = I_l$ (see eq. (36)), we then get $V A K_k - B_k \in \mathcal{J}_k^{l \times q}$, and thus, $\chi_k(B_k) = \chi_k(V) \chi_k(A) \chi_k(K_k)$. We can define the finitely presented $S_k$-module $B_k = \text{coker}_{S_k}(\chi_k(B_k))$, which depends only on the matrices $M, D_1, \dots, D_r$. Finally, as for $\mathcal{J} = \mathcal{J}_0$, to simply the notations, we shall set $B_k = V A K_k \in \mathbb{R}^{l \times q_k}$ for $k = 0, \dots, r-1$.

### 3.2.5 Characterization of the existence of a right inverse of B

Let us sum up the results obtained so far. Let us suppose that the rank factorization problem eq. (4) has a solution $(u, v)$, where $M \in \mathbb{K}^{m \times n}$ has not full column rank. As explained at the beginning of Section 3.2.1, if the rows of $L \in \mathbb{K}^{p \times m}$ define a basis of $ker_{\mathbb{K}}(.M)$, then $L A(u) v = 0$, i.e., $v \in ker_{\mathbb{K}}(Q(u))$, where $Q(u) = L A(u)$. Thus, $u \in \mathbb{K}^{m \times 1}$ must be so that $ker_{\mathbb{K}}(Q(u)) \neq 0$, i.e., by Lemma 5, $u \in V_{\mathbb{K}}(\mathcal{J}_0)$. Let $0 \le k \le r-1$ be such that $u \in V_{\mathbb{K}}(\mathcal{J}_k) \setminus V_{\mathbb{K}}(\mathcal{J}_{k+1})$. Then, by Theorem 4, there exists $K_k \in \mathbb{R}^{s \times q}$ satisfying $ker_{\mathbb{K}}(Q(u)) = im_{\mathbb{K}}(K_k(u))$. Hence, $v$ must necessary be of the form of $v = K_k(u) T_u$ for a certain $T_u \in \mathbb{K}^{q_k \times n}$. We then have $A(u) v = A(u) K_k(u) T_u$ and using the identity eq. (42), i.e., $A K_k - X B_k \in \mathcal{J}_k^{m \times q}$, where $B_k \in \mathbb{R}^{l \times q_k}$, we get $A(u) K_k(u) = X B_k(u)$ for all $u \in V_{\mathbb{K}}(\mathcal{J}_k)$, and thus, $A(u) K_k(u) T_u = X B_k(u) T_u = M = XY$, which yields $B_k(u) T_u = Y$ because $X \in \mathbb{K}^{m \times l}$ has full column rank. Hence, if $(u, v)$ is a solution of the rank factorization problem eq. (4), then necessarily $u \in V_{\mathbb{K}}(\mathcal{J}_k)$, $0 \le k \le r-1$, and $v = K_k(u) T_u$ for a matrix $T_u \in \mathbb{K}^{q_k \times n}$ satisfying $B_k(u) T_u = Y$. Conversely, if we consider $u$ and $v$ satisfying these conditions, we then have

$$A(u) v = A(u) K_k(u) T_u = X B_k(u) T_u = XY = M,$$

i.e., $(u, v)$ is a solution of the rank factorization problem eq. (4). Hence, we are led to study the existence of a matrix $T_k \in \mathbb{R}^{q \times m}$ satisfying the following inhomogeneous linear system

$$\chi_k(B_k) \chi_k(T_k) = \chi_k(Y), \quad (43)$$

where $\chi_k: \mathbb{R} \to S_k$ denotes the canonical ring epimorphism, i.e., satisfying $B_k T_k - Y \in \mathcal{J}_k^{l \times n}$.

Again, to simplify the exposition, we shall only consider below the case $S = S_0$, i.e., $\mathcal{J} = \mathcal{J}_0$. The general case exactly follows the same arguments.

More generally, we might want to solve eq. (43), i.e., $\overline{B} \overline{T}_0 = \overline{Y}$, in a different ring than just $S$. To do that, let $\varphi: S \to \mathcal{T}$ be a ring homomorphism. If we note $B_\varphi = \varphi(\overline{B}) \in \mathcal{T}^{l \times q}$ and $Y_\varphi = \varphi(\overline{Y}) \in \mathcal{T}^{l \times n}$, then eq. (43) yields the problem of finding $T \in \mathcal{T}^{q \times m}$ satisfying:

$$B_\varphi T = Y_\varphi. \quad (44)$$

The next lemma shows that the existence of a solution of eq. (44) in $\mathcal{T}$ is equivalent to the existence of a right inverse of $B_\varphi$ with entries in $\mathcal{T}$, namely, the existence of $E \in \mathcal{T}^{q \times l}$ such that $B_\varphi E = I_l$.
**Lemma 7.** With the above notations, the following assertions are equivalent:

1. There exists $T \in \mathcal{T}^{q \times n}$ satisfying $B_{\varphi} T = Y_{\varphi}$.

2. There exists $E \in \mathcal{T}^{q \times l}$ satisfying $B_{\varphi} E = I_l$.

*Proof.* Using the fact that $Y$ has a right inverse $H \in \mathbb{K}^{n \times l}$ (see the proof of Proposition 2), i.e., $Y H = I_l$, we then have $Y_{\varphi} H_{\varphi} = I_l$ where $H_{\varphi} = \varphi(H)$. Point 1 then yields $B_{\varphi}(T H_{\varphi}) = I_l$, which shows that $B_{\varphi}$ has a right inverse with entries in $\mathcal{T}$.

Conversely, if $B_{\varphi}$ has a right inverse $E \in \mathcal{T}^{q \times l}$, then $T = E Y_{\varphi}$ satisfies $B_{\varphi} T = Y_{\varphi}$. $\square$

The next lemma parametrizes all the solutions $T \in \mathcal{T}^{q \times l}$ of $B_{\varphi} T = Y_{\varphi}$.

**Lemma 8.** If $\mathcal{T}$ is a noetherian ring, $C \in \mathcal{T}^{q \times l}$ is such that $\ker_{\mathcal{T}}(B_{\varphi.}) = \text{im}_{\mathcal{T}}(C.)$, $E \in \mathcal{T}^{q \times l}$ is a right inverse of $B_{\varphi}$, then all the solutions $T \in \mathcal{T}^{q \times l}$ of $B_{\varphi} T = Y_{\varphi}$ are given by:

$$ \forall Y' \in \mathcal{T}^{t \times n}, \quad T(Y') = EY_{\varphi} + CY'. \qquad (45) $$

*Proof.* $EY_{\varphi}$ is a particular solution of the inhomogeneous linear system $B_{\varphi} T = Y_{\varphi}$. If $T' \in \mathcal{T}^{q \times l}$ is another solution, then we get $B_{\varphi}(T' - EY_{\varphi}) = 0$, which shows that $\text{im}_{\mathcal{T}}((T' - EY_{\varphi}).) \subseteq \ker_{\mathcal{T}}(B_{\varphi.}) = \ker_{\mathcal{T}}(C.)$, which yields the existence of $Y' \in \mathcal{T}^{t \times l}$ such that $T' - EY_{\varphi} = CY'$, i.e., such as $T' = T(Y')$ for a certain $Y' \in \mathcal{T}^{t \times n}$. Finally, we have $B_{\varphi} T(Y') = B_{\varphi} EY_{\varphi} + B_{\varphi} C Y' = Y_{\varphi}$ for all $Y' \in \mathcal{T}^{t \times n}$, which shows that eq. (45) parametrizes all the solutions of eq. (44) in $\mathcal{T}^{q \times l}$. $\square$

Using Lemma 7 and Lemma 8, we can then reduce the rank factorization problem eq. (4) to the study of the existence of a right inverse of the matrix $B_{\varphi}$. Let us finally study this last problem.

Applying the right exact covariant functor $\mathcal{T} \otimes_S \cdot$ [10, 25] to the exact sequence eq. (39), we obtain the following exact sequence of $\mathcal{T}$-modules:

$$ \mathcal{T}^{q \times 1} \xrightarrow{B_{\varphi.}} \mathcal{T}^{l \times 1} \xrightarrow{\text{id}_{\mathcal{T}} \otimes \sigma} \mathcal{T} \otimes_S \mathcal{B} \longrightarrow 0. \qquad (46) $$

Note that we then have $\mathcal{T} \otimes_S \mathcal{B} \cong \text{coker}_{\mathcal{T}}(B_{\varphi.})$. Thus, $\mathcal{T} \otimes_S \mathcal{B} \cong 0$, i.e., $B_{\varphi} \mathcal{T}^{q \times 1} = \mathcal{T}^{l \times 1}$, if and only if there exists a matrix $E \in \mathcal{T}^{q \times l}$ satisfying $B_{\varphi} E = I_l$, i.e., if and only if the matrix $B_{\varphi}$ has a right inverse with entries in $\mathcal{T}$. Let us now investigate when the $\mathcal{T}$-module $\mathcal{T} \otimes_S \mathcal{B}$ is reduced to 0.

We state again that a prime ideal $\mathfrak{p}$ of $\mathcal{T}$ is an ideal of $\mathcal{T}$ which is such that the factor ring $\mathcal{T}/\mathfrak{p}$ is an integral domain (i.e., $\mathcal{T}/\mathfrak{p}$ has no non-zero zero divisors). A $\mathcal{T}$-module $\mathcal{M}$ is said to be projective of constant rank $r$ if the $\mathcal{M}$-module $\mathcal{M}_{\mathfrak{p}} = \{m/s \mid m \in \mathcal{M}, s \notin \mathfrak{p}\}$ (i.e., the localization of $\mathcal{M}$ at the multiplicatively closed set $S = \mathcal{T} \setminus \mathfrak{p}$) is a free module of rank $r$, i.e., $\mathcal{M}_{\mathfrak{p}} \cong \mathcal{T}_{\mathfrak{p}}^r$, for all prime ideals $\mathfrak{p}$ of $\mathcal{T}$. For more details, see, e.g., [10, 20].

**Proposition 3** (Proposition 20.7, [10]). A finitely presented $\mathcal{T}$-module $\mathcal{M}$ is projective of constant rank $r$ if and only if $\text{Fitt}_r(\mathcal{M}) = \mathcal{T}$ and $\text{Fitt}_{r-1}(\mathcal{M}) = \langle 0 \rangle$.

Note that the zero module is a projective $\mathcal{T}$-module of rank 0. Hence, Proposition 3 shows that $\mathcal{T} \otimes_S \mathcal{B} \cong \text{coker}_{\mathcal{T}}(B_{\varphi.}) = 0$ if and only if $\text{Fitt}_0(\text{coker}_{\mathcal{T}}(B_{\varphi.})) = \mathcal{T}$.

The next proposition is a direct consequence of the right exactness of the covariant functor $\mathcal{T} \otimes_S \cdot$.

**Proposition 4** (Corollary 20.5 of [10]). Let $\varphi : S \to \mathcal{T}$ be a ring homomorphism and $\mathcal{L}$ a finitely presented $\mathcal{S}$-module. Then, we have $\text{Fitt}_i(\mathcal{T} \otimes_S \mathcal{L}) = \mathcal{T} \otimes_S \text{Fitt}_i(\mathcal{L})$ for all $i \ge 0$, where $\mathcal{T} \otimes_S \text{Fitt}_i(\mathcal{L})$ denotes the ideal of $\mathcal{T}$ generated by $\varphi(\text{Fitt}_i(\mathcal{L}))$, i.e., by the images of the generators of $\text{Fitt}_i(\mathcal{L})$ by $\varphi$.

The next result studies when the matrix $B_{\varphi}$ has a right inverse with entries in $\mathcal{T}$.

**Corollary 4.** With the above notations, let $\mathcal{I} = \text{Fitt}_0(\mathcal{B}) = \langle h_1, \dots, h_{\beta} \rangle_S$ be the ideal of $\mathcal{S}$ defined by all the $l \times l$ minors of $\bar{B}$, where $h_i \in \mathcal{S}$ for $i = 1, \dots, \beta$. Then, the matrix $B_{\varphi} \in \mathcal{T}^{l \times q}$ has a right inverse with entries in $\mathcal{T}$ if and only if $\langle \varphi(h_1), \dots, \varphi(h_{\beta}) \rangle_{\mathcal{T}} = \mathcal{T}$, i.e., if and only if there exist $t_i \in \mathcal{T}$, $i = 1, \dots, \beta$, satisfying the following Bézout equation:

$$ \sum_{i=1}^{\beta} t_i \varphi(h_i) = 1. \qquad (47) $$

Finally, if $\mathcal{I} = \langle 0 \rangle_S$, then the matrix $B_{\varphi}$ has no right inverses for all non-trivial rings $\mathcal{T}$.
Proof. Using Proposition 4, $\mathcal{T} \otimes_S \mathcal{B} \cong \text{coker}_{\mathcal{T}}(B_{\varphi.}) = 0$ if and only if:

$$ \text{Fitt}_0(\text{coker}_{\mathcal{T}}(B_{\varphi.})) = \mathcal{T} \otimes_S \text{Fitt}_0(\text{coker}_{\mathcal{S}}(\bar{B}.))) = \mathcal{T} \otimes_S \text{Fitt}_0(\mathcal{B}) = \varphi(\text{Fitt}_0(\mathcal{B})) = \mathcal{T}. $$

The last equality is equivalent to the Bézout equation eq. (47). Finally, if $\mathcal{I} = \langle 0 \rangle_S$, then $\varphi(\mathcal{I}) = \langle 0 \rangle_{\mathcal{T}}$ for all ring homomorphisms $\varphi: \mathcal{S} \to \mathcal{T}$. Hence, if $\mathcal{T}$ is a non-trivial ring, we cannot have $\mathcal{T} = \langle 0 \rangle_{\mathcal{T}}$. $\square$

In what follows, we shall suppose that $\mathcal{I} \neq \langle 0 \rangle_S$ and all the $h_i$'s are not 0.

Let us first study Corollary 4 in the case of $\mathcal{T} = \mathcal{S}$. According to Section 3.2.2, we have $\mathcal{S} = \mathcal{R}/\mathcal{J}$, $\mathcal{R} = \mathbb{K}[x_1, \dots, x_m]$, and $\mathcal{J} = \text{Fitt}_0(\mathcal{Q}) = \langle e_1, \dots, e_\gamma \rangle$. Writing $h_i = \bar{g}_i$ and $t_i = \bar{r}_i$, where $g_i, r_i \in \mathcal{R}$ for $i = 1, \dots, \beta$, eq. (47) is equivalent to the existence of $r'_1, \dots, r'_\gamma \in \mathcal{R}$ such that $\sum_{i=1}^\beta r_i g_i + \sum_{j=1}^\gamma r'_j e_j = 1$, i.e., $\langle g_1, \dots, g_\beta \rangle + \langle e_1, \dots, e_\gamma \rangle = \mathcal{R}$. Using Gröbner basis methods, the above Bézout identity can be effectively checked and the $r_i$'s, and thus, the $t_i$'s satisfying eq. (47), computed. Therefore, eq. (47) can be effectively tested for $\mathcal{T} = \mathcal{S}$ using standard effective elimination methods (see, e.g., [10, 12]).

Let us now suppose that eq. (47) holds in $\mathcal{T} = \mathcal{S}$. In this case, note that $\text{Fitt}_0(\mathcal{B}) = \langle 0 \rangle_S$ if and only if $\mathcal{B} = 0$. Then, using eq. (41), $\mathcal{B} = 0$ if and only if $(\mathcal{B} \ e^T \otimes I_l) \mathcal{R}^{(q+l\gamma)\times l} = \mathcal{R}^{l\times l}$, i.e., if and only if $(\mathcal{B} \ e^T \otimes I_l)$ has a right inverse with entries in $\mathcal{R}$. Using Gröbner basis methods, this last problem can be effectively solved (see, e.g., [5]). See the RightInverse command of the OREMODULES package [6] or the PreInverse command of the CapAndHomalg library [1]. Hence, two matrices $E \in \mathcal{R}^{q \times l}$ and $E' \in \mathcal{R}^{l \times q \times l}$ can be obtained satisfying $\mathcal{B}E + (e^T \otimes I_l)E' = I_l$, which yields $\bar{\mathcal{B}}\bar{E} = I_l$, where $\bar{E} = \chi(E)$. Hence, we have $\mathcal{B}(u)E(u) = I_l$ for all $u \in \mathcal{V}_{\mathcal{K}}(\mathcal{J})$. Using Lemma 8, where the matrix $C \in \mathcal{R}^{q \times t}$ is such that $\text{ker}_S(\bar{\mathcal{B}}.) = \text{im}_S(\bar{\mathcal{C}}.)$ (see also Remark 17), then $\{T(Y') = \bar{E}\bar{Y} + \bar{C}Y' \mid \forall Y' \in \mathcal{T}^{t \times n}\}$ parametrizes all the solutions of $\bar{\mathcal{B}}T = \bar{Y}$ in $\mathcal{S}^{q \times l}$. Hence, the solutions of the rank factorization problem eq. (4) are then parametrized as follows:

$$ \left\{ \begin{array}{l} u \in \mathcal{V}_{\mathcal{K}}(\mathcal{J}), \\ v(u, Y') = K(u) (E(u)Y + C(u)Y'(u)), \quad \forall Y' \in \mathcal{S}^{t \times n}. \end{array} \right. $$

Note that $\mathbb{K}^{t \times n} \subset \mathcal{S}^{t \times n}$ and $Y'(u) \in \mathbb{K}^{t \times n}$ for all $u \in \mathcal{V}_{\mathcal{K}}(\mathcal{J})$ and for all $Y' \in \mathcal{S}^{t \times n}$, which shows that the above parametrization is also defined as follows:

$$ \left\{ \begin{array}{l} u \in \mathcal{V}_{\mathcal{K}}(\mathcal{J}), \\ v(u, Y') = K(u) (E(u)Y + C(u)Y'), \quad \forall Y' \in \mathbb{K}^{t \times n}. \end{array} \right. \qquad (48) $$

Hence, if eq. (47) has a solution in $\mathcal{S}$, then we can obtain the above explicit parametrization of solutions of the rank factorization problem eq. (4). Using Remark 15, we know that the $h_i$'s and the $e_j$'s are either homogeneous polynomials or 0. Therefore, 0 is a common zero of the $h_i$'s and the $e_j$'s, which shows that eq. (47) does not hold in $\mathcal{S}$, and thus, the solutions of Problem eq. (4) cannot simply be parametrized by a single closed-form of the form eq. (48).

**Example 10.** We continue Example 9. We have $\mathcal{I} = \langle \bar{B}_1, \bar{B}_2 \rangle_S$, i.e., $\bar{g}_1 = \bar{B}_1$ and $\bar{g}_2 = \bar{B}_2$, where $g_1 = 5x_2x_4/2 + x_3x_4$ and $g_2 = 3x_1x_3 + x_3x_4$. Considering $e_1, e_2$, and $e_3$ defined in Example 5, we can check again that $(0000)^T$ is a common zero of the polynomials $g_1, g_2, e_1, e_2$, and $e_3$, which shows that $1 \notin \langle g_1, g_2, e_1, e_2, e_3 \rangle$ and proves that $\bar{B}$ has no right inverse with entries in $\mathcal{S}$ by Corollary 4.

### 3.2.6 Solutions of the rank factorization problem

Since eq. (47) has no solutions in $\mathcal{S}$, in this section, we seek the solutions of eq. (47) in a different ring $\mathcal{T}$.

We suppose that at least one of the generators of $\mathcal{I} = \langle h_1, \dots, h_\beta \rangle_S$, say $h_i$, is not a nilpotent element of $\mathcal{S}$, i.e., $h_i^k \neq 0$ for all $k \in \mathbb{Z}_{\ge 0}$. We can consider the non-trivial ring $\mathcal{S}_{h_i} = \{s/h_i^k \mid s \in \mathcal{S}, k \in \mathbb{Z}_{\ge 0}\}$ defined as the localization of $\mathcal{S}$ at the multiplicatively closed set $\{h_i^k\}_{k \in \mathbb{Z}_{\ge 0}}$ and the canonical ring homomorphism $j_{h_i}: \mathcal{S} \to \mathcal{S}_{h_i}$ defined by $j_{h_i}(s) = s/1$ for all $s \in \mathcal{S}$, whose kernel $\text{ker} \ j_{h_i} = \{s \in \mathcal{S} \mid \exists k \in \mathbb{Z}_{\ge 0}: h_i^k s = 0\}$ (see, e.g., [10, 25]). Then, we have $j_{h_i}(h_j) = h_j/1$ for $j = 1, \dots, \beta$ and $j_{h_i}(h_i) = h_i/1 \neq 0/1$ because $h_i$ is not a nilpotent element of $\mathcal{S}$. If we set $t_i = (h_i/1)^{-1} \in \mathcal{S}_{h_i}$ and $t_j = 0/1$ for $j \neq i$, then $(t_1, \dots, t_\beta)$ is a solution of eq. (47) in $\mathcal{S}_{h_i}$, which shows that $j_{h_i}(\bar{B}) = B_{h_i}$ has a right inverse with entries in $\mathcal{S}_{h_i}$.
Let $E \in S_{h_i}^{q \times l}$ be a right inverse of $B_{h_i}$. Writing $E_{h_i} = E'_{h_i}/h_i^a$, where $E'_{h_i} \in S^{q \times l}$ and $a \in \mathbb{Z}_{\ge 0}$, then $B_{h_i} E_{h_i} = I_l$ is equivalent to $B_{h_i} E'_{h_i} - h_i^a I_l = 0$ in $S_{h_i}^{l \times l}$, and thus, to $h_i^b (\overline{B} E'_{h_i} - h_i^a I_l) = 0$ in $S^{l \times l}$ for a certain $b \in \mathbb{Z}_{\ge 0}$. Writing $h_i = \overline{g_i}$ and $E'_{h_i} = \chi(E''_{h_i})$, where $E''_{h_i} \in \mathbb{R}^{q \times l}$, i.e., $E'_{h_i} = \overline{E''_{h_i}}$, then the last identity is equivalent to:

$$g_i^b (B E''_{h_i} - g_i^a I_l) \in \mathcal{J}^{l \times l}. \qquad (49)$$

Using eq. (49), we then obtain:

$$\forall u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}), \quad g_i(u)^b (B(u) E''_{h_i}(u) - g_i(u)^a I_l) = 0.$$

Hence, if $g_i(u) \neq 0$, then $E''_{h_i}(u)/g_i(u)^a$ is a right inverse of the matrix $B(u)$.

If $\mathbb{K}$ is an algebraically closed field of characteristic 0, using Hilbert's Nullstellensatz, the condition $\mathcal{V}_{\mathbb{K}}(\mathcal{J}) \subseteq \mathcal{V}_{\mathbb{K}}(\langle g_i \rangle)$, i.e., $g_i(u) = 0$ for all $u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J})$, is equivalent to $\langle g_i \rangle \subseteq \sqrt{\langle g_i \rangle} \subseteq \sqrt{\mathcal{J}}$, and thus, to $g_i^k \in \mathcal{J}$ for a certain $k \in \mathbb{Z}_{\ge 0}$, i.e., to $h_i^k = 0$, i.e., $h_i$ is a nilpotent element of $S$. We state again that $\mathbb{K}$ is supposed to be of characteristic 0. Hence, if $\mathbb{K}$ is an algebraically closed field and $h_i$ is not an idempotent element of $S$, then there exists $u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J})$ such that $g_i(u) \neq 0$. Thus, a right inverse of $E$ of $B_{h_i}$ exist "locally", i.e., for all $u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J})$ satisfying $g_i(u) \neq 0$ but not "globally", i.e., not for all $u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J})$.

**Proposition 5.** With the above notations, let $\text{Fitt}_0(\mathcal{B}) = \langle h_1, \dots, h_\beta \rangle_S$. If $h_i$ is not a nilpotent element of $S$, then $B_{h_i}$ has a right inverse $E_{h_i} \in S_{h_i}^{q \times l}$, i.e., $B_{h_i} E_{h_i} = I_l$, where $S_{h_i} = \{s/h_i^k \mid s \in S, k \in \mathbb{Z}_{\ge 0}\}$ denotes the localization of $S$ at the multiplicatively closed set $\{h_i^k\}_{k \in \mathbb{Z}_{\ge 0}}$.

Moreover, there exist two matrices $C_{h_i} \in S_{h_i}^{q \times t}$ and $F_{h_i} \in S_{h_i}^{t \times q}$ satisfying:

$$\ker_{S_{h_i}} (B_{h_i}.) = \text{im}_{S_{h_i}} (C_{h_i}.), \quad C_{h_i} F_{h_i} + E_{h_i} B_{h_i} = I_q. \qquad (50)$$

Finally, all the right inverses of the matrix $B_{h_i}$ with entries in $S_{h_i}$ are of the form:

$$\forall Q \in S_{h_i}^{t \times l}, \quad E_{h_i}(Q) = E_{h_i} + C_{h_i} Q. \qquad (51)$$

*Proof.* Let $S_{h_i} = \{s/h_i^k \mid s \in S, k \in \mathbb{Z}_{\ge 0}\}$ and $S_{h_i}^{-1}\mathcal{B} = \{b/h_i^k \mid b \in \mathcal{B}, k \in \mathbb{Z}_{\ge 0}\}$ the $S_{h_i}$-module defined by the localization of $\mathcal{B}$ at $\{h_i^k\}_{k \in \mathbb{Z}_{\ge 0}}$. Using Remark 16, we have $h_i \mathcal{B} = 0$, and thus, $S_{h_i}^{-1}\mathcal{B} = 0$, i.e., $B_{h_i} S_{h_i}^{q \times 1} = S_{h_i}^{l \times 1}$, which proves the existence of $E_{h_i} \in S_{h_i}^{q \times l}$ satisfying $B_{h_i} E_{h_i} = I_l$.

Now, using the fact that $S_{h_i}$ is a noetherian ring (see, e.g., [10, 25]), $\ker_{S_{h_i}}(B_{h_i}.)$ is a finitely generated $S_{h_i}$-module, and thus, there exist $t \in \mathbb{Z}_{\ge 0}$ and $C_{h_i} \in S_{h_i}^{q \times t}$ such that $\ker_{S_{h_i}}(B_{h_i}.) = \text{im}_{S_{h_i}}(C_{h_i}.)$.

Setting $\Pi = I_q - E_{h_i} B_{h_i} \in S_{h_i}^{q \times q}$, we have $B_{h_i} \Pi = 0$, i.e., $\text{im}_{S_{h_i}}(\Pi) \subseteq \ker_{S_{h_i}}(B_{h_i}.) = \text{im}_{S_{h_i}}(C_{h_i}.)$, which shows that there exists $F_{h_i} \in S_{h_i}^{t \times q}$ satisfying $\Pi = C_{h_i} F_{h_i}$, i.e., $C_{h_i} F_{h_i} + E_{h_i} B_{h_i} = I_q$.

Now, let $E'_{h_i} \in S_{h_i}^{q \times l}$ be a second right inverse of $\overline{B}$, i.e., $B_{h_i} E'_{h_i} = I_l$. Then, $B_{h_i} (E'_{h_i} - E_{h_i}) = 0$, i.e., $\text{im}_{S_{h_i}}((E'_{h_i} - E_{h_i}).) \subseteq \ker_{S_{h_i}}(B_{h_i}.) = \text{im}_{S_{h_i}}(C_{h_i}.)$, which shows that there exists $Q \in S_{h_i}^{t \times l}$ such that $E'_{h_i} - E_{h_i} = C_{h_i} Q$, i.e., using eq. (51), such that $E'_{h_i} = E_{h_i}(Q)$.

Finally, we have $B_{h_i} E_{h_i}(Q) = B_{h_i} E_{h_i} + (B_{h_i} C_{h_i}) Q = I_l$ for all $Q \in S_{h_i}^{t \times l}$, which finally proves that eq. (51) parametrizes all the right inverses of $B_{h_i}$ with entries in the ring $S_{h_i}$. $\square$

**Remark 18.** Using the fact that $S_{h_i}$ is a flat $S$-module (see, e.g., [10, 25]), applying the exact functor $S_{h_i} \otimes_S \cdot$ to eq. (39), we obtain the following split exact sequence of $S_{h_i}$-modules (see, e.g., [10, 25])

$$S_{h_i}^{t \times 1} \underset{F_{h_i} .}{\overset{C_{h_i} .}{\rightleftharpoons}} S_{h_i}^{q \times 1} \underset{E_{h_i} .}{\overset{B_{h_i} .}{\rightleftharpoons}} S_{h_i}^{l \times 1} \longrightarrow S_{h_i}^{-1} \mathcal{B} = 0,$$

where $C_{h_i} \in S_{h_i}^{q \times t}$ and $F_{h_i} \in S_{h_i}^{t \times q}$ satisfy eq. (50), which gives another proof of Proposition 5.

Using Lemma 8 with $\mathcal{T} = S_{h_i}$, all the solutions $T \in S_{h_i}^{q \times n}$ of $B_{h_i} T = \overline{Y}$ are defined by:

$$\forall Y' \in S_{h_i}^{t \times n}, \quad T_{h_i}(Y') = E_{h_i} \overline{Y} + C_{h_i} Y'$$
If all the $h_i$'s are nilpotent elements, then the ideal $\mathcal{I} = \langle h_1, \dots, h_\beta \rangle_S$ is nilpotent, namely, there exists $N \in \mathbb{Z}_{>0}$ such that $\mathcal{I}^N = 0$ (if $h_i^{\nu_i} = 0$ for $i = 1, \dots, \beta$, then we can take $N = \nu_1 + \dots + \nu_\beta$). Conversely, if $\mathcal{I}$ is a nilpotent ideal of $S$, then the $h_i$'s are idempotent elements of $S$. Hence, if $\mathcal{I}$ is a nilpotent ideal of $S$, then $\mathcal{I} = \emptyset$ and the rank factorization problem eq. (4) has no solutions.

More generally, if $\mathcal{I}$ is nilpotent and $\varphi : \mathcal{S} \to \mathcal{T}$ is a ring homomorphism, then the ideal $\varphi(\mathcal{I}) = \langle \varphi(h_1), \dots, \varphi(h_\beta) \rangle_{\mathcal{T}}$ of $\mathcal{T}$ is nilpotent. According to Corollary 4, the rank factorization problem eq. (4) has a solution in $\mathcal{T}$ if and only if $\varphi(\mathcal{I}) = \mathcal{T}$. This last condition implies that there exists $N \in \mathbb{Z}_{>0}$ such that $\mathcal{T}^N = 0$. In particular, we have $1^N = 0$ (equivalently, take the $N^{\text{th}}$ power of eq. (47)), which yields $1 = 0$ in $\mathcal{T}$, i.e., $\mathcal{T}$ is the trivial ring and the rank factorization problem eq. (4) has no solutions in $\mathcal{T}$.

**Remark 19.** If $\mathbb{K}$ is an algebraically closed field, then the smallest affine algebraic set containing the set $\mathcal{V}_{\mathbb{K}}(\mathcal{J}) \setminus \mathcal{V}_{\mathbb{K}}(\langle g_i \rangle)$, namely, its Zariski closure $\overline{\mathcal{V}_{\mathbb{K}}(\mathcal{J})} \setminus \mathcal{V}_{\mathbb{K}}(\langle g_i \rangle)$, is defined by

$$ \overline{\mathcal{V}_{\mathbb{K}}(\mathcal{J}) \setminus \mathcal{V}_{\mathbb{K}}(\langle g_i \rangle)} = \mathcal{V}_{\mathbb{K}}(\mathcal{J} : \langle g_i \rangle^{\infty}), \qquad (55) $$

where $\mathcal{J} : \langle g_i \rangle^{\infty}$ denotes the saturation of $\mathcal{J}$ with respect to $\langle g_i \rangle$ defined by:

$$ \mathcal{J} : \langle g_i \rangle^{\infty} = \{ a \in \mathbb{R} \mid \exists k \in \mathbb{Z}_{\ge 0} : a g_i^k \in \mathcal{J} \}. $$

For more details, see, e.g., [10, 20]. Now, using that $h_i$ is not a nilpotent of $S$, i.e., $g_i^k \notin \mathcal{J}$ for all $k \in \mathbb{Z}_{\ge 0}$, then $1 \notin \mathcal{J} : \langle g_i \rangle^{\infty}$, i.e., $\mathcal{J} : \langle g_i \rangle^{\infty}$ is not equal to $\mathbb{R}$, which yields $\overline{\mathcal{V}_{\mathbb{K}}(\mathcal{J})} \setminus \mathcal{V}_{\mathbb{K}}(\langle g_i \rangle) \neq \emptyset$.

Finally, if $\mathbb{R}[t]$ is the polynomial ring $\mathbb{K}[x_1, \dots, x_m, t]$ and $\mathbb{R}[t] \mathcal{J} = \langle g_1, \dots, g_\gamma \rangle_{\mathbb{R}[t]}$ is the ideal of $\mathbb{R}[t]$ generated by $\mathcal{J}$, then $\mathcal{J} : \langle g_i \rangle^{\infty}$ can be characterized as follows:

$$ \mathcal{J} : \langle g_i \rangle^{\infty} = \langle g_1, \dots, g_\gamma, t g_i - 1 \rangle_{\mathbb{R}[t]} \cap \mathbb{R}. \qquad (56) $$

See, e.g., [10, 12]. Finally, eq. (56) can be computed by a Gröbner basis computation.

We can now sum up the main result of the paper.

**Theorem 5.** Let $D_i \in \mathbb{K}^{m \times m}$ for $i = 1, \dots, r$ and $M \in \mathbb{K}^{m \times n}$ be such that:

$$ 1 \le l = \text{rank}_{\mathbb{K}}(M) \le \min\{m, r\}. $$

Let $X \in \mathbb{K}^{m \times l}$ be a full column rank matrix such that $\text{im}_{\mathbb{K}}(M.) = \text{im}_{\mathbb{K}}(X.)$, i.e., the columns of $X$ define a basis of $\text{im}_{\mathbb{K}}(M.)$. Let $V \in \mathbb{K}^{l \times m}$ be any left inverse of $X$. Moreover, let $Y \in \mathbb{K}^{l \times n}$ be such that $M = XY$. Hence, we have $\text{ker}_{\mathbb{K}}(M.) = \text{ker}_{\mathbb{K}}(Y.)$ and $Y$ has full row rank.

Let $L \in \mathbb{K}^{(m-l) \times m}$ be a full row matrix whose rows define a basis of $\text{ker}_{\mathbb{K}}(M.)$ (with the convention that $L = 0$ if $l = m$), $\mathcal{R} = \mathbb{K}[x_1, \dots, x_m]$, $A = (x_1 \dots x_m)^T$, $A = (D_1 x \dots D_r x) \in \mathcal{R}^{m \times r}$, $Q = LA \in \mathcal{R}^{p \times r}$, $Q = \mathcal{R}^{1 \times r} / (\mathcal{R}^{1 \times p} Q)$, $\mathcal{J} = \text{Fitt}_0(Q)$ the $0^{\text{th}}$ Fitting ideal of the $\mathcal{R}$-module $Q$ ($\mathcal{J} = \langle 0 \rangle$ if $r > p$ or if $l = m$), $S = \mathcal{R}/\mathcal{J}$, $\chi : \mathcal{R} \to \mathcal{S}$ the canonical ring epimorphism, and $\overline{H} = \chi(H)$ for all $H \in \mathcal{R}^{a \times b}$. Then, we have $\text{ker}_S(\overline{Q.}) \neq 0$.

Let $K \in \mathcal{R}^{r \times q}$ be such that $\text{ker}_S(\overline{Q.}) = \text{im}_S(\overline{K.})$, $B = VAK \in \mathcal{R}^{l \times q}$, $B = S^{l \times 1} / (\overline{B} S^{q \times 1})$ be the $S$-module finitely presented by $\overline{B}$, and $\mathcal{I} = \text{Fitt}_0(B) = \langle h_1, \dots, h_\beta \rangle_S$.

If $\mathcal{I}$ is a nilpotent ideal of $S$, then the rank factorization problem eq. (4) has no solution.

If $\mathbb{K}$ is an algebraically closed field, then rank factorization problem eq. (4) has no solution if and only if $\mathcal{I}$ is a nilpotent ideal of $S$.

Finally, let $h_i = \overline{g_i}$, where $g_i \in \mathcal{R}$, $\mathcal{I}_{\mathcal{R}} = \langle g_1, \dots, g_\beta \rangle_{\mathcal{R}}$ be the ideal of $\mathcal{R}$ generated by the $g_i$'s, $I = \{i \in [1, \dots, \beta] \mid g_i \notin \sqrt{\mathcal{J}}\}$, and $\mathcal{U}_{g_i} = \mathcal{V}_{\mathbb{K}}(\mathcal{J}) \setminus \mathcal{V}_{\mathbb{K}}(\langle g_i \rangle)$ for $i \in I$. If $I \neq \emptyset$, then solutions $(u, v)$ of the rank factorization problem eq. (4) are defined by

$$ u \in \mathcal{U} = \bigcup_{i \in I} \mathcal{U}_{g_i}, \\ \forall i \in I, \quad \left\{ \begin{array}{l} u \in \mathcal{U}_{g_i}, \\ v_{h_i}(u, Y') = K(u) (E_{h_i}(u) Y + C_{h_i}(u) Y'), \forall Y' \in \mathbb{K}^{t_i \times n}, \end{array} \right. \qquad (57) $$

where $E_{h_i} \in \mathcal{S}_{h_i}^{q \times l}$ is a right inverse of $B_{h_i} = j_{h_i}(\overline{B})$, i.e., $B_{h_i} E_{h_i} = I_l$, $C_{h_i} \in \mathcal{S}_{h_i}^{q \times t_i}$ is such that $\text{ker}_{S_{h_i}}(B_{h_i}) = \text{im}_{S_{h_i}}(C_{h_i})$, and $j_{h_i} : S \to S_{h_i}$ is the canonical ring homomorphism from $S$ to its localization $S_{h_i} = \{s/h_i^k \mid s \in S, k \in \mathbb{Z}_{\ge 0}\}$ at the multiplicatively set $\{h_i^k \mid k \in \mathbb{Z}_{\ge 0}\}$.
**Remark 20.** The results of Section 3.1 obtained for a full column rank matrix $M$ can be seen as a particular case of Theorem 5. Indeed, if $M$ has full row rank, then $L = 0$ and $X = I_m$, which yields $Q = LA = 0$ and $\ker_R(Q) = \mathcal{R}^{r \times 1}$, i.e., $K = I_r$, and thus, $B = A$, $B = A$, $Q = \text{coker}_R(Q) = \mathcal{R}^{1 \times r}$, $\mathcal{J} = \text{Fitt}_0(Q) \subseteq \text{ann}_R(Q) = \langle 0 \rangle$, i.e., $\mathcal{J} = \langle 0 \rangle$, $S = \mathcal{R}$, $\mathcal{I} = \text{Fitt}_0(B) = \text{Fitt}_0(A)$, and:

$$ U = \mathcal{V}_{\mathcal{K}}(\mathcal{J}) \setminus \mathcal{V}_{\mathcal{K}}(\mathcal{I}) = \mathcal{K}^{m \times 1} \setminus \mathcal{V}_{\mathcal{K}}(\mathcal{I}), \quad \mathcal{I} = \mathcal{I}_{\mathcal{R}} = \text{Fitt}_0(A) = \langle h_1, \dots, h_{\beta} \rangle, \quad h_i \in \mathcal{R}, i = 1, \dots, \beta. $$

Thus, Problem eq. (4) has a solution if and only if $\mathcal{V}_{\mathcal{K}}(\mathcal{I}) \neq \mathcal{K}^{m \times 1}$. Finally, in the case of an infinite algebraic closed field $\mathcal{K}$, $\mathcal{V}_{\mathcal{K}}(\mathcal{I}) \neq \mathcal{K}^{m \times 1}$ is equivalent to $\mathcal{I} \neq \langle 0 \rangle$.

Let us now explain how to effectively check whether or not $h_i$ is a nilpotent element of $S$ and how the matrices $C_{h_i}$, $E_{h_i}$, and $F_{h_i}$ can be computed.

Let us start with recognizing nilpotent elements of $S$. As stated again at the beginning of the section, the kernel of the canonical ring homomorphism $j_{h_i}: S \to S_{h_i}$, defined by $j_{h_i}(s) = s/1$ for all $s \in S$, is defined by $\ker j_{h_i} = \{s \in S \mid \exists k \in \mathbb{Z}_{\ge 0}: h_i^k s = 0\}$ (see, e.g., [10, 25]). Hence, $S_{h_i}$ is the trivial ring if and only if $1 \in \ker j_{h_i}$, i.e., if and only if $h_i$ is nilpotent. To test whether or not $S_{h_i}$ is the trivial ring, we shall need the following standard lemma.

**Lemma 9.** Let $\mathcal{R}_{g_i} = \mathbb{K}[x_1, \dots, x_m, g_i^{-1}] = \{a/g_i^k \mid a \in \mathcal{R}, k \in \mathbb{Z}_{\ge 0}\}$ be the localization of $\mathcal{R}$ at the multiplicatively closed set $\{g_i^k\}_{k \in \mathbb{Z}_{\ge 0}}$, $\mathcal{J} = \langle e_1, \dots, e_\gamma \rangle$ an ideal of $\mathcal{R}$, $S = \mathcal{R}/\mathcal{J}$, $h_i = \overline{h_i}$, $S_{h_i}$ the localization of $S$ at the multiplicatively closed set $\{h_i^k\}_{k \in \mathbb{Z}_{\ge 0}}$, and $\mathcal{J}_{g_i}$ the ideal of $\mathcal{R}_{g_i}$ generated by $\mathcal{J}$, i.e., $\mathcal{J}_{g_i} = \langle e_1, \dots, e_\gamma \rangle_{\mathcal{R}_{g_i}}$. Then, the map $\rho: S_{h_i} \to \mathcal{R}_{g_i}/\mathcal{J}_{g_i}$ defined by

$$ \forall s = r + \mathcal{J} \in S, \quad r \in \mathcal{R}, \quad \rho\left(\frac{s}{h_i^k}\right) = \rho\left(\frac{r + \mathcal{J}}{g_i^k + \mathcal{J}}\right) = \frac{r}{g_i^k} + \mathcal{J}_{g_i} $$

is a ring isomorphism, i.e., $S_{h_i} \cong \mathcal{R}_{g_i}/\mathcal{J}_{g_i}$.

*Proof.* See, e.g., Rule 4.16 on page 83 of [20]. □

Using Lemma 9, let us now characterize $\mathcal{R}_{g_i}/\mathcal{J}_{g_i}$. We have $\mathcal{R}_{g_i} = \mathcal{R}[y]/\langle y g_i - 1 \rangle$ and the following exact sequence of $\mathcal{R}[y]$-modules:

$$ 0 \longrightarrow \mathcal{R}[y] \xrightarrow{(y g_i - 1)} \mathcal{R}[y] \xrightarrow{\vartheta} \mathcal{R}_{g_i} \longrightarrow 0. $$

Let $e = (e_1 \dots e_\gamma)^T \in \mathcal{R}^{\gamma \times 1}$ and $j_{g_i}: \mathcal{R} \to \mathcal{R}_{g_i}$ be the canonical ring homomorphism defined by $j_{g_i}(a) = a/1$ for all $a \in \mathcal{R}$. Using the fact that $\mathcal{R}$ is an integral domain, we get $\ker j_{g_i} = 0$, and identifying $e_i$ with $e_i/1$ in $\mathcal{R}_{g_i}$, we have the following finite presentation of the $\mathcal{R}_{g_i}$-module $\mathcal{R}_{g_i}/\mathcal{J}_{g_i}$:

$$ \mathcal{R}_{g_i}^{1 \times \gamma} \xrightarrow{\cdot e} \mathcal{R}_{g_i} \xrightarrow{\varpi} \mathcal{R}_{g_i}/\mathcal{J}_{g_i} \longrightarrow 0. $$

Combining the last exact sequences, we obtain the following commutative exact diagram of $\mathcal{R}[y]$-modules:

<figure><img src="image_6.png" /></figure>

Using Lemma 9 and 4 of Proposition 3.1 of [7]), we then have:

$$ S_{h_i} \cong \mathcal{R}_{g_i}/\mathcal{J}_{g_i} \cong \mathcal{R}[y] / \left( (y g_i - 1) \mathcal{R}[y] + \mathcal{R}[y]^{1 \times \gamma} e \right) = \mathcal{R}[y] / \langle y g_i - 1, e_1, \dots, e_\gamma \rangle_{\mathcal{R}[y]}. \quad (58) $$

Therefore, $h_i$ is a nilpotent element of $S$ if and only if $\langle y g_i - 1, e_1, \dots, e_\gamma \rangle_{\mathcal{R}[y]} = \mathcal{R}[y]$, i.e., if and only if $1 \in \langle y g_i - 1, e_1, \dots, e_\gamma \rangle_{\mathcal{R}[y]}$, a result that can be checked by a Gröbner basis computation.
**Example 11.** If $\mathcal{R} = \mathbb{K}[x]$, $e = x^2$, and $g_i = x$, then $\mathcal{J} = \langle x^2 \rangle$, $\mathcal{S} = \mathbb{K}[x]/\langle x^2 \rangle$, $\mathcal{R}_x = \mathbb{K}[x, y]/\langle yx - 1 \rangle$, $\mathcal{J}_x = \mathcal{R}_x x^2$, and $\mathcal{S}_{\bar{x}} \cong \mathbb{K}[x, y]/\langle yx - 1, x^2 \rangle$. We can check that $1 \in \langle yx - 1, x^2 \rangle$ because we have $-(xy + 1)(yx - 1) + y^2 x^2 = 1$. Therefore, $\mathcal{S}_{\bar{x}} = 0$ and $\bar{x}$ is a nilpotent element of $\mathcal{S}$.

Using eq. (41) and writing $h_i = \bar{g}_i$, where $g_i \in \mathcal{R}$, $h_i \mathcal{S} = 0$ is then equivalent to the existence of two matrices $D \in \mathcal{R}^{q \times l}$ and $D' \in \mathcal{R}^{l \times q}$ satisfying:

$$g_i I_l = (B \quad e^T \otimes I_l) \begin{pmatrix} D \\ D' \end{pmatrix} = B D + (e^T \otimes I_l) D'$$

Using Gröbner basis methods, the matrices $D$ and $D'$ can be computed (see, e.g., [5]) using, e.g., the **Factorize** command of the OREMODULES package. This factorization yields $h_i I_l = \bar{B} \bar{D}$ as an identity of matrices with entries in $\mathcal{S}$, which finally shows that we can take $E_{h_i} = h_i^{-1} \bar{D}$.

Using eq. (58) and doing similarly as explained in Section 3.2.2 (see eq. (27)), we can compute $C_{h_i} \in \mathcal{R}^{q \times l}$ satisfying $\ker_{S_{h_i}}(B_{h_i}) = \text{im}_{S_{h_i}}(C_{h_i})$ using, e.g., OREMODULES. The matrices $C_{h_i}$, $E_{h_i}$, and $F_{h_i}$ can also be computed by CapAndHomalg [1]. Note that CapAndHomalg directly works in the factor ring $\mathcal{S} = \mathcal{R}/\mathcal{J}$ or the localization $S_{h_i}$ of $\mathcal{S}$.

Finally, using eq. (56), $\overline{\mathcal{V}}_{\mathcal{K}}(\mathcal{J}) \setminus \overline{\mathcal{V}}_{\mathcal{K}}(\langle g_i \rangle) = \mathcal{V}_{\mathcal{K}}(\mathcal{J} : \langle g_i \rangle^{\infty})$ can also be computed.

**Example 12.** Let us continue Example 4, Example 5, Example 8, and Example 9. Using $\mathcal{I} = \text{Fitt}_0(\mathcal{B}) = \langle \bar{B}_1, \bar{B}_2 \rangle_{\mathcal{S}}$, where $\bar{B}_1$ and $\bar{B}_2$ are the first two entries of the matrix $\bar{B}$ defined in Example 8, we then have to consider the following two cases:

* If $h_1 = \bar{B}_1$, where $B_1 = g_1 = x_4(5x_2/2 + x_3) \in \mathcal{R}$, then $h_1$ is not an nilpotent element of $\mathcal{S}$. Considering the ring $S_{h_1} = \{s/h_1^k | s \in \mathcal{S}, k \in \mathbb{Z}_{\ge 0}\}$, the matrix $E_{h_1} = (h_1^{-1} \quad 0 \quad 0)^T \in S_{h_1}^{3 \times 1}$ then satisfies $B E_{h_1} = 1$. Using eq. (57), we obtain that

$$\left\{ \begin{array}{l} u \in \mathcal{U}_{g_1} = \mathcal{V}_{\mathcal{K}}(\mathcal{J}) \setminus \mathcal{V}_{\mathcal{K}}(\langle g_1 \rangle), \\ v_{h_1}(u) = K(u) E_{h_1}(u) Y = \begin{pmatrix} \frac{6 u_2}{g_1(u)} & 0 & 0 \\ \frac{6 u_4}{g_1(u)} & 0 & 0 \end{pmatrix}, \end{array} \right.$$

is a solution of Problem eq. (4). More generally, using $\ker_{S_{h_1}}(\bar{B}) = \text{im}_{S_{h_1}}(C_{h_1})$, where

$$C_{h_1} = \begin{pmatrix} 3 & 0 \\ 0 & -6x_4 \\ -1 & 9x_2 + 6x_3 + 2x_4 \end{pmatrix} \in S_{h_1}^{3 \times 2},$$

and $x_i$ simply stands for $j_{h_1}(\bar{x}_i) = \bar{x}_i/1$ for $i = 1, \dots, 4$, then the solutions $(u, v)$ of Problem eq. (4) in $\mathcal{U}_{g_1}$ are defined by:

$$\forall Y' \in \mathbb{K}^{2 \times 3}, \quad \left\{ \begin{array}{l} u \in \mathcal{U}_{g_1}, \\ v_{h_1}(u, Y') = K(u) (E_{h_1}(u) Y + C_{h_1}(u) Y'). \end{array} \right.$$

Finally, we have $\mathcal{J} : \langle g_1 \rangle^{\infty} = \langle 2x_1 - 3x_2 - 2x_3, x_2(9x_2 + 6x_3 + 2x_4) \rangle$, which yields:

$$\overline{\mathcal{V}_{\mathcal{K}}(\mathcal{J}) \setminus \mathcal{V}_{\mathcal{K}}(\langle g_1 \rangle)} = \mathcal{V}_{\mathcal{K}}(\mathcal{J} : \langle g_1 \rangle^{\infty}) = \{ (u_1 \quad 0 \quad u_1 \quad u_4)^T \mid u_1, u_4 \in \mathbb{K} \} \cup \{ (-u_4/3 \quad -2u_3/3 - 2u_4/9 \quad u_3 \quad u_4)^T \mid u_3, u_4 \in \mathbb{K} \}.$$

* If $h_2 = \bar{B}_2$, where $B_2 = g_2 = (3x_1 + x_4)x_3 \in \mathcal{R}$, then $h_2$ is not an nilpotent element of $\mathcal{S}$. Considering the ring $S_{h_2} = \{s/h_2^k | s \in \mathcal{S}, k \in \mathbb{Z}_{\ge 0}\}$, the matrix $E_{h_2} = (h_2^{-1} \quad 0)^T \in S_{h_2}^{3 \times 1}$ then satisfies $B E_{h_2} = 1$. Using eq. (57), we obtain that

$$\left\{ \begin{array}{l} u \in \mathcal{U}_{g_2} = \mathcal{V}_{\mathcal{K}}(\mathcal{J}) \setminus \mathcal{V}_{\mathcal{K}}(\langle g_2 \rangle), \\ v_{h_2}(u) = K(u) E_{h_2}(u) Y = \begin{pmatrix} 0 & 0 & 0 \\ \frac{6(3u_3 + u_4)}{h_2(u)} & 0 & 0 \end{pmatrix}, \end{array} \right.$$
is a solution of Problem eq. (4). More generally, using $\ker_{S_{h_2}}(\bar{B}_.) = \mathrm{im}_{S_{h_2}}(C_{h_2}.)$, where

$$C_{h_2} = \begin{pmatrix} 3 & 0 \\ 0 & -3x_4 \\ -1 & 3x_3 + x_4 \end{pmatrix} \in S_{h_2}^{3 \times 2},$$

then the solutions $(u, v)$ of Problem eq. (4) in $U_{g_2}$ are defined by:

$$\left\{ \begin{array}{l} u \in U_{g_2}, \\ v_{h_2}(u, Y') = K(u) (E_{h_2}(u) Y + C_{h_2}(u) Y'), \forall Y' \in \mathbb{K}^{2 \times 3}. \end{array} \right.$$

$$\text{Finally, we have } \overline{V_{\mathbb{K}}(\mathcal{J}) \setminus V_{\mathbb{K}}(\langle g_2 \rangle)} = \overline{V_{\mathbb{K}}(\mathcal{J}) \setminus V_{\mathbb{K}}(\langle g_1 \rangle)}. $$

In Algorithm 3, we present a pseudocode summarizing Theorem 5. It can easily be implemented in any standard computer algebra system. See the RANKFACTORIZATION package [9] dedicated to the rank factorization problem and its applications (built upon the OREMODULES package [6]). Note that an index $k$ - fixed to 0 - is given in this input of RANKFACTORIZATIONPROBLEM command. It corresponds to the computation of Fitt$_0(\mathcal{Q})$. In Section 4, we shall show that all the solutions of the rank factorization eq. (4) can be obtained by considering the different Fitt$_k(\mathcal{Q})$ for $k = 0, \dots, r - 1$ (see also Remark 11).

<caption>**Algorithm 3 RankFactorizationProblem**</caption>

1: **procedure** RANKFACTORIZATIONPROBLEM($D_1, \dots, D_r \in \mathbb{K}^{m \times m}, 0 \neq M \in \mathbb{K}^{m \times n}, k = 0$)
2: Define $\mathcal{R} = \mathbb{K}[x_1, \dots, x_m]$, $x = (x_1 \dots x_m)^T$, $A = (D_1 x \dots D_r x) \in \mathcal{R}^{m \times r}$
3: Compute a basis of $\ker_{\mathbb{K}}(\cdot, M)$ and stack its row vectors into a full row rank matrix $L \in \mathbb{K}^{p \times m}$ satisfying $\ker_{\mathbb{K}}(\cdot, M) = \mathrm{im}_{\mathbb{K}}(\cdot, L)$, where $p = m - l$ and $l = \mathrm{rank}_{\mathbb{K}}(M)$
4: Define $Q = LA \in \mathcal{R}^{p \times r}$ and the finitely presented $\mathcal{R}$-module $Q = \mathrm{coker}_{\mathcal{R}}(\cdot, Q)$
5: Compute the ideal $\mathcal{J} = \mathrm{Fitt}_k(\mathcal{Q}) = \mathrm{Fitt}_0(\mathcal{Q})$ and define the ring $\mathcal{S} = \mathcal{R}/\mathcal{J}$
6: Compute $K \in \mathcal{R}^{r \times q}$ such that $\ker_{\mathcal{S}}(\mathcal{Q}) = \mathrm{im}_{\mathcal{S}}(\bar{K})$, where $\bar{K} = \chi(K) \in \mathcal{S}^{r \times q}$ and $\chi: \mathcal{R} \to \mathcal{S}$ is the canonical ring epimorphism
7: Compute a basis of $\mathrm{im}_{\mathbb{K}}(\cdot, M)$ and stack its column vectors into a full column rank matrix $X \in \mathbb{K}^{m \times l}$ satisfying $\mathrm{im}_{\mathbb{K}}(\cdot, M) = \mathrm{im}_{\mathbb{K}}(\cdot, X)$
8: Compute a full row rank matrix $Y \in \mathbb{K}^{l \times n}$ such that $M = XY$
9: Compute a left inverse $V \in \mathbb{K}^{l \times m}$ of $X$
10: Define $B = VAK \in \mathcal{R}^{l \times q}$ and the finitely presented $\mathcal{S}$-module $\mathcal{B} = \mathrm{coker}_{\mathcal{S}}(\bar{B}_.)$, where $\bar{B} = \chi(B)$
11: Compute the ideal $\mathcal{I} = \mathrm{Fitt}_0(\mathcal{B}) = \langle h_1, \dots, h_\beta \rangle_{\mathcal{S}}$ of $\mathcal{S}$
12: **if** $\mathcal{I} = \langle 0 \rangle_{\mathcal{S}}$ **then** return "No solutions exist"
13: **else**
14: Set $I = \emptyset$
15: **for** $i \leftarrow 1, \dots, \beta$ **do**
16: **if** $h_i$ is nilpotent element of $\mathcal{S}$ **then** $i := i + 1$
17: **else**
18: Define the localization $S_{h_i}$ of $\mathcal{S}$ at the multiplicatively closed set $\{h_i^k\}_{k \in \mathbb{Z}_{\ge 0}}$
19: Compute a right inverse $E_{h_i} \in S_{h_i}^{q \times l}$ of $B_{h_i} = j_{h_i}(\bar{B})$, where $j_{h_i}: \mathcal{S} \to \mathcal{S}_{h_i}$ is the canonical ring homomorphism
20: Compute $C_{h_i} \in S_{h_i}^{q \times t_i}$ such that $\ker_{S_{h_i}}(B_{h_i}.) = \mathrm{im}_{S_{h_i}}(C_{h_i}.)$
21: Let $g_i \in \mathcal{R}$ define the residue class of $h_i \in \mathcal{S}$, i.e., $h_i = \bar{g}_i$, and $I := I \cup \{g_i\}$
22: **end if**
23: **end for**
24: **if** $I = \emptyset$ **then** return "No solutions exist"
25: **else** return $\mathcal{J}, K, Y, \{h_i\}_{i \in I}, \{E_{h_i}\}_{i \in I}$, and $\{C_{h_i}\}_{i \in I}$ defining the solutions eq. (57)
26: **end if**
27: **end if**
28: **end procedure**
# 4 Getting all the solutions of the rank factorization problem

## 4.1 The solutions of the rank factorization problem

In this section, we shall use the notations of Theorem 4 and of the last paragraph of Section 3.2.4.

As explained in Section 3.2.1, the solutions $(u, v)$ of the rank factorization problem necessarily satisfy the condition $u \in \mathcal{V}_{\mathcal{K}}(\mathcal{J})$, where $\mathcal{J} = \mathcal{J}_0 = \text{Fitt}_0(\mathcal{Q})$. Using module theory over the ring $S = \mathbb{R}/\mathcal{J}$, in Section 3.2, solutions of the rank factorization problem were characterized. We also explained that a similar approach could be developed for the rings $S_k = \mathbb{R}/\mathcal{J}_k$ for $k = 0, \dots, r-1$. More precisely, Theorem 5 also holds if $\mathcal{J} = \text{Fitt}_0(\mathcal{Q})$ is replaced by $\mathcal{J}_k = \text{Fitt}_k(\mathcal{Q})$ for $0 \le k \le r-1$. Hence, we can characterize solutions of the rank factorization problem which satisfy $u \in \mathcal{V}_{\mathcal{K}}(\mathcal{J}_k)$ by considering the $S_k = \mathbb{R}/\mathcal{J}_k$-module $B_k = \text{coker}_{S_k}(B_k)$, where $B_k = V A K_k$. It is important to note that not all those solutions are the restrictions of the solutions obtained by considering the ring $S = \mathbb{R}/\mathcal{J}$ to $\mathcal{V}_{\mathcal{K}}(\mathcal{J}_k)$. Indeed, if $(u, v)$ is a solution of the rank factorization problem and $\text{rank}_{\mathcal{K}}(Q(u)) = r-k-1$, then $u \in \mathcal{V}(\mathcal{J}_k) \setminus \mathcal{V}(\mathcal{J}_{k+1})$ and using Theorem 4 (see eq. (29)), $v \in \text{ker}_{\mathcal{K}}(Q(u)) = \text{im}_{\mathcal{K}}(K_k(u))$, i.e., $v$ is of the form $v = K_k(u) T_u$, for a certain $T_u \in \mathbb{K}^{q_k \times n}$ satisfying $B_k(u) T_u = Y$. But $v$ does not necessarily belong to $\text{im}_{\mathcal{K}}(K(u))$ since we usually only have $\text{im}_{\mathcal{K}}(K(u)) \subseteq \text{ker}_{\mathcal{K}}(Q(u))$. See Theorem 4 and eq. (29). Hence, by considering the solutions over $S$, we are only sure to parametrize all the solutions $(u, v)$ which are such that $\text{rank}_{\mathcal{K}}(Q(u)) = r-1$. Similarly, considering the solutions over $S_k$, we are only sure to parametrizing all the solutions $(u, v)$ which are such that $\text{rank}_{\mathcal{K}}(Q(u)) = r-k-1$. Finally, the case $k=r-1$ corresponds to Section 2.2. Indeed, as explained at the end of Remark 11, $\mathcal{V}_{\mathcal{K}}(\mathcal{J}_{r-1}) = \text{ker}_{\mathcal{K}}(N.)$, where $\mathcal{J}_{r-1} = \text{Fitt}_{r-1}(\mathcal{Q})$ and $N$ is defined by eq. (7). In Section 2.2, all the solutions of the rank factorization problem with the condition $u \in \mathcal{V}_{\mathcal{K}}(\mathcal{J}_{r-1})$, were found using linear algebra methods. This approach correspond to the approach developed in Section 3 for the ring $S_{r-1} = \mathbb{R}/\mathcal{J}_{r-1}$. Indeed, we first note that $\chi_{r-1}(\mathcal{Q}) = 0$, which yields $K_{r-1} = I_r$, and then, using eq. (42), we have $\chi_{r-1}(A) = \chi_{r-1}(X) \chi_{r-1}(B_{r-1})$ and $\chi_{r-1}(B_{r-1}) = \chi_{r-1}(V) \chi_{r-1}(A)$, i.e., $B_{r-1}-V A \in \mathcal{J}_{r-1}^{l \times q}$. Using the fact that $\mathcal{V}_{\mathcal{K}}(\mathcal{J}_{r-1}) = \text{ker}_{\mathcal{K}}(N.) = \text{im}_{\mathcal{K}}(Z.)$, where $Z \in \mathbb{K}^{m \times d}$ is defined in Lemma 2, then $u = Z \psi$ for all $\psi \in \mathbb{K}^{d \times 1}$, and thus, using eq. (9) and $V X = I_l$, we have $B_{r-1}(Z \psi) = V A(Z \psi) = V X B(\psi) = B(\psi) = (W_1 \psi \dots W_r \psi)$ for all $\psi \in \mathbb{K}^{d \times 1}$.

**Theorem 6.** The complete set of solutions of the rank factorization problem eq. (4) is the union of the solutions given in Theorem 5, where $\mathcal{J}$ is replaced by $\mathcal{J}_k$ for $k = 0, \dots, r-1$.

*Proof.* To get the complete set of solutions for the rank factorization problem, we have to collect all the solutions defined in Theorem 5 for the different ideals $\mathcal{J}_k$ for $k = 0, \dots, r-1$. Indeed, all these sets of solutions are, by construction, solutions of the rank factorization problem eq. (4). Conversely, if $(u, v)$ is a solution to the rank factorization problem, then we have $u \in \mathcal{V}_{\mathcal{K}}(\mathcal{J}_0)$. Let $k \in [0, \dots, r-1]$ be such that $\text{rank}_{\mathcal{K}}(Q(u)) = r-k-1$. Then, we have $u \in \mathcal{V}_{\mathcal{K}}(\mathcal{J}_k) \setminus \mathcal{V}_{\mathcal{K}}(\mathcal{J}_{k+1})$. Let $K_k \in \mathbb{R}^{r \times q_k}$ be defined as in Theorem 4. By Theorem 4, each column of $v$ belongs to $\text{ker}_{\mathcal{K}}(Q(u)) = \text{im}_{\mathcal{K}}(K_k(u))$. Therefore, there exists $T_u \in \mathbb{K}^{q_k \times n}$ such that $v = K_k(u) T_u$, where $T_u$ satisfies $B_k(u) T_u = Y$. Since $Y$ has a right inverse $H \in \mathbb{K}^{n \times l}$ (see the proof of Proposition 2), i.e., $Y H = I_l$, then we have $B_k(u) (T_u H) = I_l$, which shows that $\text{rank}_{\mathcal{K}}(B_k(u)) = l$. Let $B_k = V A K_k \in \mathbb{R}^{l \times q_k}$ and $B_k = \text{coker}_{S_k}(\chi_k(B_k))$ be the $S_k$-module finitely presented by $\chi_k(B_k)$, where $\chi_k: \mathbb{R} \to S_k$ is the canonical ring epimorphism. Moreover, let $\mathcal{I}_k = \text{Fitt}_0(B_k) = \langle h_{k,1}, \dots, h_{k,\beta_k} \rangle_{S_k}$, $g_{k,j} \in \mathbb{R}$ be such that $h_{k,j} = \chi_k(g_{k,j})$ for $j = 1, \dots, \beta_k$, and $\mathcal{I}_{k,\mathbb{R}} = \langle g_{k,1}, \dots, g_{k,\beta_k} \rangle_{\mathbb{R}}$. Set $I_k = \{i \in [1, \dots, \beta_k] \mid g_{k,i} \notin \sqrt{\mathcal{J}_k}\}$. By Theorem 5, the solutions of the rank factorization problem defined over $S_k$ are of the form

$$ u \in \mathcal{V}_{\mathcal{K}}(\mathcal{J}_k) \setminus \mathcal{V}_{\mathcal{K}}(\mathcal{I}_{k,\mathbb{R}}) = \bigcup_{i \in I_k} (\mathcal{V}_{\mathcal{K}}(\mathcal{J}_k) \setminus \mathcal{V}_{\mathcal{K}}(\langle g_{k,i} \rangle)), \quad (59) \\ \forall i \in I_k, \quad \left\{ \begin{array}{l} u \in \mathcal{V}_{\mathcal{K}}(\mathcal{J}_k) \setminus \mathcal{V}_{\mathcal{K}}(\langle g_{k,i} \rangle), \\ v_{h_{k,i}}(u, Y') = K_k(u) (E_{h_{k,i}}(u) Y + C_{h_{k,i}}(u) Y'), \quad \forall Y' \in \mathbb{K}^{t_{k,i} \times n}, \end{array} \right. $$

where for $i \in I_k$, $\text{ker}_{\mathcal{K}}(B_k(u)) = \text{im}_{\mathcal{K}}(C_{h_{k,i}}(u))$, $C_{h_{k,i}}(u) \in \mathbb{K}^{q_k \times t_{k,i}}$, and $B_k(u) E_{h_{k,i}}(u) = I_l$ for all $u \in \mathcal{V}_{\mathcal{K}}(\mathcal{J}_k) \setminus \mathcal{V}_{\mathcal{K}}(\langle g_{k,i} \rangle)$. Finally, coming back to the above solution $(u, v)$ of the rank factorization problem satisfying $u \in \mathcal{V}_{\mathcal{K}}(\mathcal{J}_k)$, note that $u \notin \mathcal{V}_{\mathcal{K}}(\mathcal{I}_{k,\mathbb{R}})$. Indeed, if so, then $\text{rank}_{\mathcal{K}}(B_k(u)) < l$, which contradicts the fact that $(u, v)$ is a solution of the rank factorization problem. Thus, there exists $i \in I_k$ such that $g_{k,i}(u) \neq 0$, i.e., $u \in \mathcal{V}_{\mathcal{K}}(\mathcal{J}_k) \setminus \mathcal{V}_{\mathcal{K}}(\langle g_{k,i} \rangle)$, and thus, $v = v_{h_{k,i}}(u, Y')$ for a certain matrix $Y' \in \mathbb{K}^{t_{k,i} \times n}$, which finally proves the result. $\square$
**Algorithm 4 AllSolutions**

1: **procedure** ALLSOLUTIONS(D<sub>1</sub>, ..., D<sub>r</sub> ∈ K<sup>m×m</sup>, 0 ≠ M ∈ K<sup>m×n</sup>)

2: For k = 0, ..., r − 1, Sol<sub>k</sub> = RANKFACTORIZATIONPROBLEM(D<sub>1</sub>, ..., D<sub>r</sub>, M, k)

3: return ⋃<sub>k=0</sub><sup>r − 1</sup> Sol<sub>k</sub>

4: end procedure

If r = 1 (see [14, 15]), then we only have to consider J = J<sub>0</sub> = J<sub>r − 1</sub> and the approach of Section 2.2 is enough to find all the solutions of the rank factorization problem eq. (4).

**Example 13.** We continue Example 1. Let $x = (x_1 \dots x_4)^T$, $\mathcal{R} = \mathbb{Q}[x_1, x_2, x_3, x_4]$,

$$
A = (D_1 x \quad D_2 x \quad D_3 x \quad D_4 x) = \begin{pmatrix} 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{pmatrix} \in \mathcal{R}^{4 \times 4},
$$

$Q = \operatorname{coker}_S(Q) = \mathcal{R}^{1 \times 4} / (\mathcal{R}^{1 \times 3} Q)$ be the $\mathcal{R}$ finitely presented by the following matrix

$$
Q = L A = \begin{pmatrix} 0 & -x_3 & 0 & -x_2 \\ 0 & x_2 & 0 & x_3 \\ x_1 + x_4 & 0 & x_1 + x_4 & 0 \end{pmatrix} \in \mathcal{R}^{3 \times 4},
$$

and the Fitting ideals of $\mathcal{Q}$ defined by:

$$
\left\{
\begin{array}{l}
\mathcal{J} = \mathcal{J}_0 = \text{Fitt}_0(\mathcal{Q}) = \langle 0 \rangle, \\
\mathcal{J}_1 = \text{Fitt}_1(\mathcal{Q}) = \langle (x_1 + x_4)(x_2 - x_3)(x_2 + x_3) \rangle, \\
\mathcal{J}_2 = \text{Fitt}_2(\mathcal{Q}) = \langle (x_2 - x_3)(x_2 + x_3), x_3(x_1 + x_4), x_2(x_1 + x_4) \rangle, \\
\mathcal{J}_3 = \text{Fitt}_3(\mathcal{Q}) = \langle x_2, x_3, x_1 + x_4 \rangle.
\end{array}
\right.
$$

Hence, rank<sub>k</sub>(Q(u)) for u ∈ V<sub>k</sub>(J<sub>k</sub>) is less than or equal to 3 − k for k = 0, . . . , 3. In particular, we have
Q(u) = 0 for u ∈ V<sub>k</sub>(J<sub>3</sub>) = {(1 0 0 − 1)<sup>T</sup> u<sub>1</sub> | u<sub>1</sub> ∈ K}. See Example 1.

Let us consider the rings $S_k = \mathcal{R}/\mathcal{J}_k$ for $k=0, \dots, 3$, with the notation $S_0 = S = \mathcal{R}$, and $\chi_k : S \to S_k$
the canonical ring epimorphisms for $k=1, 2, 3$. Denote the residue class $\bar{x}_i$ (resp., $\chi_k(x_i)$) of $x_i$ in $S$
(resp., $S_k$) simply by $x_i$. Let $K_k$ be a matrix satisfying $\ker_{S_k}(\chi_k(Q)) = \operatorname{im}_{S_k}(\chi_k(K_k))$ for $k=0, \dots, 3$:

$$
K = K_0 = \begin{pmatrix} 1 \\ 0 \\ -1 \\ 0 \end{pmatrix} \in \mathcal{S}^{4 \times 1}, \quad K_2 = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & -x_3 & x_2 & x_1 + x_4 & 0 & 0 \\ -1 & 0 & 0 & 0 & x_3 & x_2 \\ 0 & x_2 & -x_3 & 0 & 0 & x_1 + x_4 \end{pmatrix} \in \mathcal{S}_2^{4 \times 7},
$$

$$
K_1 = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & -x_3(x_1+x_4) & x_2(x_1+x_4) & 0 & 0 & 0 \\ -1 & 0 & 0 & (x_2-x_3)(x_2+x_3) & 0 & 0 \\ 0 & x_2(x_1+x_4) & -x_3(x_1+x_4) & 0 & 0 & x_1+x_4 \end{pmatrix} \in \mathcal{S}_1^{4 \times 4}, \quad K_3 = I_4.
$$

Using the left inverse $V = (0 \ 0 \ 0 \ 1)$ of $X$, then we have:

$$
\left\{
\begin{array}{l}
B = V A K_0 = (x_1 - x_4) \in \mathcal{R}, \\
B_1 = V A K_1 = (x_1 - x_4 \quad 0 \quad 0 \quad -x_1(x_2 - x_3)(x_2 + x_3)) \in \mathcal{R}^{1 \times 4}, \\
B_2 = V A K_2 = (x_1 - x_4 \quad 0 \quad 0 \quad 0 \quad -x_1 x_3 \quad -x_1 x_2 \quad 0) \in \mathcal{R}^{1 \times 7}, \\
B_3 = V A K_3 = (-x_4 \quad 0 \quad -x_1 \quad 0) \in \mathcal{R}^{1 \times 4}.
\end{array}
\right.
$$

Introducing the $S_k$-modules $B_k = \operatorname{coker}_{S_k}(\chi_k(B_k).)$ for $k=1,2,3$, we then get:

$$
\left\{
\begin{array}{l}
\mathcal{I} = \text{Fitt}_0(\mathcal{B}) = \langle x_1 - x_4 \rangle_{\mathcal{S}}, \\
\mathcal{I}_1 = \text{Fitt}_0(\mathcal{B}_1) = \langle x_1 - x_4, -x_1(x_2 - x_3)(x_2 + x_3) \rangle_{\mathcal{S}_1} = \langle x_1 - x_4 \rangle_{\mathcal{S}_1}, \\
\mathcal{I}_2 = \text{Fitt}_0(\mathcal{B}_2) = \langle x_1 - x_4, -x_1 x_3, -x_1 x_2 \rangle_{\mathcal{S}_2} = \langle x_1 - x_4 \rangle_{\mathcal{S}_2}, \\
\mathcal{I}_3 = \text{Fitt}_0(\mathcal{B}_3) = \langle x_1, x_4 \rangle_{\mathcal{S}_3} = \langle x_4 \rangle_{\mathcal{S}_3}.
\end{array}
\right.
$$
We then have $S_k \otimes_S \mathcal{I} = \langle x_1 - x_4 \rangle_{S_k} = \mathcal{I}_k$ for $k = 1, 2, 3$.

First consider $\mathcal{I}$. Let $h_0 = g_0 = x_1 - x_4$ and consider the localization $S_{h_0} \cong \mathcal{R}[y]/\langle y h_0 - 1 \rangle$ of $S = \mathcal{R}$ (see eq. (58)). Then, $B$ has the inverse $E_{h_0} = y$. Moreover, we have $C_{h_0} = 0$ because $\ker_{S_{h_0}}(B.) = 0$. Hence, using $Y = (1 \ 0 \ 0 \ 1)$, the corresponding solutions of Problem eq. (4) are defined by:

$$ egin{cases} u = (u_1 \dots u_4)^T \in \mathcal{U}_0 = \mathbb{K}^{4 \times 1} \setminus \mathcal{V}_{\mathbb{K}}(\langle x_1 - x_4 \rangle) = \{ (u_1 \dots u_4)^T \in \mathbb{K}^{4 \times 1} \mid u_1 \neq u_4 \} \\ v_{h_0}(u) = K_0(u) E_{h_0}(u) Y = \frac{1}{u_1 - u_4} \begin{pmatrix} 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ -1 & 0 & 0 & -1 \\ 0 & 0 & 0 & 0 \end{pmatrix}. \end{cases} $$

Now, consider the ideal $\mathcal{I}_1$ of $S_1 = \mathcal{R}/\langle (x_1 + x_4)(x_2 - x_3)(x_2 + x_3) \rangle$, $g_1 = x_1 - x_4$, $h_1 = \chi_1(g_1)$, and the localization $S_{1h_1} \cong \mathcal{R}[y]/\langle y g_1 - 1, (x_1 + x_4)(x_2 - x_3)(x_2 + x_3) \rangle$ of $S_1$ (see eq. (58)). We can check that $h_1$ is not a nilpotent element of $S_1$, i.e., $S_{1h_1}$ is not the trivial ring. Then, $B_1$ has a right inverse $E_{h_1} = y(1 \ 0 \ 0 \ 0)^T \in S_{1h_1}^{4 \times 1}$ and the following matrix

$$ C_{h_1} = \begin{pmatrix} x_2^2 - x_3^2 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 2 & 0 & 0 \end{pmatrix} \in S_{1h_1}^{4 \times 3} $$

satisfies $\ker_{S_{1h_1}}(B_{1.}) = \operatorname{im}_{S_{1h_1}}(C_{h_1.})$. Let us define the following quasi-affine variety:

$$ \begin{align*} \mathcal{U}_1 &= \mathcal{V}_{\mathbb{K}}(\langle (x_1 + x_4)(x_2 - x_3)(x_2 + x_3) \rangle) \setminus \mathcal{V}_{\mathbb{K}}(\langle (x_1 + x_4)(x_2 - x_3)(x_2 + x_3), x_1 - x_4 \rangle) \\ &= \left\{ \begin{pmatrix} u_1 \\ u_2 \\ u_3 \\ -u_1 \end{pmatrix}, \begin{pmatrix} u_1 \\ u_2 \\ u_2 \\ u_4 \end{pmatrix}, \begin{pmatrix} u_1 \\ u_2 \\ -u_2 \\ u_4 \end{pmatrix} \mid u_i \in \mathbb{K} \right\} \setminus \left\{ \begin{pmatrix} 0 \\ u_2 \\ u_3 \\ 0 \end{pmatrix}, \begin{pmatrix} u_1 \\ u_2 \\ u_2 \\ u_1 \end{pmatrix}, \begin{pmatrix} u_1 \\ u_2 \\ -u_2 \\ u_1 \end{pmatrix} \mid u_i \in \mathbb{K} \right\}. \end{align*} $$

Then, the corresponding solutions of Problem eq. (4) are defined by:

$$ egin{cases} u = (u_1 \dots u_4)^T \in \mathcal{U}_1, \\ v_{h_1}(u, Y'_1) = K_1(u) (E_{h_1}(u) Y + C_{h_1}(u) Y'_1) \\ = \frac{1}{u_1 - u_4} \begin{pmatrix} 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ -1 & 0 & 0 & -1 \\ 0 & 0 & 0 & 0 \end{pmatrix} + \begin{pmatrix} u_2^2 - u_3^2 & 0 & 0 & 0 \\ 0 & -u_3(u_1 + u_4) & u_2(u_1 + u_4) & 0 \\ u_2^2 - u_3^2 & 0 & 0 & 0 \\ 0 & u_2(u_1 + u_4) & -u_3(u_1 + u_4) & 0 \end{pmatrix} Y'_1, \\ \forall Y'_1 \in \mathbb{K}^{4 \times 4}. \end{cases} $$

Consider $S_2 \cong \mathcal{R}/\langle (x_2 - x_3)(x_2 + x_3), x_3(x_1 + x_4), x_2(x_1 + x_4) \rangle$, $g_2 = x_1 - x_4$, $h_2 = \chi_2(g_2)$, and the localization $S_{2h_2} \cong \mathcal{R}[y]/\langle y g_2 - 1, (x_2 - x_3)(x_2 + x_3), x_3(x_1 + x_4), x_2(x_1 + x_4) \rangle$ of $S_2$ (see eq. (58)). We can check that $h_2$ is not a nilpotent element of $S_2$, i.e., $S_{2h_2}$ is not the trivial ring. Then, $B_2$ has a right inverse $E_{h_2} = y(1 \ 0 \ 0 \ 0 \ 0 \ 0)^T \in S_{2h_2}^{7 \times 1}$ and the following matrix

$$ C_{h_2} = \begin{pmatrix} 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{pmatrix} \in S_{2h_2}^{7 \times 6} $$
satisfies $\ker_{S_{2h_2}}(B_2.) = \operatorname{im}_{S_{2h_2}}(C_{h_2.})$. Let us define the following quasi-affine variety:

$$
\begin{align*}
\mathcal{U}_2 &= \mathcal{V}_{\mathbb{K}}(\langle x_2^2 - x_3^2, x_3(x_1+x_4), x_2(x_1+x_4) \rangle) \setminus \mathcal{V}_{\mathbb{K}}(\langle x_2^2 - x_3^2, x_3(x_1+x_4), x_2(x_1+x_4), x_1-x_4 \rangle) \\
&= \left\{ \begin{pmatrix} u_1 \\ 0 \\ 0 \\ u_4 \end{pmatrix}, \begin{pmatrix} u_1 \\ u_2 \\ u_2 \\ -u_1 \end{pmatrix}, \begin{pmatrix} u_1 \\ u_2 \\ -u_2 \\ -u_1 \end{pmatrix} \middle| u_i \in \mathbb{K} \right\} \setminus \left\{ \begin{pmatrix} u_1 \\ 0 \\ 0 \\ u_1 \end{pmatrix}, \begin{pmatrix} 0 \\ u_2 \\ u_2 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ u_2 \\ -u_2 \\ 0 \end{pmatrix} \middle| u_i \in \mathbb{K} \right\}.
\end{align*}
$$

Then, the corresponding solutions of Problem eq. (4) are:

$$
\left\{
\begin{array}{l}
u = (u_1 \dots u_4)^T \in \mathcal{U}_2, \\
v_{h_2}(u, Y'_2) = K_2(u) (E_{h_2}(u) Y + C_{h_2}(u) Y'_2) \\
\quad = \frac{1}{u_1 - u_4} \begin{pmatrix} 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ -1 & 0 & 0 & -1 \\ 0 & 0 & 0 & 0 \end{pmatrix} + \begin{pmatrix} u_3 & u_2 & 0 & 0 & 0 & 0 \\ 0 & 0 & -u_3 & u_2 & u_1 + u_4 & 0 \\ u_3 & u_2 & 0 & 0 & 0 & 0 \\ 0 & 0 & u_2 & -u_3 & 0 & u_1 + u_4 \end{pmatrix} Y'_2, \\
\forall Y'_2 \in \mathbb{K}^{6 \times 4}.
\end{array}
\right.
$$

The solutions obtained in Example 1 correspond to $S_3 = \mathbb{R}/\langle x_2, x_3, x_1 + x_4 \rangle$, $g_3 = x_4$, $h_3 = \chi_3(g_3)$, $S_{3h_3} \cong \mathbb{R}[y]/\langle y g_3 - 1, x_2, x_3, x_1 + x_4 \rangle$ (see eq. (58)), $E_{h_3} = y/2(-1 \ 0 \ 1 \ 0)^T \in S_{3h_3}^{4 \times 1}$, $\ker_{S_{3h_3}}(B_3.) = \operatorname{im}_{S_{3x_4}}(C_{h_3.})$, where $C_{h_3}$ is defined by eq. (12). We find again eq. (13) because we have:

$$
\mathcal{U}_3 = \mathcal{V}_{\mathbb{K}}(\langle x_2, x_3, x_1 + x_4 \rangle) \setminus \mathcal{V}_{\mathbb{K}}(\langle x_2, x_3, x_1 + x_4, x_4 \rangle) = \left\{ \begin{pmatrix} -u_4 \\ 0 \\ 0 \\ u_4 \end{pmatrix} \middle| u_4 \in \mathbb{K} \setminus \{0\} \right\}.
$$

## 4.2 A few final remarks on the solution space

In this section, we state a few remarks on the solution space of the rank factorization problem.
We first study connections between the modules $\mathcal{B}_k$'s.

Applying the right exact covariant functor $S_{k+1} \otimes_S \mathcal{B}_k$ to the exact sequence of $S_k$-modules

$$
S_k^{q_k \times 1} \xrightarrow{\chi_k(B_k)} S_k^{l \times 1} \xrightarrow{\sigma_k} \mathcal{B}_k \longrightarrow 0,
$$

we obtain the following exact sequence of $S_k$-modules

$$
S_{k+1}^{q_k \times 1} \xrightarrow{\chi_{k+1}(B_k)} S_{k+1}^{l \times 1} \xrightarrow{\mathrm{id}_{S_{k+1}} \otimes \sigma_k} S_{k+1} \otimes_S \mathcal{B}_k \longrightarrow 0,
$$

i.e., $S_{k+1} \otimes_S \mathcal{B}_k \cong \operatorname{coker}_{S_k}(\chi_{k+1}(B_k).)$. Using Proposition 4, we then have:

$$
S_{k+1} \otimes_S \mathrm{Fitt}_j(\mathcal{B}_k) = \mathrm{Fitt}_j(S_{k+1} \otimes_S \mathcal{B}_k) = \mathrm{Fitt}_j(\mathrm{coker}_{S_{k+1}}(\chi_{k+1}(B_k))), \quad j = 0, \dots, l-1.
$$

Using eq. (32), we obtain the following commutative exact diagram of $S_{k+1}$-modules

$$
\begin{tikzcd}
& & S_{k+1}^{q_k \times 1} \arrow[r, "\chi_{k+1}(B_k)"] \arrow[d, "\chi_k(L_{k,k+1})"'] & S_{k+1}^{l \times 1} \arrow[r, "\mathrm{id}_{S_{k+1}} \otimes \sigma_k"'] \arrow[d, "\vartheta_{k+1}"] & S_{k+1} \otimes_S \mathcal{B}_k \arrow[r, "\sigma_{k+1}"] \arrow[d, "\vartheta_{k+1}"] & 0 \\
S_{k+1}^{t_{k+1} \times 1} \arrow[r, "\chi_{k+1}(C_{k+1})"] & S_{k+1}^{q_{k+1} \times 1} \arrow[r, "\chi_{k+1}(B_{k+1})"] & S_{k+1}^{l \times 1} \arrow[r, "\sigma_{k+1}"] & \mathcal{B}_{k+1} \arrow[r, "\vartheta_{k+1}"] & 0,
\end{tikzcd}
$$

where $C_{k+1} \in \mathbb{R}^{t_{k+1} \times q_{k+1}}$ is such that $\ker_{S_{k+1}}(\chi_{k+1}(B_{k+1}.) = \operatorname{im}_{S_{k+1}}(\chi_{k+1}(C_{k+1}.)$.
Using 4 of Proposition 3.1 of [7], we have

$$ \operatorname{coker} \vartheta_{k+1} = S_{k+1}^{l \times 1} / \left( (\chi_{k+1}(B_{k+1}) \quad I_l) S_{k+1}^{(q_{k+1}+l) \times 1} \right) = 0, $$

i.e., $\vartheta_{k+1} : S_{k+1} \otimes_S B_k \to B_{k+1}$ is an epimorphism for $k = 0, \dots, r-2$. Thus, we have the following short exact sequences of $S_{k+1}$-modules:

$$ 0 \longrightarrow \operatorname{ker} \vartheta_{k+1} \longrightarrow S_{k+1} \otimes_S B_k \xrightarrow{\vartheta_{k+1}} B_{k+1} \longrightarrow 0, \quad k = 0, \dots, r-2. \quad (60) $$

Using 1 of Proposition 3.1 of [7], we obtain the following presentation matrix for $\operatorname{ker} \vartheta_{k+1}$:

$$ \begin{aligned} \operatorname{ker} \vartheta_{k+1} &= \operatorname{im}_{S_{k+1}} (\chi_{k+1}(B_{k+1}))/\operatorname{im}_{S_{k+1}} (\chi_{k+1}(B_k)) \\ &\cong \operatorname{coker}_{S_{k+1}} ((\chi_{k+1}(L_{k,k+1}) \quad \chi_{k+1}(C_{k+1})).) \end{aligned} $$

If $C_{k+1} = 0$, then note that $\operatorname{ker} \vartheta_{k+1} \cong \operatorname{coker}_{S_{k+1}} (\chi_{k+1}(L_{k,k+1})).$, a result which is a direct consequence of the application of the snake lemma to the above commutative exact diagram.

**Proposition 6** ([23]). If $g : \mathcal{M} \to \mathcal{M}''$ is an epimorphism of modules, then we have:

$$ \mathrm{Fitt}_0(\mathcal{M}) \subseteq \mathrm{Fitt}_0(\mathcal{M}''). $$

Note $\mathcal{I}_k = \mathrm{Fitt}_0(B_k)$ for $k = 0, \dots, r-1$. Applying Proposition 6 to $\vartheta_{k+1}$, we obtain

$$ S_{k+1} \otimes_S \mathcal{I}_k = S_{k+1} \otimes_S \mathrm{Fitt}_0(\mathcal{B}_k) = \mathrm{Fitt}_0(\mathrm{coker}_{S_{k+1}}(\chi_{k+1}(\mathcal{B}_k))). \subseteq \mathcal{I}_{k+1} = \mathrm{Fitt}_0(\mathcal{B}_{k+1}), \quad (61) $$

for $k = 0, \dots, r-2$. More precisely, if $\mathcal{I}_k = \langle h_{k,1}, \dots, h_{k,\beta_k} \rangle_{S_k}$, where $g_{k,j} \in \mathcal{R}$ is such that $h_{k,j} = \chi_k(g_{k,j})$ for $j = 1, \dots, \beta_k$ and $k = 0, \dots, r-1$, then eq. (61) yields:

$$ \langle \chi_{k+1}(g_{k,1}), \dots, \chi_{k+1}(g_{k,\beta_k}) \rangle_{S_{k+1}} \subseteq \langle \chi_{k+1}(g_{k+1,1}), \dots, \chi_{k+1}(g_{k+1,\beta_{k+1}}) \rangle_{S_{k+1}}. $$

Let $\Theta_{k+1} = \{j \in [1, \dots, \beta_{k+1}] \mid \chi_{k+1}(g_{k+1,j}) \notin S_{k+1} \otimes_S \mathcal{I}_k\}$, i.e., $\Theta_{k+1}$ is the set of the indices of the generators $\chi_{k+1}(g_{k+1,j})$ of $\mathcal{I}_{k+1}$ which are not zero in $\mathcal{I}_{k+1} / (S_{k+1} \otimes_S \mathcal{I}_k)$. Therefore, we have:

$$ \mathcal{I}_{k+1} = \langle \chi_{k+1}(g_{k,1}), \dots, \chi_{k+1}(g_{k,\beta_k}) \rangle_{S_{k+1}} + \sum_{j \in \Theta_{k+1}} S_{k+1} \chi_{k+1}(g_{k+1,j}). $$

In other words, $\chi_{k+1}(g_{k,1}), \dots, \chi_{k+1}(g_{k,\beta_k})$ and the $\chi_{k+1}(g_{k+1,j})$'s, where $j \in \Theta_{k+1}$, is a set of generators of $\mathcal{I}_{k+1}$. If we set $\beta'_{k+1} = \beta_k + \mathrm{card}(\Theta_{k+1})$, $g'_{k+1,j} = g_{k,j}$ for $j = 1, \dots, \beta_k$, and $g'_{k+1,\beta_{k+1}} = g_{k+1,j}$ for $j \in \Theta_{k+1}$, then we have:

$$ \mathcal{I}_{k+1} = \langle \chi_{k+1}(g'_{k+1,1}), \dots, \chi_{k+1}(g'_{k+1,\beta'_{k+1}}) \rangle_{S_{k+1}}. \quad (62) $$

In the rest of the text, while considering a set of generators of $\mathcal{I}_{k+1}$, we shall assume eq. (62) for $k = 0, \dots, r-2$, i.e., $\mathcal{I}_{k+1} = \langle \chi_{k+1}(g_{k+1,1}), \dots, \chi_{k+1}(g_{k+1,\beta_{k+1}}) \rangle_{S_{k+1}}$, where $g_{k+1,j} = g_{k,j}$ for $j = 1, \dots, \beta_k$.

**Remark 21.** If $0 \to \mathcal{M}' \xrightarrow{f} \mathcal{M} \to \mathcal{M}'' \to 0$ is a short exact sequence of modules, then we have $\mathrm{Fitt}_i(\mathcal{M}') \mathrm{Fitt}_j(\mathcal{M}'') \subseteq \mathrm{Fitt}_{i+j}(\mathcal{M})$ for all $i, j \in \mathbb{Z}_{\ge 0}$. Thus, we get $\mathrm{Fitt}_0(\mathcal{M}') \mathrm{Fitt}_0(\mathcal{M}'') \subseteq \mathrm{Fitt}_0(\mathcal{M})$. See, e.g., [23]. Hence, if, for $k = 0, \dots, r-2$, we note $\mathcal{L}_k = \mathrm{Fitt}_0(\mathrm{coker}_{S_k}((\chi_k(L_{k-1,k}) \quad \chi_k(C_k))).)$, then $\mathcal{L}_{k+1} \mathcal{I}_{k+1} \subseteq S_{k+1} \otimes_S \mathcal{I}_k$ for $k = 0, \dots, r-2$.

**Corollary 5.** With the notations of the proof of Theorem 6 and, without loss of generality, assuming $\mathcal{I}_{k+1} = \langle \chi_{k+1}(g_{k+1,1}), \dots, \chi_{k+1}(g_{k+1,\beta_{k+1}}) \rangle_{S_{k+1}}$, where $g_{k+1,j} = g_{k,j}$ for $j = 1, \dots, \beta_k$, then the restriction of a solution $(u, v)$ of the rank factorization problem eq. (4) defined by eq. (59) from $\mathcal{V}_{\mathbb{K}}(\mathcal{J}_k)$ to $\mathcal{V}_{\mathbb{K}}(\mathcal{J}_{k+1})$ satisfy the following property:

$$ \forall u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_{k+1}) \setminus \mathcal{V}_{\mathbb{K}}(\langle g_{k,i} \rangle), \forall Y' \in \mathbb{K}^{t_{k,i} \times n}, \exists Y'' \in \mathbb{K}^{t_{k+1,i} \times n} : v_{h_{k,i}}(u, Y') = v_{h_{k+1,i}}(u, Y''). $$

In other words, the restrictions of the solutions of the rank factorization problem eq. (4) from $\mathcal{V}_{\mathbb{K}}(\mathcal{J}_k)$ to $\mathcal{V}_{\mathbb{K}}(\mathcal{J}_{k+1})$ are among the solutions defined in $\mathcal{V}_{\mathbb{K}}(\mathcal{J}_{k+1})$.
Proof. Let $B_k = V A K_k \in \mathbb{R}^{l \times q_k}$, $B_k = \text{coker}_{S_k}(\chi_k(B_k))$, and $\chi_k : \mathbb{R} \to S_k$ be the canonical ring epimorphism. Let $\mathcal{I}_k = \text{Fitt}_0(B_k) = \langle h_{k,1}, \dots, h_{k,\beta_k} \rangle_{S_k}$, $g_{k,j} \in \mathbb{R}$ be such that $h_{k,j} = \chi_k(g_{k,j})$ for $j = 1, \dots, \beta_k$. By notation (see the comment after eq. (62)), we have:

$$ \mathcal{I}_{k+1} = \langle \chi_{k+1}(g_{k+1,1}), \dots, \chi_{k+1}(g_{k+1,\beta_{k+1}}) \rangle_{S_{k+1}}, \quad g_{k+1,j} = g_{k,j}, \quad 1, \dots, \beta_k. $$

By Theorem 5, the solutions of the rank factorization problem defined over $S_k$ are eq. (59). Combining eq. (32), i.e., $\chi_{k+1}(K_k) = \chi_{k+1}(K_{k+1}) \chi_{k+1}(L_{k,k+1})$, with $B_k = V A K_k$, we have

$$ \begin{aligned} \chi_{k+1}(B_k) &= \chi_{k+1}(V) \chi_{k+1}(A) \chi_{k+1}(K_k) = \chi_{k+1}(V) \chi_{k+1}(A) \chi_{k+1}(K_{k+1}) \chi_k(L_{k,k+1}) \\ &= \chi_{k+1}(B_{k+1}) \chi_k(L_{k,k+1}), \quad k = 0, \dots, r-2, \end{aligned} $$

i.e., $B_k - B_{k+1} L_{k,k+1} \in \mathcal{J}_{k+1}^{l \times q_k}$, and thus, $B_k(u) = B_{k+1}(u) L_{k,k+1}(u)$ for all $u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_{k+1})$. We state again that $\chi_{k+1}(K_k) = \chi_{k+1}(K_{k+1}) \chi_{k+1}(L_{k,k+1})$ and:

$$ \begin{aligned} \forall u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_k) \setminus \mathcal{V}_{\mathbb{K}}(\langle g_{k,i} \rangle), & \quad B_k(u) E_{h_{k,i}}(u) = I_l, \\ \forall u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_{k+1}) \setminus \mathcal{V}_{\mathbb{K}}(\langle g_{k+1,i} \rangle), & \quad B_{k+1}(u) E_{h_{k+1,i}}(u) = I_l, \\ \forall u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_k) \setminus \mathcal{V}_{\mathbb{K}}(\langle g_{k,i} \rangle), & \quad B_k(u) C_{h_{k,i}}(u) = 0. \end{aligned} $$

Using $g_{k+1,i} = g_{k,i}$ for $i = 1, \dots, \beta_k$ and $\mathcal{V}_{\mathbb{K}}(\mathcal{J}_{k+1}) \subseteq \mathcal{V}_{\mathbb{K}}(\mathcal{J}_k)$, we then have:

$$ \forall u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_{k+1}) \setminus \mathcal{V}_{\mathbb{K}}(\langle g_{k,i} \rangle), \quad \left\{ \begin{array}{l} B_{k+1}(u) (L_{k,k+1}(u) E_{h_{k,i}}(u)) = I_l, \\ B_{k+1}(u) E_{h_{k+1,i}}(u) = I_l, \\ B_{k+1}(u) (L_{k,k+1}(u) C_{h_{k,i}}(u)) = 0, \\ K_k(u) = K_{k+1}(u) L_{k,k+1}(u). \end{array} \right. $$

From the first two identities, we get $B_{k+1}(u) (E_{h_{k+1,i}}(u) - L_{k,k+1}(u) E_{h_{k,i}}(u)) = 0$. Using eq. (53), i.e., $\ker_{\mathbb{K}}(B_{k+1}(u)) = \text{im}_{\mathbb{K}}(C_{h_{k+1,i}}(u))$ for all $u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_{k+1}) \setminus \mathcal{V}_{\mathbb{K}}(\langle g_{k,i} \rangle)$, there exists $O \in \mathbb{K}^{t_k \times q_{k+1}}$ which depends on $k, i, h_{i,k}$, and $u$ - such that such that $E_{h_{k+1,i}}(u) = L_{k,k+1}(u) E_{h_{k,i}} + C_{h_{k+1,i}}(u) O$. Similarly, there exists $O' \in \mathbb{K}^{t_{k+1} \times t_k}$ - which depends on $k, i, h_{i,k}$, and $u$ - such that the identity $L_{k,k+1}(u) C_{h_{k,i}}(u) = C_{h_{k+1,i}}(u) O'$. We then obtain

$$ \begin{aligned} \forall u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_{k+1}) \setminus \mathcal{V}_{\mathbb{K}}(\langle g_{k,i} \rangle), \forall Y' \in \mathbb{K}^{t_{k,i} \times n}, \\ v_{h_{k,i}}(u, Y') &= K_k(u) (E_{h_{k,i}}(u) Y + C_{h_{k,i}}(u) Y') \\ &= K_{k+1}(u) (L_{k,k+1}(u) E_{h_{k,i}}(u) Y + L_{k,k+1}(u) C_{h_{k,i}}(u) Y') \\ &= K_{k+1}(u) (E_{h_{k+1,i}}(u) Y + C_{h_{k+1,i}}(u) (O' Y' - O Y)) \\ &= v_{h_{k+1,i}}(u, O' Y' - O Y), \end{aligned} $$

which finally proves the result.

<figure><img src="image_7.png" /></figure>

**Example 14.** Let us illustrate Corollary 5 on Example 13. We can first check the identities $\chi_{k+1}(K_k) = \chi_{k+1}(K_{k+1}) \chi_k(L_{k,k+1})$ for $k = 0, 1, 2$, where:

$$ L_{0,1} = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}, \quad L_{1,2} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix}, \quad L_{2,3} = \begin{pmatrix} 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 \end{pmatrix}. $$

We can also check again that all the entries of the matrices $K_k - K_{k+1} L_{k,k+1}$ belong $\mathcal{J}_{k+1}$ for $k = 0, 1, 2$. We also have $\chi_k(B_k) = \chi_k(B_{k+1}) \chi_k(L_{k,k+1})$ for $k = 0, 1, 2$, i.e., all the entries of the matrix $B_k - B_{k+1} L_{k,k+1}$ belong to $\mathcal{J}_{k+1}$ for $k = 0, 1, 2$. Moreover, all the entries of $L_{k,k+1} C_{h_k}$ belong to $\mathcal{J}_{k+1}$, i.e., $L_{k,k+1}(u) C_{h_k}(u) = 0$ for all $u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_{k+1})$, i.e., we have $L_{k,k+1}(u) C_{h_k}(u) = C_{h_{k+1}}(u) O'$, where $O'$ is
a zero matrix of the appropriated size. Similarly, we have $E_{h_1} = L_{0,1} E_{h_0}$ and $E_{h_2} = L_{1,2} E_{h_1}$. Note that $E_{h_3} - L_{2,3} E_{h_2} = 3/2 (-y \ 0 \ y \ 0)^T$ is not in the image of the matrix $C_{h_3}$ defined by eq. (12). It does not contradict Corollary 5 once we have noticed that $g_2 = x_1 - x_4$ and $g_3 = x_4$. As explained in eq. (12) (see eq. (62)), we must assume that the generator of $\mathcal{I}_3$ is $\chi_3(g_2) = -2x_4$. In this case, a right inverse of $\chi_3(B_3) = (-x_4 \ 0 \ x_4 \ 0)$ with entries in $S_{3\chi_3(g_2)}$ is, for instance, $E_{h_3} = (y \ 0 \ -y \ 0)^T$. Hence, we obtain $E_{h_3} = L_{2,3} E_{h_2}$. We thus have $E_{h_{k+1}}(u) = L_{k,k+1}(u) E_{h_k} + C_{h_{k+1}}(u) O$ for all $u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_{k+1})$, where $O$ is a zero matrix of the appropriate size. Finally, we can check again that $v_{h_k}(u, Y') = v_{h_{k+1}}(u, 0)$ for all $u \in \mathcal{V}_{\mathbb{K}}(\mathcal{J}_{k+1}) \setminus \mathcal{V}_{\mathbb{K}}(\langle g_k \rangle)$ and for all $Y'$.

# 5 Conclusion

In this paper, we have studied the general solutions of the rank factorization problem eq. (4). This last problem is connected to demodulation problems studied in gearbox vibration analysis [14, 15]. Using module theory, homological, and computer algebra methods, we have shown how to characterize the general solutions of this rank factorization problem. The results obtained in [16, 17, 18, 19], which characterize a particular class of solutions, are found again and generalized. The characterization of the general solutions obtained here is effective and can be implemented in modern computer algebra systems. In particular, it was implemented in the RANKFACTORIZATION package (built upon the OREMODULES package [6]) dedicated to the rank factorization problem eq. (4) and its applications.

Many important issues on the rank factorization problem eq. (4) still have to be investigated such as, for instance, the algebraic geometric interpretation of its solution space using projective geometry.

A first remark in this direction is that if $(u, v)$ is a solution of eq. (4), then so is $(\lambda u, \lambda^{-1} v)$ for all $\lambda \in \mathbb{K}^\times = \mathbb{K} \setminus \{0\}$. Hence, $\mathbb{K}^\times$ defines a group action on the solution space of eq. (4) and the orbit $O_{(u,v)} = \{(\lambda u, \lambda^{-1} v) \mid \lambda \in \mathbb{K}^\times\}$ could be considered instead of the solution $(u, v)$ only.

A second remark is that eq. (4) can be transformed into a multi-homogeneous polynomial system over a multi-projective space [26]. Indeed, writing $v = (v_{\bullet 1} \dots v_{\bullet n})$ (resp., $M = (M_{\bullet 1} \dots M_{\bullet n})$), where $v_{\bullet i} \in \mathbb{K}^{r \times 1}$ (resp., $M_{\bullet i} \in \mathbb{K}^{m \times 1}$) denotes the $i^{th}$ column of $v$ (resp., $M$), eq. (1) can be rewritten as $A(u)v_{\bullet i} = M_{\bullet i}$ for $i = 1, \dots, n$, and introducing the new variables $u_0$ and $v_{0i}$ for $i = 1, \dots, n$, and $M_h = u_0(v_{01} M_{\bullet 1} \dots v_{0n} M_{\bullet n})$, the change of variables $u \leftarrow u/u_0$ and $v_{\bullet i} \leftarrow v_{\bullet i}/v_{0i}$, $i = 1, \dots, n$, in $A(u)v_{\bullet i} = M_{\bullet i}$ for $i = 1, \dots, n$ then yields the following multi-homogeneous polynomial system

$$A(u)v = M_h \qquad (63)$$

of degree (1, 1) with respect to the partition $\{u_0, u_1, \dots, u_m\} \cup \{v_{0j}, v_{1j}, \dots, v_{rj}\}$ of the variables. Since $(u_0, u_1, \dots, u_n)$ (resp., $(v_{0j}, v_{1j}, \dots, v_{rj})$) is a point of the projective space $\mathbb{P}^n(\mathbb{K})$ (resp., $\mathbb{P}^r(\mathbb{K})$), the solutions of eq. (63) can be sought in the multi-projective space [26]:

$$\underbrace{\mathbb{P}^m(\mathbb{K}) \times \mathbb{P}^r(\mathbb{K}) \times \dots \times \mathbb{P}^r(\mathbb{K})}_{n}.$$

In vibration analysis, the complex matrices $D_i$'s and $M$ are centrohermitian. The solutions of the corresponding rank factorization problem eq. (4) are sought to also be centrohermitian. As explained in Section 1, the corresponding rank factorization problem can be transformed into an equivalent rank factorization problem for real matrices $\rho(D_i)$'s and $\rho(M)$. Symbolic-numeric methods will be used in the future to obtain certified numerical solutions to the rank factorization problem eq. (4) for $\mathbb{K} = \overline{\mathbb{Q}}$ or $\mathbb{R}$, and thus, to the corresponding vibration problem by transforming back the obtained real solutions to centrohermitian solutions of the original problem. For more details, see [18].

In practice, the matrices $D_i$'s are explicitly known because they are fixed by the demodulation problem under study, contrary to $M$ which is only measured. Hence, the matrix $M$ is obtained through noisy measurement. Thus, Problem eq. (1) corresponds to the ideal demodulation problem, i.e., to the case with no perturbations and noise corrupting the measured signal. In practice, i.e., when $M$ is not supposed to be exactly known, one usually prefers to consider the following optimization problem

$$\arg \min_{u \in \mathrm{CH}_{n,1}, v_i \in \mathrm{CH}_{1,m}} \left\| \sum_{i=1}^{r} D_i u v_i - M \right\|_{\mathrm{Frob}}, \qquad (64)$$