Solvability of the matrix equation $AX^{2} = B$ with semi-tensor product

1.   Introduction

Matrix theory plays an important role in many fields such as system and control theory [10,3,1,2], automation and information sciences [15], economic theory [23], physics [16,14] and computing sciences [19,11]. On the other hand, matrix theory is the basis of numerical calculation and is effective to deal with the one-dimensional array (linear function) and two dimensional array (double linear function or secondary). However, matrix multiplication of $A$ and $B$ requires that the number of columns of $A$ and the number of rows of $B$ are equal. Therefore, it is difficult to solve multiple linear problems and nonlinear problems directly by traditional matrix method. Cheng [5] proposed the semi-tensor product of matrices to settle this dilemma. As a convenient and powerful new mathematical tool, it keeps the main properties of original matrix multiplication and has nice features. It has been quickly applied to fields such as mathematics, physics in nonlinear systems, and Boolean networks. Recently, the solutions of the matrix equation $AX = B$ in which the multiplication is semi-tensor product was discussed by Yao and Feng [21,7] in optimization and control analysis problems. The higher-order equation $XX = R$ was also mentioned by Fan [6] in the investigation of fuzzy relation decomposition problems. In fact, high-order algebraic equations have important applications in file encryption and file transmission [17,18]. Furthermore, the equation solution of high order logical matrix is very useful in the decoupling of logical networks [22]. Based on this, the solvability of the matrix equation $AX^{2} = B$ in which the multiplications are semi-tensor product is studied in this paper.

To achieve the goal, we will study the matrix equation $AX^{2} = B$ with semi-tensor product by the following steps. The solvability of $AX^{2} = B$ will be discussed in two cases. In each case we give the compatible conditions on $A$ and $B$ firstly and then discuss necessary and sufficient condition for the solvability. Then concrete methods are provided. At the end, we give examples to verify the effectiveness of the results.

There are five sections in this paper. We introduce notations and definitions in Section 2 and study in Section 3 the solvability of the matrix equation $AX^{2} = B$ through investigating matrix equations $AY = B$ and $X^{2} = Y$ simultaneously in both cases. The first case is a matrix-vector equation and the other is a general matrix equation. We provide some examples to illustrate the results in Section 4 and draw our conclusion on Section 5.

2.   Preliminaries

Throughout this paper, ${\mathbb C}^n$ denotes the set of complex column vectors of dimension $n$, ${\mathbb C}_{m\times n}$ denotes the vector space of $m\times n$ complex matrices and $A^T$ denotes the transpose of $A\in {\mathbb C}_{m\times n}$. Let ${lcm}(m,n)$ and $\gcd(m,n)$ be the least common multiple and the greatest common divisor of two positive integers $m$ and $n$, respectively. Let $A = [a_{ij}]\in {\mathbb C}_{m\times n}$ and $B = [b_{ij}]\in {\mathbb C}_{p\times q}$. The Kronecker product $A\otimes B$ of $A$ and $B$ is [9]:

The semi-tensor product $A\ltimes B$ of $A\in {\mathbb C}_{m\times n}$ and $B\in {\mathbb C}_{p\times q}$ is [3]:

where $t = {lcm}(n,p)$.

Remark 1. $A\ltimes B = (A\otimes I_{a})\ltimes B$ if and only if ${lcm}(na,p) = {lcm}(n,p)$. Similarly, $A\ltimes B = A\ltimes (B\otimes I_{b})$ if and only if ${lcm}(n,pb) = {lcm}(n,p)$.

Noting that when $n = p$, we have $t = n$ and the semi-tensor product coincides with the conventional matrix product. Thus, in this paper, we always consider $AB$ as $A\ltimes B$. The vectorization of $A\in {\mathbb C}_{m\times n}$, denoted by ${\rm{vec}} (A)\in {\mathbb C}^{mn}$ is defined as [9]:

The vectorization is often used together with the Kronecker product to express matrix multiplication as a linear transformation on matrices. For $A\in {\mathbb C}_{k\times \ell}$, $B\in {\mathbb C}_{\ell\times m}$ and $C \in {\mathbb C}_{m\times n}$,

3.   Solvability of the matrix equation $AX^{2}=B$

With respect to the semi-tensor product, if $X$ is a solution of $AX^{2} = B$, then $X$ satisfies the matrix equations $AY = B$ and $X^{2} = Y$ simultaneously. Note that $AX^{2} = B$ means that $A\ltimes(X\ltimes X) = B$. We will decompose the equation $AX^{2} = B$ into two equations $AY = B$ and $X^{2} = Y$.

3.1.   The case $X\in {\mathbb C}_{a\times 1}$ and $Y\in {\mathbb C}_{p\times 1}$

We now study the solvability of the matrix-vector equation with semi-tensor product

where $A\in {\mathbb C}_{m\times n}, \; B\in {\mathbb C}_{h\times k},\; X\in {\mathbb C}_{a\times 1}$ is an unknown vector.

3.1.1.   The equation $X^{2}=Y$

In this subsection, we discuss the solvability of the equation with semi-tensor product

where $X\in {\mathbb C}_{a\times 1}$ and $Y\in {\mathbb C}_{p\times 1}$.

By the definition of semi-tensor product, we have

Thus, we establish the following lemma.

Lemma 3.1. The following is a necessary and sufficient condition on $Y$ for the solvability of $X^{2} = X\ltimes X = Y$

where

and $p = a^{2}$.

Theorem 3.2. If equation ($6$) has solution, then $x_{i} = \pm\sqrt{y_{(i-1)a+i}}, \; i = 1,\dots,a$.

3.1.2.   The matrix-vector equation $AY=B$

In this subsection, we discuss the solvability of the matrix-vector equation with semi-tensor product

where $A\in {\mathbb C}_{m\times n}$, $B\in {\mathbb C}_{h\times k}$ and $Y\in {\mathbb C}_{p\times 1}$ is an unknown vector.

Lemma 3.3. If $AY = B$ has solution, then the following conditions must hold.

1. $\frac{h}{m}$ and $\frac{ n}{k}$ must be positive integers, $\gcd (k, \frac{h}{m}) = 1$, and $(a^{2} = )p = \frac{nh}{mk}$ is a square integer;

2. $B = \begin{bmatrix} {\rm{Block}}_{1}(B)\\ \vdots \\ {\rm{Block}}_{m}(B)\\ \end{bmatrix}$, where ${\rm{Block}}_{i}(B)\in {\mathbb C}_{\frac{h}{m}\times k}$, $i = 1,\dots,m$, are Toeplitz matrices.

Proof. $(1)$ By investigating $B = A\ltimes Y = (A\otimes I_{t/n})(Y\otimes I_{t/p}) \in {\mathbb C}_{(mt/n)\times(t/p)}$, where $t = {lcm}(n,p)$, we obtain that $h = \frac{mt}{n}$, $k = \frac{t}{p}$. Because of $\frac{h}{m} = \frac{t}{n}$ and $t = \frac{nh}{m}$, $\frac{h}{m}$ is a positive integer. On the other hand $p = \frac{t}{k} = \frac{nh}{mk}$ and $t = \frac{nh}{m} = {lcm}(n,p) = {lcm}(n,\frac{nh}{mk})$, so $\frac{n}{k}$ must be a positive integer. Furthermore, ${lcm}(n,\frac{nh}{mk}) = \frac{n}{k}\cdot {lcm}(k,\frac{h}{m})$; hence we have ${lcm}(k,\frac{h}{m}) = k\cdot \frac{h}{m}$ and $\gcd(k, \frac{h}{m}) = 1$.

$(2)$ As $p = \frac{nh}{mk}$, let $k = l_{1}\cdot \frac{h}{m}+l_{2}$, where $l_{1},l_{2}$ are integers. For $s = 1,\dots,m$, we have

Thus ${\rm{Block}}_{s}(B)$ is a Toeplitz matrix.

For $s = 1,\dots,\frac{h}{m}$, using the technique in the proof of Lemma $3.3(2)$, we obtain the following $\frac{h}{m}$ equations:

Let $i\cdot k = l^{i}_{1}\cdot\frac{h}{m}+l^{i}_{2}$, $i = 1,\dots,\frac{h}{m}$, and $\widetilde{B}_{j}$ be the $j$-th column of $\widetilde{B}$ with

Remark 2. The Lemma $3.3$ gives a necessary condition for matrix-vector equation ($5)$ and we call them compatible conditions for matrix-vector equation ($5$). At this time, matrices $A$ and $B$ are said to be compatible.

Theorem 3.4. The solvability of matrix-vector equation $(7)$ is equivalent to the solvability of the following matrix-vector equations:

Let

If the matrix-vector equations

have solutions $Z_{s} = (z_{s1},\ z_{s1},\ \dots,\ z_{s\frac{n}{k}})^T$, $s = 1,\dots,\frac{h}{m}$, accordingly, then

is the solution of matrix-vector equation $(7)$.

Hence, we obtain a necessary and sufficient condition for the solvability of matrix-vector equation $(7)$.

Theorem 3.5. Matrix-vector equation $(7)$ has solution if and only if $\check{A}_{j}, \check{A}_{\frac{h}{m}+j},\dots , \check{A}_{(\frac{n}{k}-1)\frac{h}{m}+j}$ and $\check{B}_{j}$ are linearly dependent, $j = 1,\dots,\frac{h}{m}$. Moreover, if $\check{A}_{j}, \check{A}_{\frac{h}{m}+j}, \dots , \check{A}_{(\frac{n}{k}-1)\frac{h}{m}+j}$, $j = 1,\dots,\frac{h}{m}$ are linearly independent, then the solution of $AY = B$ is unique.

In conclusion, the solvability of the matrix-vector equation with semi-tensor product $AX^{2} = B$ has been studied in this subsection. And we give an algorithm to solve the matrix-vector equation $AX^{2} = B$ as follow:

● Step 1: Check whether $AX^{2} = B$ satisfies the compatible conditions or not, that is, inspect that if $\frac{nh}{km}$ is a square integer, $m|h,k|n$, $\gcd(k, \frac{h}{m}) = 1$, and if $B$ has the form:

where ${\rm{Block}}_{i}(B)\in {\mathbb C}_{\frac{h}{m}\times k}$ ($i = 1,\dots,a$) are Toeplitz matrices. If the compatible conditions hold, then let's go to the next step; otherwise the equation has no solution.

● Step 2: Let $Y = X^{2}$, and solve the matrix-vector equation $AY = B$ by theorem $3.4$.

● Step 3: Derived from the solution to matrix-vector equation $X^{2} = Y$ by theorem $3.2$, we can get the solution $X$ to the matrix-vector equation $AX^{2} = B$.

3.2.   The case $X\in {\mathbb C}_{a\times b}$ and $Y\in {\mathbb C}_{p\times q}$

We now study the solvability of the matrix equation with semi-tensor product

where $A\in {\mathbb C}_{m\times n}$, $B\in {\mathbb C}_{h\times k}$ and $X\in {\mathbb C}_{a\times b}$ is an unknown matrix.

3.2.1.   The matrix equation $X^{2}=Y$

In this subsection, we discuss the solvability of the matrix equation with semi-tensor product

where $X\in {\mathbb C}_{a\times b}$ and $Y\in {\mathbb C}_{p\times q}$.

Lemma 3.6. $X^{2} = Y$ has solution under the condition that $pq$ is a square integer and $\frac{p}{q}$ is a square rational number. Furthermore,

Proof. The conclusions can be obtained similar to the proof of Lemma $3.3(1)$.

Let $X = (X_{1}\ X_{2}\ \dots \ X_{b}) = \begin{bmatrix} \alpha_{1} \\ \alpha_{2}\\ \vdots \\ \alpha_{a}\\ \end{bmatrix}$, where $X_{i}\in {\mathbb C}_{a\times 1}, \alpha_{j}\in {\mathbb C}_{1\times b}$.

Lemma 3.7. If $X^{2} = Y$ has solution, then

where

is a Toeplitz matrix, $i = 1, \dots, a$, $j = 1, \dots, b$.

Proof. Let $t = {lcm}(a,b)$, $t/a = l_{1}(t/b)+l_{2}$. For $i = 1, 2, \dots, a$, we have

Let

We have

where $H_{ij}, j = 1,2, ,a$, has been defined in the equation above.

Hence, ${\rm{Block}}_{ij}(Y) = x_{1j}H_{i1}+x_{2j}H_{i2}+\dots+x_{aj}H_{ia}$, $i = 1, \dots, a$, $j = 1, \dots, b$, are Toeplitz matrices and

On the other hand, for $t = {lcm}(a,b)$, we have

Denoting $\alpha_{i}\ltimes X_{j} = (\alpha_{i}\otimes I_{t/b})(X_{j}\otimes I_{t/a}) = X^{\ast}_{ij} \in {\mathbb C}_{t/b\times t/a}$, we have $X^{\ast}_{ij} = {\rm{Block}}_{ij}(Y)$, $i = 1,\dots,a$, $j = 1,\dots,b.$ We can see that ${\rm{Block}}_{s}(Y) = ( X^{\ast}_{i1}\ X^{\ast}_{i2} \ \dots X^{\ast}_{ib})$, and $X^{\ast}_{ij}$ are Toeplitz matrices.

Let $t = {lcm} (a,b)$, for $s = 1,\dots,\frac{t}{b}$. Similar to the proof of Lemma $3.3(2)$, we obtain the following $\frac{t}{b}$ equations:

$\dots$

Let $i\cdot k = l^{i}_{1}\cdot\frac{t}{b}+l^{i}_{2}$, $i = 1,\dots,\frac{t}{b}$ and $\widetilde{Y}_{j}$ be the $j$-th column of $\widetilde{Y}$ with

We have the following equations:

$1$)

$2$)

$\frac{t}{b}$)

Let

and label

1)

2)

$\frac{t}{b}$)

Theorem 3.8. The solvability of matrix equation $(9)$ is equivalent to the solvability of the following matrix equations:

Denote the matrixes $W^{(1)}_{1},\ W^{(1)}_{2}, \dots,\ W^{(1)}_{t/b}, \dots, W^{(b)}_{1},\ W^{(b)}_{2}, \dots, \ W^{(b)}_{t/b}$ by

$s = 1, 2, \dots, t/b$, $k = 1, 2, \dots, b$ is a solution of matrix equations $(10)$, then

⋮

⋮

is a solution of matrix equation $(9)$.

3.2.2.   The matrix equation $AY=B$

In this subsection, we discuss the solvability of the matrix equation with semi-tensor product

where $A\in {\mathbb C}_{m\times n}$, $B\in {\mathbb C}_{h\times k}$ and $Y\in {\mathbb C}_{p\times q}$ is an unknown matrix.

Lemma 3.9. $AY = B$ has solution when the following conditions hold:

1. $\frac{h}{m},\frac{n}{k}$ are positive integers.

2. $(\frac{a^2}{b^2} = )\frac{nh}{km}$ is a square rational number and $p = \frac{nh}{vm}( = \frac{at}{b} = \frac{a^2}{\gamma})$, $q = \frac{k}{v}( = \frac{bt}{a} = \frac{b^2}{\gamma})$, where $t = {lcm} (a,b)$, $v$ is a common divisor of $n$ and $k$, and satisfies $\gcd (v,\frac{h}{m}) = 1$.

Proof. Similar to the proof at Lemma $3.3(1)$, we can get the conclusions that $\frac{h}{m},\frac{n}{k}$ are positive integers and $h = \frac{mt'}{n}$, $k = \frac{qt'}{p}$, $t' = {lcm}(n,p)$. Thus $t' = \frac{nh}{m}$, $\frac{t'}{k} = \frac{k}{q}$, let $v = \frac{nh/m}{p}, \frac{t'}{p} = \frac{k}{q}$, then $p = \frac{nh}{vm} = \frac{at}{b}$, $q = \frac{k}{v} = \frac{bt}{a}$, $t = {lcm}(a,b)$, $v$ is a common divisor of $n$ and $k$, and satisfies $\gcd(v,\frac{h}{m}) = 1$. On the other hand $\frac{p}{q} = \frac{nh}{km}$, and as $\frac{p}{q}$ is a square rational number, $\frac{nh}{km}$ is a square rational number automatically.

Remark 3. 1. The condition $m|h,\; k|n$ are necessary conditions for the solvability of matrix equation ($11$) (equation ($8$)).

2. The sizes, which satisfy the condition in Lemma $3.9$, are called admissible sizes. If $gcd(n,k)|\frac{h}{m}$, there is only one admissible size. In this case, $v = 1,\; p = \frac{nh}{m},\; q = k$, and matrix equation ($11$) is reduced to $(A\otimes I_{\frac{h}{m}})Y = B$ with conventional product.

Accordingly, matrix equation ($8$) is reduced to $(A\otimes I_{\frac{h}{m}})X^{2} = B$ with conventional product.

3. Supposing that $p_{1}\times q_{1},\; p_{2}\times q_{2}$ are two admissible sizes and $1<\frac{p_{2}}{p_{1}} = \frac{q_{2}}{q_{1}}\in \mathbb{Z}$, we consider the following two equations:

If $Y$ is a solution of matrix equation ($12$), then $Y\otimes I_{\frac{p_{2}}{p_{1}}}$ is a solution of matrix equation ($13$); reversely, if equation ($13$) has unique solution, the solution of equation ($12$), if exists, would be unique.

Accordingly, consider the following two equations:

As $(X\otimes I_{s})(X\otimes I_{s}) = (X^2)\otimes I_{s}$, if $X$ is a solution of matrix equation ($14$), then $X\otimes I_{\frac{p_{2}}{p_{1}}}$ is a solution of matrix equation ($15$).

4. Denote $\overline{\varepsilon} = \frac{gcd(n,k)}{gcd(n,k,h/m)}, \; \overline{p} = \frac{nh}{m\overline{\varepsilon}}, \; \overline{q} = \frac{k}{\overline{\varepsilon}}$. If matrix equation ($11$) has a solution for the minimum size $\overline{p}\times\overline{q}$, the equation has a solution for every admissible size.

5. Assuming $rank(A) = n$, the solution for every admissible size, if exists, would be unique.

Lemma 3.10. If equation ($11)$ has solution, then

where ${\rm{Block}}_{ij}(B)\in {\mathbb C}_{h/m\times k/q}$ are Toeplitz matrices, $i = 1, \dots, m$, $j = 1, \dots, q$.

Proof. The proof is similar to the proof of Lemma $3.3(2)$.

Remark 4. The Lemma $3.9$ and $3.10$ gives a necessary condition for matrix equation ($11$) and we call them compatible conditions for matrix equation ($11)$. At this time, matrices $A$ and $B$ are said to be compatible.

How to solve the matrix equation ($11$)? Firstly, we should find out all the admissible sizes satisfying the condition by Lemma 3.9. Then, by solving $q$ matrix-vector equations with semi-tensor product, we can get the solutions of matrix equation ($11$) of size $p\times q$. However, the matrix-vector equations with semi-tensor product can be solved in the same way as the last section.

In conclusion, the solvability of the matrix equation ($8$) with semi-tensor product has been studied in this subsection. And we give an algorithm to solve the matrix equation ($8$) as follow:

● Step 1: Check whether $AX^{2} = B$ satisfies the compatible conditions or not, that is, inspect that if $\frac{nh}{km}$ is a square rational number, $m|h,k|n$, and if $B$ has the form:

where ${\rm{Block}}_{ij}(B)\in {\mathbb C}_{h/m\times k/q}$($i = 1, \dots, m$, $j = 1, \dots, q$, $q = \frac{k}{v} = \frac{bt}{a}, t = {lcm} (a,b)$) are Toeplitz matrices. If the compatible conditions hold, then let's go to the next step; otherwise the equation has no solution.

● Step 2: Let $Y = X^{2}$, and solve the matrix equation $AY = B$.

● Step 3: Derived from the solution to matrix equation $X^{2} = Y$, we can get the solution $X$ to the matrix equation $AX^{2} = B$.

4.   Examples

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

Example 1. For matrix-vector equation $AX^{2} = B$, where $X$ is unknown, take $A$ and $B$ as follow:

(1)

Noting that $\frac{3}{2}$ is not a positive integer, so the given matrices are not compatible and the equation has no solution.

(2)

Despite $\frac{4}{2},\frac{6}{3}$ are positive integers and their product is $2^{2}$, a square integer, $B$ cannot be divided into a compatible form. So the equation has no solution.

(3)

Because of the given matrices are compatible, set $Y = X^{2}$. Solving the equation $AY = B$, we have

where $k$ is an arbitrary real number. Then we can just choose $Y = \begin{bmatrix} 4&2&2&1 \end{bmatrix}^T$ to make $Y = X^{2}$ meaningful. Solving

we have

Example 2. For matrix equation $AX^{2} = B$, where $X$ is unknown, take $A$ and $B$ as follow:

(1)

As $\frac{3}{4}$ is not a positive integer, the given matrices are not compatible and the equation has no solution.

(2)

Although $\frac{6}{2}, \frac{4}{2}$ are positive integers, their product is $6$, not a square integer. Thus the equation has no solution.

(3)

By Lemma $3.9$ we have $v = 1$, $p = 12$, $q = 3$, $a = 6$, $b = 3$, ${\rm{Block}}_{i}(B)\in {\mathbb C}_{2\times 1}$, and the given matrices are compatible. We denote $Y = X^{2}$ and solve equation $AY = B$. By selecting the compatible $Y$ as solution, we have

5.   Conclusion

In this paper, the solvability of the matrix equation $AX^{2} = B$ with semi-tensor product is studied. Conditions are given for two kinds: the matrix-vector equation one and the matrix equation one. For the matrix-vector equation case, we derive the compatible conditions first, and then find a necessary and sufficient condition for the solvability. Besides, concrete solving methods have been provided. Based on this, the solvability of the matrix equation $AX^{2} = B$ with semi-tensor product has been discussed in a similar way. The compatible conditions, solvability conditions, and concrete solving methods of the matrix equation have been developed as well. At last, we give several examples to illustrate the efficiency of the results.

Acknowledgments

The authors wish to thank the Editor and anonymous referees for providing very useful suggestions to improve this paper. The corresponding author would also like to thank Professor Tin-Yau Tam, who helped revise the paper during her visit to Auburn University.