Solvability of the Sylvester equation $AX-XB = C$ under left semi-tensor product

1.   Introduction

Matrix equations have become an important part of matrix theory, and have been successfully applied in many fields, such as control theory, physics, electronic technology, sensing technology, cryptography, and so on ^[1,2,3,4]. The main work of this paper is to study the solvability of the Sylvester matrix equation with respect to left semi-tensor product. As an important role in control theory, it plays an important role in dynamic systems, neural network systems, robust control, and other directions ^[5,6,7]. Many mathematics professors and cybernetics experts from world-renowned universities and scientific research institutions have conducted in-depth research on the Sylvester matrix equation. For example, Professor Roth ^[8] proved the compatibility condition of the Sylvester matrix equation, that is, the famous Roth theorem. Professor G. Golub ^[9] studied the Sylvester equation by Hesenberg-Schur method. Professor Varga of the German Aerospace Center ^[10] considered the application of the Sylvester equation in robust pole assignment. Professor Kågström ^[11] studied the compatibility of matrix equations containing any Sylvester and ^*-Sylvester by using the equivalence relationship of the matrix.

Professor Cheng ^[12] proposed the semi-tensor product of matrices to solve linearization problems in nonlinear systems. It has been widely used in many fields, such as physics in nonlinear systems, graphs ^[13], and Boolean networks ^[14]. Recently, Yao and Feng ^[15] discussed the solution of the matrix equation $AX = B$ with respect to semi-tensor product. Li ^[16] studied the solvability of the matrix semi-tensor product $AXB = C$. Based on this, the solvability of the famous Sylvester matrix equation $AX-XB = C$ in which the matrix multiplication is left semi-tensor product is studied in this paper.

There are six sections in this paper. The remaining five sections are structured as follows: we introduce some fundamental definitions and properties in section 2. In section 3, we study the solution of the Sylvester matrix equation $AX-XB = C$ by investigating the matrix-vector equation in two cases. In section 4, we discuss the solvability of the matrix equation $AX-XB = C$ in two cases. We provide some examples to illustrate the results in section 5 and draw our conclusion in section 6.

Some notations are presented as follows:

(1). $\mathbb{C}_{p}$ : the vector space of complex $p$-tuples.

(2). $\mathbb{C}_{m\times n}$ : the vector space of $m\times n$ complex matrices.

(3). $lcm(r, s)$: the least common multiple of two positive integers $r$ and $s$.

(4). $gcd(r, s)$: the greatest common divisor of two positive integers $r$ and $s$.

(5). $A_{i}$ : the $i$-th column of $A$.

2.   Preliminaries

In this section, we briefly review some fundamental definitions and properties which will be used in the following.

Definition 2.1. (^[17]) The Kronecker product of two matrices $A = ({a}_{ij})\in \mathbb{C}^{m\times r}$ and $B = ({b}_{ij})\in \mathbb{C}^{s\times n}$ is

where $\otimes$ is the Kronecker product.

Definition 2.2. (^[17]) With each matrix $A = ({a}_{ij})\in \mathbb{C}^{m\times r}$, denoted by $V_{c}(A)$ is defined as

Proposition 2.1. (^[17]) Let $A \in \mathbb{C}^{m\times r}$, $B \in \mathbb{C}^{r\times s}$ and $C \in \mathbb{C}^{s\times n}$. Then we have the following

Lemma 2.1. (^[17]) Let $A\in \mathbb{C}^{m\times m}$, $B\in \mathbb{C}^{n\times n}$ and $C\in \mathbb{C}^{m\times n}$. $X\in \mathbb{C}^{m\times n}$ is unknown.Then the solvability of the Sylvester matrix equation $AX-XB = C$ is equivalent to the solvability of the matrix-vector equation

Definition 2.3. (^[12]) Let $A = ({a}_{ij})\in \mathbb{C}^{m\times r}$, $B = ({b}_{ij})\in \mathbb{C}^{s\times n}$. The left semi-tensor product of $A$ and $B$ is defined as

where $t = lcm(r, s)$.

3.   Solvability of the Sylvester matrix-vector equation $AX-XB=C$

In this section, we discuss the solvability of the Sylvester matrix-vector equation

under left semi-tensor product, where $A\in \mathbb{C}^{m\times r}$, $B\in \mathbb{C}^{s\times n}$, and $C\in \mathbb{C}^{h\times k}$ are known. The problem is to find a vector $X$ satisfying matrix-vector equation (3.1). Firstly, we investigate the simple case $m = h$, then we discuss the general case.

3.1.   The case m=h

In this subsection, we study the solvability of the Sylvester matrix-vector equation (3.1) under left semi-tensor product, where $A\in \mathbb{C}^{m\times r}$, $B\in \mathbb{C}^{s\times n}$, $C\in \mathbb{C}^{m\times k}$. $X\in \mathbb{C}^{p\times 1}$ is an unknown vector. By Definition 2.3, we have the following lemma.

Lemma 3.1. If the Sylvester matrix-vector equation (3.1) exists a solution, then $\frac{r}{k}$ and $\frac{m}{s}$ are positive integers. In fact, $\frac{r}{k} = \frac{m}{s} = p$.

Proof. By Definition 2.3, we have

and

where $t = lcm(r, p)$. We obtain that $m = \frac{mt}{r} = sp$, $k = \frac{t}{p} = n$. Then, $t = r$ and $k = \frac{t}{p} = \frac{r}{p}$. Consequently, $\frac{r}{k}$ and $\frac{m}{s}$ are positive integers. Furthermore, $\frac{r}{k} = \frac{m}{s} = p$. Hence, if the solution of the matrix-vector equation (3.1) exists, $\frac{r}{k}$ and $\frac{m}{s}$ are required to be positive integers and $\frac{r}{k} = \frac{m}{s} = p$. The proof is completed.

Remark 3.1. When $p = m = r, k = n = s = 1$, the solvability of the Sylvester matrix-vector equation $AX-XB = C$ under left semi-tensor product becomes conventional case.

Now we investigate the solvability of the Sylvester matrix-vector equation (3.1). Suppose that

Then, the Sylvester matrix-vector equation (3.1) can be rewritten as

where $\widehat{A_{1}}$, $\widehat{A_{2}}$, $\ldots$, $\widehat{A_{p}}$ are $p$ equal-size blocks of matrix $A$, $\widehat{D_{1}}$, $\widehat{D_{2}}$, $\dots$, $\widehat{D_{p}}$ are $p$ equal-size blocks of matrix $I_{p} \otimes B$. Accordingly, we establish the following result.

Theorem 3.1. The Sylvester matrix-vector equation (3.1) exists a solution if and only if $\widehat{A_{1}}-\widehat{D_{1}}$, $\widehat{A_{2}}-\widehat{D_{2}}$, $\ldots$, $\widehat{A_{p}}-\widehat{D_{p}}$ and $C$ are linearly dependent in vector space $\mathbb{C}^{m\times k}$. Moreover, if $\widehat{A_{1}}-\widehat{D_{1}}$, $\widehat{A_{2}}-\widehat{D_{2}}$, $\ldots$, $\widehat{A_{p}}-\widehat{D_{p}}$ are linearly independent, the solution would be unique.

Corollary 3.1. If the Sylvester matrix-vector equation (3.1) exists a solution, the following rank condition holds:

Here, we have a necessary condition for the solvability of the Sylvester matrix-vector equation (3.1). In particular, when the Sylvester matrix-vector equation $AX-XB = C$ with respect to conventional matrix product, condition (3.3) is a necessary and sufficient one. The following is an example to illustrate it.

Example 3.1. (i) Let matrices $A$, $B$, $C$ as following:

It is easy to verify that

is a solution. Obviously, it satisfies condition (3.3).

(ii) Let

and $A$, $B$ are the same as (i). Clearly, it satisfies condition (3.3), but the matrix-vector equation (3.1) has no solution.

It is easy to know that the equation (3.2) is equivalent to the following equation:

Next, we have the following equivalent form.

Theorem 3.2. The Sylvester matrix-vector equation $AX-XB = C$ under semi-tensor product is equivalent to the following matrix-vector equation under conventional matrix product:

where

$A_{i}$, $D_{i}$ are the $i$-th column of $A$ and $I_{p} \otimes B$, respectively.

Corollary 3.2. The Sylvester matrix-vector equation (3.1) exists a solution if and only if

Remark 3.2. Here $\bar{D} = I_{p} \otimes \bar{B}^\mathrm{T}$, then the Sylvester matrix-vector equation (3.1) exists a solution if and only if

3.2.   The general case

In this subsection, we study the solvability of the Sylvester matrix-vector equation (3.1) with $m \neq h$. We give the following lemma, which presents a necessary condition for solvability of the Sylvester matrix-vector equation (3.1).

Lemma 3.2. If the Sylvester matrix-vector equation (3.1) exists a solution, the orders of matrices $A$, $B$, and $C$ satisfy the following two conditions:(i)$\frac{h}{m}$ and $\frac{r}{k}$ are positive integers.(ii)$gcd(k, \frac{h}{m}) = 1$. Actually, $\frac{rh}{mk} = p$.

Proof. By Definition 2.3, we have

and

where $t = lcm(r, p)$. We obtain that $h = \frac{mt}{r} = sp$, $k = \frac{t}{p} = n$. Then, $\frac{h}{m} = \frac{t}{r}$ and $k = \frac{t}{p}$. So, $t = \frac{rh}{m}$ and $\frac{t}{k} = \frac{rh}{mk} = p$. Consequently, $\frac{h}{m}$ and $\frac{k}{r}$ are positive integers. Furthermore, $t = \frac{rh}{m} = lcm(r, p) = lcm(r, \frac{rh}{mk})$. Then $lcm(r, \frac{rh}{mk}) = \frac{r}{k}lcm(k, \frac{h}{m})$. Thus, $lcm(k, \frac{h}{m}) = k \cdot \frac{h}{m}$. Therefore, $gcd(k, \frac{h}{m}) = 1$. Hence, if the Sylvester matrix-vector equation (3.1) exists a solution, the two conditions are required. The proof is completed.

Next, we study the solvability of the equation. Suppose that $i \cdot k = l_{1}^{i} \cdot \frac{h}{m}+ l_{2}^{i}$, $i = 1, \dots, \frac{h}{m}$. We can rewrite them in the following form:

where

and $\tilde{C}_{j}$ is the $j$-th column of $\tilde{C}$. Therefore we obtain the following result.

Theorem 3.3. The solvability of the Sylvester matrix-vector equation (3.1) is equivalent to the solvability of the following matrix-vector equations:

where

and

Consequently, if the Sylvester matrix-vector equations (3.4) exist solutions

where $i = 1, \dots, \frac{h}{m}$, then

is the solution of the Sylvester matrix-vector equation (3.1).Therefore, we obtain a necessary and sufficient condition for the solvability of the Sylvester matrix-vector equation (3.1).

Denote

A necessary and sufficient condition for the solvability of the Sylvester matrix-vector equation (3.1) is obtained.

Corollary 3.3. The Sylvester matrix-vector equation $AX-XB = C$ exists a solution if and only if $\check{A}_{j}-\check{D}_{j}$, $\check{A}_{\frac{h}{m}+j}-\check{D}_{\frac{h}{m}+j}$, $\dots$, $\check{A}_{(\frac{r}{k}-1)\frac{h}{m}+j}-\check{D}_{(\frac{r}{k}-1)\frac{h}{m}+j}$ and $\widetilde{C}_{j}$ are linearly dependent, $j = 1, 2, \dots, \frac{h}{m}$. Moreover, if $\check{A}_{j}-\check{D}_{j}$, $\check{A}_{\frac{h}{m}+j}-\check{D}_{\frac{h}{m}+j}$, $\dots$, $\check{A}_{(\frac{r}{k}-1)\frac{h}{m}+j}-\check{D}_{(\frac{r}{k}-1)\frac{h}{m}+j}$ are linearly independent, $j = 1, 2, \dots, \frac{h}{m}$, then the solution of Sylvester matrix-vector equation $AX-XB = C$ would be unique.

4.   Solvability of the Sylvester matrix equation $AX-XB=C$

In this section, we discuss the solvability of the Sylvester matrix equation

under left semi-tensor product, where $A\in \mathbb{C}^{m\times r}$, $B\in \mathbb{C}^{s\times n}$, and $C\in \mathbb{C}^{h\times k}$ are known. The problem is to find a matrix $X$ satisfying matrix equation (4.1). Firstly, we investigate the simple case $m = h$, then we discuss the general case.

4.1.   The case m=h

In this subsection, we study the solvability of matrix equation (4.1) under left semi-tensor product, where $A\in \mathbb{C}^{m\times r}$, $B\in \mathbb{C}^{s\times n}$, and $C\in \mathbb{C}^{m\times k}$. $X\in \mathbb{C}^{p\times q}$ is an unknown matrix. By Definition 2.3, we have the following lemma.

Lemma 4.1. If the Sylvester matrix equation (4.1) exists a solution, then $\frac{r}{\alpha} = \frac{mn}{\beta} = p$, $\frac{k}{\alpha} = \frac{sk}{\beta} = q$, where $\alpha$ is a common divisor of $r$ and $k$, $\beta$ is a common divisor of $sk$ and $mn$.

Proof. By Definition 2.3, we have

and

where $t = lcm(r, p)$, $l = lcm(q, s)$. We obtain that $m = \frac{mt}{r} = \frac{pl}{q}$, $k = \frac{qt}{p} = \frac{nl}{s}$. Then, $t = r$ and $p = \frac{qt}{k} = \frac{qr}{k} = \frac{r}{k}\cdot q$. Consequently, $\frac{r}{\alpha} = p$ and $\frac{k}{\alpha} = q$, where $\alpha$ is a common divisor of $r$ and $k$. And $l = \frac{ks}{n}$, $\frac{m}{p} = \frac{l}{q}$. Moreover, $\frac{m}{p} = \frac{l}{q} = \frac{ks}{nq}$, $\frac{mn}{sk}q = p$. Hence, $\frac{sk}{\beta} = q$, $\frac{mn}{\beta} = p$, where $\beta$ is a common divisor of $sk$ and $mn$. Therefore, if the matrix equation (4.1) exists a solution, then $\frac{r}{\alpha} = \frac{mn}{\beta} = p$, $\frac{k}{\alpha} = \frac{sk}{\beta} = q$. The proof is completed.

Remark 4.1. When the orders $p_{i} \times q_{i}$ satisfies Lemma 4.1, we call them admissible orders, where $i = 1, 2, \dots, u$. And $\alpha_{i}$ are all the common divisor of $r$ and $k$, $\beta_{i}$ are all the common divisor of $mn$ and $sk$.

(i) When $\alpha = 1$, $\beta = n$, we have $p = r = m$, $q = k = s = n$, and the product becomes conventional product.

(ii) If $\alpha = gcd(r, k), \beta = gcd(mn, sk)$, the Sylvester matrix equation (4.1) exists a solution for the minimum order $\bar{p} \times \bar{q}$. And the Sylvester matrix equation (4.1) exists a solution for every admissible order.

Now we study the solvability of the Sylvester matrix equation (4.1). Firstly, we consider the solutions for the minimum order $\bar{p} \times \bar{q}$, then the matrix equation exists a solution for other admissible order can be studied. By Definition 2.3, the Sylvester matrix equation (4.1) can be rewritten as

where $\widehat{A}_{1}, \widehat{A}_{2}, \ldots, \widehat{A}_{\bar{p}}$ are $p$ equal-size blocks of matrix $A$, $\widehat{B}_{1}, \widehat{B}_{2}, \ldots, \widehat{B}_{\bar{p}}$ are $\bar{p}$ equal-size blocks of matrix $B$, $\widehat{C}_{1}, \widehat{C}_{2}, \ldots, \widehat{C}_{\bar{q}}$ are $\bar{q}$ equal-size blocks of matrix $C$. Consequently, equation (4.2) is equivalent to the following matrix-vector equations under left semi-tensor product:

$X_{j}\in \mathbb{C}^{\bar{p}}$, $j = 1, \dots, \bar{q}$. Thus we have the following results.

Theorem 4.1. The Sylvester matrix equation (4.1) exists a solution $X \in \mathbb{C}^{\bar{p}\times \bar{q}}$, if and only if $\widehat{A}_{1}, \widehat{A}_{2}, \ldots, \widehat{A}_{\bar{p}}$, $\widehat{B}_{1}, \widehat{B}_{2}, \ldots, \widehat{B}_{\bar{p}}$ and $\widehat{C}_{j}$ are linearly dependent, $j = 1, 2, \dots, \bar{q}$. Moreover, if $\widehat{A}_{1}, \widehat{A}_{2}, \ldots, \widehat{A}_{\bar{p}}$, $\widehat{B}_{1}, \widehat{B}_{2}, \ldots, \widehat{B}_{\bar{p}}$ are linearly independent, the solution would be unique.

Corollary 4.1. If the Sylvester matrix equation (4.1) exists a solution, the following rank condition holds:

Similar to the matrix-vector case, condition (4.3) is a necessary.

In order to solve the solution of the Sylvester matrix equation $AX-XB = C$, we have the following equivalent form.

Theorem 4.2. The Sylvester matrix equation $AX-XB = C$, $X \in \mathbb{C}^{\bar{p}\times \bar{q}}$, under left semi-tensor product is equivalent to the following matrix-vector equation with conventional matrix product:

where

and $A_{i}$, $B_{i}$ are the i-th column of A and B, respectively.

Corollary 4.2. The Sylvester matrix equation $AX-XB = C$ exists a solution $X \in \mathbb{C}^{p\times q}$ if and only if the following rank condition holds:

4.2.   The general case

In this subsection, we study the solvability of the Sylvester matrix equation (4.1) with $m \neq h$. We give the following lemma, which presents a necessary condition for solvability of the matrix equation (4.1).

Lemma 4.2. If the Sylvester matrix equation (4.1) exists a solution $X \in \mathbb{C}^{p\times q}$, the orders of matrices $A$, $B$ and $C$ satisfy the following two conditions:(i) $\frac{h}{m}$ and $\frac{k}{n}$ are positive integers.(ii) $\frac{rh}{m\alpha} = \frac{h}{\beta} = p$ and $\frac{k}{\alpha} = \frac{sk}{n\beta} = q$, where $\alpha$ is a common divisor of $r$ and $k$, $\beta$ is a common divisor of $s$ and $h$. Moreover, it satisfies $gcd(\alpha, \frac{h}{m}) = 1$, $gcd(\beta, \frac{k}{n}) = 1$.

Proof. (ⅰ) By Definition 2.3, we suppose that matrix equation (4.1) exists a solution $X$, and its order is $p \times q$, we can obtain that $\frac{mt}{r} = \frac{lp}{q} = h$, $\frac{qt}{p} = \frac{ln}{s} = k$. Then $t = \frac{rh}{m}$, $l = \frac{sk}{n}$. Consequently, $\frac{h}{m}$ and $\frac{k}{n}$ are positive integers, where $t = lcm(r, p)$, $l = lcm(q, s)$.

(ⅱ) Supposing the matrix equation (4.1) exists a solution $X \in \mathbb{C}^{p\times q}$, we can get $\frac{mt}{r} = \frac{lp}{q} = h$, $\frac{qt}{p} = \frac{ln}{s} = k$. Then $t = \frac{rh}{m}$, $\frac{t}{p} = \frac{k}{q}$. Denote $\alpha = \frac{rh/m}{p} = \frac{t}{p} = \frac{k}{q}$. Then we have $\frac{rh}{m\alpha} = p$, $\frac{k}{\alpha} = q$. Consequently, $\frac{r}{\alpha}$ is a positive integer, and $\alpha$ is a common divisor of $r$ and $k$, and $gcd(\alpha, \frac{h}{m}) = 1$. As the same way, $l = \frac{sk}{n}$, $\frac{h}{p} = \frac{l}{q}$. Denote $\beta = \frac{sk}{qn} = \frac{l}{q} = \frac{h}{p}$. Then we have $\frac{sk}{n\beta} = q$, $\frac{h}{\beta} = p$. Consequently, $\frac{s}{\beta}$ is a positive integer, and $\beta$ is a common divisor of $s$ and $h$, and $gcd(\beta, \frac{k}{n}) = 1$. The proof is completed.

Remark 4.2. (i) $\frac{h}{m}$ and $\frac{k}{n}$ are positive integers is a necessary condition for the solvability of the Sylvester matrix equation $AX-XB = C$.

(ii) The orders, which satisfy the conditions in Lemma 4.2, are called admissible orders. When $\alpha = 1$, $\beta = 1$, we have $\frac{rh}{m} = h = p$, $k = \frac{sk}{n} = q$, then $m = r$, $s = n$. The Sylvester matrix equation $AX-XB = C$ can transform into

with respect to the conventional product.

5.   Some examples

In this section, two numerical examples are given. One is about matrix-vector equation, and the other one is about general matrix equation.

Example 5.1. (i) Let matrices $A$, $B$, $C$ as follows:

It is easy to verify that

is a solution. $\frac{2}{2}, \frac{4}{2}$ are positive integers, and the given matrices satisfy the conditions of the Lemma 3.1.

(ii) Let matrices $A$, $B$, $C$ as follows:

Clearly, $\frac{5}{2}$, $\frac{4}{3}$ are not positive integers, the given matrices do not satisfy the conditions of the Lemma 3.2. So the equation has no solution.

(iii) Let matrices $A$, $B$, $C$ as follows:

It is easy to verify that

is a solution. $\frac{4}{2}$, $\frac{3}{3}$ are positive integers, and $gcd(k, \frac{h}{m}) = gcd(3, 2) = 1$. Consequently, it is a necessary condition for solvability of the Sylvester matrix-vector equation (3.1).

Example 5.2. (i) We reconsider items (i) in Example 5.1.

Take matrices $A$, $B$, $C$ as following:

Obviously, the admissible orders of solutions are $2 \times 1, 4 \times 2$. And we have the solution

in Example 5.1. Moreover, $X_{a}$ is the unique solution for admissible order $2 \times 1$. Meanwhile, $X_{b} = X_{a} \otimes I_{2}$, and $X_{b}$ is the unique solution for admissible order $4 \times 2$.

(ii) Take matrices $A$, $B$, $C$ as following:

As $\frac{7}{4}, \frac{8}{3}$ are not positive integers, the given matrices do not satisfy the conditions of the Lemma 4.2 and the equation has no solution.

(iii) Take matrices $A$, $B$, $C$ as following:

It is easy to verify that

is a solution of the Sylvester matrix equation (4.1). We find $\frac{8}{4}, \frac{9}{3}$ are positive integers, and $p = 2, q = 3$. Moreover, the given matrices satisfy the conditions of the Lemma 4.2.

6.   Conclusion

In this paper, we discuss the solvability of the Sylvester matrix equation $AX-XB = C$ with respect to left semi-tensor product. Firstly, we divide the solution $X$ into two kinds: the matrix-vector equation one and the matrix equation one. For the matrix-vector equation case, we discuss a necessary and sufficient condition for the solvability and concrete solving methods. Based on this, the solvability of the Sylvester matrix equation under left semi-tensor product has been studied. At last, we give several examples to illustrate the efficiency of the results.

Acknowledgment

This research work is partially supported by undergraduate education reform project of Shandong Normal University (No. 2021BJ054).

Conflict of interest

The author declares that there is no conflicts of interest in this paper.