Reachability of dimension-bounded linear systems

1.   Introduction

Cross-dimensional systems are also called dimension-varying systems or dimension free systems ^[1]. Some mathematical models with different dimensions can be described as cross-dimensional systems, such as biological systems ^[2], electric power generators ^[3] and vehicle clutch systems ^[4]. Four phenomena appearing in a spacecraft formation ^[5], docking, undocking, departure and participation, are also practical examples of cross-dimensional systems. Take participation as an example. Some new spacecrafts join in the formation, or departed spacecrafts come back. In these cases, their states are treated as new ones and considered in the next mode. Thus, state dimensions increase in the next mode. For simulating the whole flying process of a spacecraft formation, a switched system approach was used to handle dimension-varying systems ^[6]. In the spacecraft formation, it is important to guarantee a smooth transition from one mode to another, which requires that the system is continuous at the mode conversion time. However, the continuity of switched systems at the switching time cannot be determined. Hence, it is necessary to find more ideal models for modeling spacecraft formation.

Hybrid systems, reflecting the interaction of continuous- and discrete-time dynamics ^[7], can also be applied to study dimension-varying systems. From the evolution of hybrid systems, there are at least two subsystems in a hybrid system. When an event occurs, the hybrid system switches from the current discrete mode to a new discrete mode. The switching rule is provided via a given reset map ^[8]. Consider a discrete dynamic model generating a sequence of modes as a switching signal defined in a switched system. Hybrid systems can be viewed as switched systems ^[9]. Thus, the most basic way to deal with dimension-varying systems is to switch. Thus, the continuity at the dimension change time is also not determined via the hybrid system method. To solve this problem, a unified form model should be established for dimension-varying systems. Motivated by this, cross-dimensional linear systems were presented by Cheng ^[10].

The difficulty of giving a unified form model for dimension-varying systems is how to connect spaces with different dimensions together. Thanks to Cheng operations, this difficulty was solved, and cross-dimensional linear systems were established. The Cheng operations include semi-tensor product of matrices, M-addition of matrices, V-addition of vectors and V-product of matrices and vectors ^[11]. Using these operations, cross-dimensional linear systems can go a cross spaces with different dimensions ^[10]. The next problem is how to apply cross-dimension systems to handle the dynamics of the transient process of practical examples, most of which have invariant dimensions except the transient period. In the light of the proposed projection among spaces with different dimensions ^[12], the dynamic of the transient process was modeled, and the control of the transient dynamic of clutch systems was discussed ^[4]. Thus, the problem of how to determine the continuity at the dimension change time is solved preliminarily.

The reachability analysis of a dynamical system refers to computing a reachable set, which contains the entire state trajectories of the system starting from uncertain initial conditions and driven by uncertain inputs. Up to now, there are many references concerning the reachability analysis of dynamical systems, such as linear systems ^[13,14,15], switched systems ^[16,17,18], logical control networks ^[19,20,21] and other systems ^[22,23,24]. An event-triggered impulsive control problem was investigated in ^[25,26]. In ^[27], several reachability analysis techniques, used in the tools SpaceEx ^[28], Flow^{* [29]} and CORA ^[30], were summarized. These reachability analysis techniques relied on ellipsoids ^[31], intervals ^[32], polytopes ^[33], zonotopes ^[14,34,35], support functions ^[36] and so on. Notably, ^[37,38] analyzed the observability and optimal control problems via the reachability approach. In addition, the reachability shows its strong applicability in studying formal and compositional analysis of power systems ^[35], fault diagnosis system verification ^[39] and safety verification ^[40]. Since the reachability of dynamical systems occupies a significant position in both theoretical developments and practical applications, it is meaningful to study the reachability of cross-dimensional linear systems.

Because state dimensions of cross-dimensional linear systems vary with time, the first step of taking the reachability into account is to discuss state dimensions of the system. ^[10] pointed out that cross-dimensional linear systems are classified into two cases: dimension-unbounded linear systems and dimension-bounded linear ones. For the former one, after a certain time, state dimensions not only increase with time but also go to infinity ^[10]. Thus, state dimensions of dimension-unbounded linear systems were studied in ^[41]. For the latter one, state dimensions are invariant after a certain time $t^{\ast}$, which is called the invariant time point. This means that the trajectory of the system enters an invariant space. A recursive formula was proposed to compute the dimension of state at each time ^[10]. However, using this recursive formula, the dimension of a state at time $t$ is obtained when all dimensions of states before time $t$ are calculated. Hence, giving an approach to computing state dimensions directly draws our attention. The expression of state dimension after time $t^{\ast}$ was provided by ^[42]. However, the invariant time point $t^{\ast}$ and state dimensions before time $t^{\ast}$ are not researched. Furthermore, to the best of our knowledge, there is no result on reachable subsets of dimension-bounded linear systems.

Although switched systems and hybrid systems can be used to model some dynamics with different dimensions, the continuity at the dimension change time cannot be determined. Thus, this paper focuses on a unified form model for dimension-varying linear systems. Since the method for analyzing the reachability of dimension-bounded linear systems can be employed to handle dimension-unbounded linear systems, this paper only discusses the reachability of dimension-bounded linear systems. Because state dimensions of dimension-bounded linear systems vary with time before the invariant time point $t^{\ast}$, this paper studies state dimensions first, and then computes the $t$-step reachable subset. The main contributions of this paper are as follows.

● For a given dimension-bounded linear system, the expression of state dimension at each time is provided. Compared with the recursive formula proposed by ^[10], it is easier to determine whether a given integer is a reachable dimension. It also reveals the dimension variation law of dimension-bounded linear systems clearly.

● By proving that the $t$-step reachable subset is a linear space, this paper concludes that the $t$-step reachable subset equals the span of a list of specific vectors. A rank condition is presented to verify the $t$-step reachability of a given state. It is worth noting that these results also hold for dimension-unbounded linear systems.

● To illustrate the relationship between the invariant space and the reachable subset after the invariant time point $t^{\ast}$, annihilator polynomials are discussed. The obtained results show that an $A$-annihilator of vector space $\mathcal{V}_{n}$ is the generalization of a conventional annihilator polynomial, where $A$ is a given matrix.

● An example is studied to explain the inclusion relation between reachable subsets at times $t^{\ast}+i$ and $t^{\ast}+j$. This example makes the discussion of reachable subsets more perfect.

The rest of this paper is organized as follows. Preliminaries and the problem formulation are provided in Sections 2 and 3, respectively. Section 4 gives the main results of this paper, including the discussion of state dimension and the analysis of reachable subsets. Section 5 gives some concluding remarks.

2.   Preliminaries

This section reviews some necessary preliminaries, and it proposes some results about annihilator polynomials.

2.1.   Notations

In this subsection, we provide a list of notations and some results about V-product and V-addition.

● $\mathcal{M}_{m\times n}$ is the set of all $m\times n$ real matrices. Define $\mathcal{M}: = \bigcup\limits_{m = 1}^{\infty}\bigcup\limits_{n = 1}^{\infty}\mathcal{M}_{m\times n}$.

● $\mathcal{V}_{n}$ is the set of all $n$ real column vectors. Define $\mathcal{V}: = \bigcup\limits_{n = 1}^{\infty}\mathcal{V}_{n}$.

● $\mathbb{N}$ is the set of all non-negative integers.

● $\mathbb{R}$ is the set of all real numbers.

● $\mathrm{lcm}(m, n)$ represents the least common multiple of $m$ and $n$.

● $a\mid b$ means that integer $a$ is a divisor of integer $b$.

● ${\bf 0}$ is a null matrix.

● $\delta_{n}^{i}$ is the $i$th column of identity matrix $I_{n}$.

● ${\bf 1}_{m\times n} = [{\bf 1}_{m}\ \cdots\ {\bf 1}_{m}]\in\mathcal{M}_{m\times n}$, where ${\bf 1}_{m}: = \sum\limits_{i = 1}^{m}\delta_{m}^{i}$.

● $\mathrm{span}\{\alpha_{1}, \alpha_{2}, \ldots, \alpha_{s}\} = \{k_{1}\alpha_{1}+k_{2}\alpha_{2}+\cdots+k_{s}\alpha_{s}| \alpha_{i}\in\mathcal{V}_{n},$ $\forall k_{i}\in\mathbb{R}, i = 1, 2, \ldots, s\}.$

● For two given matrices $P\in\mathcal{M}_{m\times n}$ and $Q\in\mathcal{M}_{p\times q}$, the semi-tensor product of $P$ and $Q$ is defined as

where $t = \mathrm{lcm}(n, p)$, $\otimes$ is the Kronecker product.

As main tools for addressing cross-dimensional linear systems, definitions of V-product and V-addition are reviewed.

Definition 2.1. ^[1] (1) Let $A\in\mathcal{M}_{m\times n}, x\in\mathcal{V}_{r}$ and $s = \mathrm{lcm}(n, r)$. The V-product of $A$ and $x$, denoted by $\vec{\ltimes}$, is defined as

(2) Let $x\in\mathcal{V}_{n}, y\in\mathcal{V}_{r}$ and $s = \mathrm{lcm}(n, r)$. The V-addition of $x$ and $y$, denoted by , is defined as

If $n = r$, then $A\vec{\ltimes}x = Ax$, and $x$$y = x+y$. That is, V-addition and V-product are generalizations of conventional vector addition and conventional vector product, respectively. The following lemmas were proven in ^[1].

Lemma 2.2. ^[1] Consider V-product $\vec{\ltimes}:\mathcal{M}\times\mathcal{V}\rightarrow \mathcal{V}$. It is linear with respect to the second variable; precisely,

Lemma 2.3. ^[1] For any two matrices $A, B\in\mathcal{M}$ and any vector $x\in\mathcal{V}$, it holds that

Moreover, we have

The definition of invariant space is given in the following.

Definition 2.4. ^[1] For a given matrix $A\in\mathcal{M}_{m\times n}$, vector space $\mathcal{V}_{r}$ is called an $A$-invariant space if $A\vec{\ltimes}x\in\mathcal{V}_{r}$ for any $x\in\mathcal{V}_{r}.$

2.2.   Annihilator polynomial

For the purpose of investigating the reachability of dimension-bounded linear systems, this subsection discusses annihilator polynomials. To begin with, the definition of annihilator polynomial is provided.

Definition 2.5. ^[1] Given a matrix $A\in\mathcal{M}$, a vector $x\in\mathcal{V}$ and a polynomial

(1) $q(z)$ is called an $A$-annihilator of $x$ if

(2) If $q(z)$ is the $A$-annihilator of $x$ with minimum degree, then $q(z)$ is called the minimum $A$-annihilator of $x$.

Remark 1. Consider polynomial (2.1). The positive integer $n$ is called the degree of polynomial (2.1). For a given matrix $A\in\mathcal{M}$ and a vector $x\in\mathcal{V}$, if $q(z)$ is the $A$-annihilator of $x$ with minimum degree, then $q(z)$ is an $A$-annihilator of $x$, and each polynomial with degree less than $n$ is not an $A$-annihilator of $x$.

For a given matrix $A\in\mathcal{M}_{m\times km}$ and each vector $x\in\mathcal{V}$, Corollary 256 of ^[1] pointed out that there exists at least one $A$-annihilator of $x$. Based on Example 260 of ^[1], we present a constructive proof of this result, which is shown in the following proposition.

Proposition 2.6. Given a matrix $A\in\mathcal{M}_{m\times km}$, for each vector $x\in\mathcal{V}$, there exists an integer $i\in\mathbb{N}$ and a set of coefficients $c_{0}, c_{1}, \ldots, c_{i-1}$ such that polynomial $q(z) = z^{i}+c_{i-1}z^{i-1}+\cdots+c_{1}z+c_{0}$ is the minimal $A$-annihilator of $x$.

Proof. If $x = {\bf 0}$, then the minimal $A$-annihilator of $x$ is $q(z) = 1$. Otherwise, the minimal $A$-annihilator of $x$ is obtained by the following steps.

Let $x_{0} = x\in\mathcal{V}_{r_{0}}$ and $x_{1} = A\vec{\ltimes}x_{0}\in\mathcal{V}_{r_{1}}$. Then, we calculate $y_{0} = x_{0}\otimes{\bf 1}_{t_{1}/r_{0}}$ and $y_{1} = x_{1}\otimes{\bf 1}_{t_{1}/r_{1}}$, where $t_{1} = \mathrm{lcm}(r_{0}, r_{1})$. If there exist $c'_{0}, c'_{1}\in\mathbb{R}$ and $c'_{1}\neq 0$ such that $c'_{1}A\vec{\ltimes}x_{0}$$c'_{0}x_{0} = c'_{1}x_{1}$$c'_{0}x_{0} = c'_{1}y_{1}+c'_{0}y_{0} = {\bf 0}$, then the minimal $A$-annihilator of $x_{0}$ is $q(z) = z+c_{0}$, where $c_{0} = \frac{c'_{0}}{c'_{1}}$. Otherwise, repeat this process until coefficients $c'_{0}, c'_{1}, \ldots, c'_{i}, c'_{i}\neq 0$ satisfying $c'_{i}A^{i}\vec{\ltimes}x_{0}$$c'_{i-1}A^{i-1}\vec{\ltimes}x_{0}$$\cdots$$c'_{1}A\vec{\ltimes}x_{0}$$c'_{0}x_{0} = {\bf 0}$ are derived. Since ^[1] proved that $x_{0}, A\vec{\ltimes}x_{0}, \ldots, A^{i}\vec{\ltimes}x_{0}$ enter an $A$-invariant space at finite steps, $\{c'_{0}, c'_{1}, \ldots, c'_{i}\}$ is a finite set. Therefore, the minimal $A$-annihilator of $x_{0}$ is $q(z) = z^{i}+c_{i-1}z^{i-1}+\cdots+c_{1}z+c_{0}$, where $c_{j} = \frac{c'_{j}}{c'_{i}}, j = 0, 1, \ldots, i-1$.

From the proof of Proposition 2.6, for any $x, y\in\mathcal{V}$ satisfying $x\neq y$, the annihilator polynomials of $x$ and $y$ may be different. Thus, we define the annihilator polynomial of subset $U\subset\mathcal{V}$, which is the generalization of a conventional annihilator polynomial.

Definition 2.7. Given a matrix $A\in\mathcal{M}_{m\times km}$, a subset $U\subset\mathcal{V}$ and a polynomial

(1) $q(z)$ is called an $A$-annihilator of $U$, if $q(z)$ is an $A$-annihilator of each vector $x\in U$.

(2) If $q(z)$ is the $A$-annihilator of $U$ with minimum degree, then $q(z)$ is called the minimum $A$-annihilator of $U$.

Given a matrix $A\in\mathcal{M}_{n\times n}$, if $q(z)$ is an $A$-annihilator of $\mathcal{V}_{n}$, then $q(z)$ is an $A$-annihilator of $\delta_{n}^{i}, \ i = 1, 2, \ldots, n$, i.e., $q(A)\delta_{n}^{i} = {\bf 0}, \ i = 1, 2, \ldots, n$. $q(z)$ is a conventional annihilator polynomial because ${\bf 0} = [q(A)\delta_{n}^{1}\ q(A)\delta_{n}^{2}\ \cdots\ q(A)\delta_{n}^{n}]$ $= q(A)I_{n} = q(A).$ This implies that an $A$-annihilator of $\mathcal{V}_{n}$ is the generalization of a conventional annihilator polynomial. The following proposition proposes an approach to computing the minimal annihilator polynomial of $\mathcal{V}_{n}$.

Proposition 2.8. Given a matrix $A\in\mathcal{M}_{m\times km}$, if $q_{i}(z)$ is the minimum $A$-annihilator of $\delta_{n}^{i}, \ i = 1, 2, \ldots, n$, then $q(z) = \mathrm{lcm}(q_{1}(z), q_{2}(z), \ldots, q_{n}(z))$ is the minimum $A$-annihilator of $\mathcal{V}_{n}$.

Proof. Obviously, $q(z)$ is an $A$-annihilator of $\delta_{n}^{i}, i = 1, 2, \ldots,$ $n$. For each $x\in\mathcal{V}_{n}$, define $x = k_{1}\delta_{n}^{1}+k_{2}\delta_{n}^{2}+\cdots+k_{n}\delta_{n}^{n}$. Then, $q(A)\vec{\ltimes}x = q(A)\vec{\ltimes}(k_{1}\delta_{n}^{1}+k_{2}\delta_{n}^{2}+\cdots+k_{n}\delta_{n}^{n}) = k_{1}q(A)\vec{\ltimes}\delta_{n}^{1}+k_{2}q(A)\vec{\ltimes}\delta_{n}^{2}+\cdots+k_{n}q(A)\vec{\ltimes}\delta_{n}^{n} = {\bf 0}.$ Hence, $q(z)$ is an $A$-annihilator of $x$. Due to the arbitrariness of $x$, $q(z)$ is an $A$-annihilator of $\mathcal{V}_{n}$.

Assume $f(z)$ is the minimum $A$-annihilator of $\mathcal{V}_{n}$. It is obvious that $f(z)\mid q(z)$. Since $q_{i}(z)$ is the minimum $A$-annihilator of $\delta_{n}^{i}, \ i = 1, 2, \ldots, n$, one sees $q_{i}(z)\mid f(z), \ i = 1, 2, \ldots, n$. That is, $f(z)$ is a common multiple of $q_{i}(z), \ i = 1, 2, \ldots, n$. Thus, we have $q(z)\mid f(z)$, which means $f(z) = aq(z), a\in\mathbb{R}, a\neq 0$. From the proof above, we find that $q(z)$ is the minimum $A$-annihilator of $\mathcal{V}_{n}$.

Remark 2. For linear space $U = \mathrm{span}\{x_{1}, x_{2}, \ldots, x_{n}\}$, if $q_{i}(z)$ is the minimal $A$-annihilator of $x_{i}, i = 1, 2, \ldots, n$, then $q(z) = \mathrm{lcm}(q_{1}(z), \ldots, q_{n}(z))$ is the minimal $A$-annihilator of $U$.

3.   Problem formulation

Consider a cross-dimensional linear system

where $A\in\mathcal{M}_{m\times n}$. According to Definition 2.1, system (3.1) can be rewritten as

where $r(t)$ is the dimension of state $x(t)$, $s(t) = \mathrm{lcm}(n, r(t))$. It is a linear difference equation. If $m = n = r(0)$, then system (3.1) is a conventional linear system. It is seen that $r(t)$ varies with time. If there exists a time $t^{\ast}$ and a dimension $r^{\ast}$ such that $r(t) = r^{\ast}$ holds for $t\geq t^{\ast}$, then system (3.1) becomes a dimension-bounded linear system, which is defined as follows.

Definition 3.1. ^[10] Consider system (3.1). $A$ is called a dimension-bounded operator, if for any $x(0) = x_{0}\in\mathcal{V}_{p}$, there exists a $t^{\ast} > 0$ and an $r^{\ast}$ such that $x(t)\in\mathcal{V}_{r^{\ast}}$ holds for any $t\geq t^{\ast}$, where $\mathcal{V}_{r^{\ast}}$ is called the invariant space of system (3.1). Additionally, system (3.1) is called a dimension-bounded linear system.

In this paper, system (3.1) is a dimension-bounded linear system unless otherwise specified. According to Lemma 3.2, it is reasonable to assume $A\in\mathcal{M}_{m\times km}$.

Lemma 3.2. ^[1] $A\in\mathcal{M}_{m\times n}$ is dimension-bounded if and only if $m\mid n$.

To analyze the reachability of dimension-bounded linear systems, the following definition is introduced.

Definition 3.3. Consider dimension-bounded linear system (3.1) with initial space $\mathcal{V}_{p}$.

(1) A state $x$ is said to be $t$-step reachable, if there exists an initial value $x(0)\in\mathcal{V}_{p}$ such that the trajectory of the system reaches $x$ from $x(0)$ at time $t$.

(2) $x$ is said to be reachable, if there exists an integer $t$ such that $x$ is $t$-step reachable.

(3) $R\subset\mathcal{V}$ is called a reachable subset, if each state $x\in R$ is reachable.

(4) $r$ is called a reachable dimension of system (3.1), if there exists a state $x\in\mathcal{V}_{r}$ such that it is reachable.

Obviously, there is a difference in the definition of reachability between dimension-bounded linear systems and conventional linear systems. That is, the reachable dimension is defined for dimension-bounded linear systems, but needs not to be considered in conventional linear systems. It is necessary to compute the reachable dimension when studying the reachability of dimension-bounded linear systems. For example, consider dimension-bounded linear system (3.1) with initial space $\mathcal{V}_{8}$, where

1) How to determine the reachability of a given state $x = [2\ 3\ 1\ 2\ 1]^{T}$?

By computing directly, one sees

Thus, $x$ is not a reachable state. This means that discussing the reachable dimension is helpful in excluding some unreachable states. Although the reachable dimension can be obtained via the recursive approach ^[10], the difficulty is providing formulas for computing the reachable dimension directly.

2) How to determine the reachability of a given state $x = [6\ 4]^{T}$?

It is obvious that the dimension of $x$ is reachable. Taking $x(0) = [1\ 0\ 0\ 0\ 0\ 0\ 0\ 1]^{T}$ and calculating step by step, one concludes that $x$ is $3$-step reachable. However, there is a difficulty, i.e., how to determine the corresponding initial state $x(0)$. In fact, it is not necessary to find the corresponding initial state $x(0)$. The purpose for determining the reachability of a given state can be achieved if the reachable set of dimension-bounded linear systems is obtained. Thus, this paper focuses on the computation of the reachable set. Delicate differences between the V-product and the conventional matrix product increase the difficulty in determining the reachable set.

Based on the analysis above, this paper investigates the reachability of dimension-bounded linear systems via the following two steps. The first one is to compute all possible reachable dimensions. The second one is to determine the reachable set.

4.   Reachability analysis

This section studies the reachability of dimension-bounded linear systems from four aspects: state dimension at each time, the $t$-step reachable subset, the relationship between the invariant space and the reachable subset after the invariant time point $t^{\ast}$ and the inclusion relation between reachable subsets at times $t^{\ast}+i$ and $t^{\ast}+j$.

4.1.   The discussion of state dimension

This subsection proposes a method for determining whether a given integer is a reachable dimension. To this end, an example is provided to show the relationship between reachable dimensions and dimensions of system matrix $A$ and initial space $\mathcal{V}_{p}$.

Example 4.1. Consider a dimension-bounded linear system $x(t+1) = A\vec{\ltimes}x(t)$ with $A\in\mathcal{M}_{m\times km}$ and initial value $x(0)\in\mathcal{V}_{p}$. Denote the dimension of state $x(t)$ by $r(t)$. According to Definition 2.1, $r(t+1) = \frac{s(t)}{k}$ can be obtained via $x(t+1) = (A\otimes I_{s(t)/km})(x(t)\otimes{\bf 1}_{s(t)/r(t)})\in\mathcal{V}_{s(t)/k}$, where $s(t) = \mathrm{lcm}(km, r(t))$. Taking three different values of $k, m, p$, the change of $r(t)$ is shown in Table 1.

From Table 1, the following conclusions are derived.

(1) State dimensions before the invariant time point $t^{\ast}$ decrease with time.

(2) One obtains $m\mid r(t)$.

(3) There may be a factor $m_{1}$ of $m$ such that $mm_{1} \mid r(t)$ holds.

(4) Comparing $r(t)$ with $r(t-1), t\leq t^{\ast}$, it is easy to see that $r(t-1) = k_{1}lr(t)$, where $k_{1}\mid k, l\in\mathbb{N}, l\neq 0$.

(5) If $k^{a}k_{1}\mid r(t)$, where $k_{1}\mid k, k_{1}\nmid m, a\in\mathbb{N}$, then $k^{a-1}k_{1}\mid r(t+1), \ldots, k_{1}\mid r(t+a), k\nmid r(t+a), k_{1}\nmid r(t+a+1)$.

Example 4.1 shows the necessity of factorizing dimensions of system matrix $A$ and initial space $\mathcal{V}_{p}$ before computing state dimensions of system (3.1). Assume $k = k_{1}^{\mu_{1}}k_{2}^{\mu_{2}}\cdots k_{\varpi}^{\mu_{\varpi}}, m = m_{1}^{\nu_{1}}m_{2}^{\nu_{2}}\cdots m_{\omega}^{\nu_{\omega}}$, where $k_{i}, m_{j}, i = 1, 2, \ldots, \varpi, j = 1, 2, \ldots, \omega$ are prime numbers. $p$ is factorized according to the following steps.

(1) Write $p$ in the form of $p = k^{\alpha}p'$, where $k\nmid p'$.

(2) Write $p'$ in the form of $p' = k_{1}^{\beta_{1}}k_{2}^{\beta_{2}}\cdots k_{\varpi}^{\beta_{\varpi}}p''$, where $k_{i}\nmid p'', i = 1, \ldots, \varpi$. Due to $k\nmid p'$, there is at least one positive integer $l$ such that $\beta_{l} < \mu_{l}$ holds.

(3) Write $p''$ in the form of $p'' = m_{1}^{\theta_{1}}m_{2}^{\theta_{2}}\cdots m_{\omega}^{\theta_{\omega}}p_{1}$, where $m_{i}\nmid p_{1}, i = 1, \ldots, \omega$. If $k_{i} = m_{j}$, then $\theta_{j} = 0$, i.e., $m_{j}^{\theta_{j}} = 1$. Hence, we assume $(m_{i}, k) = 1, i = 1, \ldots, \omega$.

To give the expression of state dimension $r(t)$ better, some assumptions are presented.

Assumption 1. Assume $k = k_{1}^{\mu_{1}}k_{2}^{\mu_{2}}\cdots k_{\varpi}^{\mu_{\varpi}}$, $m = m_{1}^{\nu_{1}}m_{2}^{\nu_{2}}\cdots$ $m_{\omega}^{\nu_{\omega}}$, where $k_{i}, m_{j},$ $i = 1, 2, \ldots, \varpi, j = 1, 2, \ldots, \omega$ are prime numbers. Write $p$ in form of $p = k^{\alpha}k_{1}^{\beta_{1}}k_{2}^{\beta_{2}}\cdots k_{\varpi}^{\beta_{\varpi}}m_{1}^{\theta_{1}}m_{2}^{\theta_{2}}\cdots m_{\omega}^{\theta_{\omega}}p_{1},$ where

Theorem 4.2. Consider dimension-bounded linear system (3.1) with initial space $\mathcal{V}_{p}$. Under Assumption 1, state dimension $r(t)$ can be computed directly.

(1) If $t\leq\alpha$, then state dimension $r(t)$ is

(2) Let $\tau_{d} = 0$. If $\alpha+\tau_{k} < t\leq\alpha+\tau_{k+1}, k = d, d+1, \ldots, \varpi-1$, then state dimension $r(t)$ is

(3) If $t\geq\alpha+\tau_{\varpi}+1$, then state dimension $r(t)$ is

Proof. According to Definition 2.1, $r(t+1) = \frac{s(t)}{k}$ can be obtained via $x(t+1) =$ $(A\otimes I_{s(t)/km})(x(t)\otimes{\bf 1}_{s(t)/r(t)})\in\mathcal{V}_{s(t)/k}$, where $s(t) = \mathrm{lcm}(km, r(t))$. Due to $r(0) = p = k^{\alpha}\prod\limits_{i = 1}^{\varpi}k_{i}^{\beta_{i}}\prod\limits_{j = l}^{\omega}m_{j}^{\theta_{j}}p_{1}$, one sees $s(0) = mk^{\alpha}\prod\limits_{i = 1}^{\varpi}k_{i}^{\beta_{i}}\prod\limits_{j = l}^{\omega}m_{j}^{\theta_{j}-\nu_{j}}p_{1}$. Thus, $r(1) = mk^{\alpha-1}\prod\limits_{i = 1}^{\varpi}k_{i}^{\beta_{i}}\prod\limits_{j = l}^{\omega}m_{j}^{\theta_{j}-\nu_{j}}p_{1}$. It is easy to see that $s(t) = mk^{\alpha-t}\prod\limits_{i = 1}^{\varpi}k_{i}^{\beta_{i}}\prod\limits_{j = l}^{\omega}m_{j}^{\theta_{j}-\nu_{j}}p_{1}$ holds for $t\leq\alpha-1$, which means $r(t+1) = mk^{\alpha-t-1}\prod\limits_{i = 1}^{\varpi}k_{i}^{\beta_{i}}\prod\limits_{j = l}^{\omega}m_{j}^{\theta_{j}-\nu_{j}}p_{1}$. Similarly, we have $s(t) = km\prod\limits_{i = k+1}^{\varpi}k_{i}^{(\tau_{i}+\alpha-t)\mu_{i}+\eta_{i}}\prod\limits_{j = l}^{\omega}m_{j}^{\theta_{j}-\nu_{j}}p_{1}$ for $\alpha+\tau_{k} < t\leq\alpha+\tau_{k+1}, k = d, d+1,$ $\ldots, \varpi-1$. Hence, $r(t+1) = m\prod\limits_{i = k+1}^{\varpi}k_{i}^{(\tau_{i}+\alpha-t-1)\mu_{i}+\eta_{i}}\prod\limits_{j = l}^{\omega}m_{j}^{\theta_{j}-\nu_{j}}p_{1}$ holds. When $t\geq\alpha+\tau_{\omega}$, it is seen that $s(t) = km\prod\limits_{j = l}^{\omega}m_{j}^{\theta_{j}-\nu_{j}}p_{1}$ and $r(t+1) = m\prod\limits_{j = l}^{\omega}m_{j}^{\theta_{j}-\nu_{j}}p_{1}$.

Remark 3. It is worth noting that the number of multiplication operations of state dimension $r(t)$ is not more than $\alpha+\varpi\beta+\omega\gamma+3$, where $\beta = \max\{\beta_{1}, \ldots,$ $\beta_{\varpi}\}$ and $\gamma = \max\{\theta_{1}-\nu_{1}, \ldots, \theta_{\omega}-\nu_{\omega}\}$.

Consider system (3.1) with $A\in\mathcal{M}_{2\times 6}$. when $x(0)\in\mathcal{V}_{5}$, the invariant time point of system (3.1) is $t^{\ast} = 1$. The invariant time point of system (3.1) is $t^{\ast} = 2$ if $x(0)\in\mathcal{V}_{18}$. This shows that the invariant time point $t^{\ast}$ of system (3.1) depends on the dimension of the initial value. Hence, we denote the invariant time point $t^{\ast}$ as $t^{\ast}(p)$ with $p$ being the dimension of the initial value.

Remark 4. From Theorem 4.2, the invariant time point $t^{\ast}$ of system (3.1) can be calculated via the formula $t^{\ast}(p) = \alpha+\tau_{\varpi}+1$.

Based on Theorem 4.2, a method is given to determine whether $r$ is a reachable dimension of system (3.1).

Corollary 4.3. Consider dimension-bounded linear system (3.1) with initial space $\mathcal{V}_{p}$. For a given vector space $\mathcal{V}_{r}$, $r$ is a reachable dimension of system (3.1), if one of the following conditions holds.

(1) $r = r^{\ast} = m\prod\limits_{j = l}^{\omega}m_{j}^{\theta_{j}-\nu_{j}}p_{1}$.

(2) $\frac{r}{r^{\ast}} = k^{\alpha-t}\prod\limits_{i = 1}^{\varpi}k_{i}^{\beta_{i}}, t\leq\alpha$.

(3) $\frac{r}{r^{\ast}} = \prod\limits_{i = k+1}^{\varpi}k_{i}^{(\tau_{i}+\alpha-t)\mu_{i}+\eta_{i}}, \alpha+\tau_{k} < t\leq\alpha+\tau_{k+1}, k = d, d+1, \ldots, \varpi-1$.

4.2.   Reachable subsets

Reachable subsets are computed in this subsection. Since V-product is linear with respect to the second variable, it is easy to prove that the $t$-step reachable subset is a linear space.

Theorem 4.4. Consider dimension-bounded linear system (3.1) with initial space $\mathcal{V}_{p}$. The $t$-step reachable subset of the system is a linear space. Moreover, the $t$-step reachable subset is called the $t$-step reachable subspace and calculated via

Remark 5. For a given time $t$, to derive the $t$-step reachable subspace of dimension-bounded linear systems, up to $pt$ matrix multiplications are required according to Theorem 4.4. For each matrix multiplication, the number of multiplication operations is not more than $\max\{2m^{3}k^{2t-1}, \frac{3a^{2}}{k^{t}}\}$, where $a = \mathrm{lcm}(k^{t}m, p)$. Thus, the computational complexity of obtaining the $t$-step reachable subspace is $O(p^{2}tm^{3}k^{2t})$.

On the basis of Theorem 4.4, a necessary and sufficient condition about $x\in R_{t}$ is provided.

Theorem 4.5. Consider dimension-bounded linear system (3.1) with initial space $\mathcal{V}_{p}$. A state $x$ is $t$-step reachable if and only if

where $\dim R_{t}$ is the dimension of the $t$-step reachable subspace.

Remark 6. For a dimension-unbounded linear system, results about the $t$-step reachable subspace also hold.

Suppose system (3.1) reaches the invariant space $\mathcal{V}_{r^{\ast}}$ at the invariant time point $t^{\ast}$. Then, $\bigcup_{t\geq t^{\ast}}R_{t}\subset\mathcal{V}_{r^{\ast}}$ is the reachable subset of system (3.1) after time $t^{\ast}$. Our concern is whether $\bigcup_{t\geq t^{\ast}}R_{t}$ equals $\mathcal{V}_{r^{\ast}}$. Annihilator polynomials are used to answer this question. To this end, an approach to obtaining the minimum $A$-annihilator of $\bigcup_{t\geq t^{\ast}}R_{t}$ is given.

Theorem 4.6. Consider dimension-bounded linear system (3.1) with initial space $\mathcal{V}_{p}$. If $q_{i}(z)$ is the minimum $A$-annihilator of $A^{t^{\ast}}\vec{\ltimes}\delta_{p}^{i}, \ i = 1, 2, \ldots, p$, then $q(z) = \mathrm{lcm}(q_{1}(z), q_{2}(z), \ldots, q_{p}(z))$ is the minimum $A$-annihilator of $\bigcup_{t\geq t^{\ast}}R_{t}$.

Proof. The proof is obvious according to Proposition 2.8.

Remark 7. $q_{i}(z)$ in Proposition 2.8 stands for the minimum annihilator of $\delta_{n}^{i}$, while $q_{i}(z)$ in Theorem 4.6 represents the minimum annihilator of $A^{t^{\ast}}\vec{\ltimes}\delta_{p}^{i}$. It is easy to see $\mathcal{V}_{n} = \mathrm{span}\{\delta_{n}^{1}, \ldots, \delta_{n}^{n}\}$. However, $\bigcup_{t\geq t^{\ast}}R_{t} = \mathrm{span}\{A^{t^{\ast}}\vec{\ltimes}\delta_{p}^{1}, \ldots, A^{t^{\ast}}\vec{\ltimes}\delta_{p}^{p}\}$ does not hold. Assume $q_{i}(z)$ is the minimum $A$-annihilator of $A^{t^{\ast}}\vec{\ltimes}\delta_{p}^{i}, \ i = 1, 2, \ldots, p$. Using Proposition 2.8, one sees that $q(z) = \mathrm{lcm}(q_{1}(z), \ldots, q_{p}(z))$ is the minimum $A$-annihilator of $R^{t^{\ast}}$. However, the conclusion that $q(z) = \mathrm{lcm}(q_{1}(z), \ldots, q_{p}(z))$ is the minimum $A$-annihilator of $\bigcup_{t\geq t^{\ast}}R^{t}$ cannot be obtained according to Proposition 2.8. Thus, Theorem 4.6 is presented to show that $q(z) = \mathrm{lcm}(q_{1}, \ldots, q_{p}(z))$ is the minimum $A$-annihilator of $\bigcup_{t\geq t^{\ast}}R^{t}$. Since the proof of Theorem 4.6 is similar to Proposition 2.8, it is omitted.

According to the definition of annihilator polynomial of a given subset, a sufficient condition of $\bigcup_{t\geq t^{\ast}}R_{t}\neq\mathcal{V}_{r^{\ast}}$ is proposed.

Theorem 4.7. Consider dimension-bounded linear system (3.1). Suppose $q(z)$ is the minimum $A$-annihilator of $\bigcup_{t\geq t^{\ast}}R_{t}$. If $q(z)$ is not the minimum $A$-annihilator of $\mathcal{V}_{r^{\ast}}$, then $\bigcup_{t\geq t^{\ast}}R_{t}\neq\mathcal{V}_{r^{\ast}}$.

Proof. Since $q(z)$ is not the minimum $A$-annihilator of $\mathcal{V}_{r^{\ast}}$, there exists an $x\in\mathcal{V}_{r^{\ast}}$ such that $q(z)$ is not an $A$-annihilator of $x$. Thus, $x\not\in\bigcup_{t\geq t^{\ast}}R_{t}$ because $q(z)$ is the minimum $A$-annihilator of $\bigcup_{t\geq t^{\ast}}R_{t}$. Therefore, we conclude $\bigcup_{t\geq t^{\ast}}R_{t}\neq\mathcal{V}_{r^{\ast}}$.

From Theorem 4.7, a necessary condition of $x\in\bigcup_{t\geq t^{\ast}}R_{t}$ is presented.

Corollary 4.8. Consider dimension-bounded linear system (3.1). Suppose $q(z)$ is the minimum $A$-annihilator of $\bigcup_{t\geq t^{\ast}}R_{t}$. If state $x$ is reachable after time $t^{\ast}$, then $q(z)$ is the minimum $A$-annihilator of $x$.

Remark 8. Based on the obtained results, a procedure is given to compute the reachable set of dimension-bounded linear system (3.1) and determine whether a given state is reachable. Consider dimension-bounded linear system (3.1) with initial space $\mathcal{V}_{p}$.

1) Compute all possible reachable dimensions according to Theorem 4.2. Denote these reachable dimensions by $\Theta = \{r_{1}, \ldots, r_{t^{\ast}}\}$, where $t^{\ast}$ is the invariant time point.

2) Compute the $t$-step reachable subspace via $R_{t} = \mathrm{span}\{A^{t}\vec{\ltimes}\delta_{p}^{1}, A^{t}\vec{\ltimes}\delta_{p}^{2}, \ldots, A^{t}\vec{\ltimes}\delta_{p}^{p}\}$. Then, the reachable set is $\bigcup\limits_{t = 0}^{\infty}R_{t}$.

3) Compute the minimum $A$-annihilator of $\bigcup_{t\geq t^{\ast}}R_{t}$ according to Theorem 4.6, denoted by $q(z)$.

4) For a given state $x\in\mathcal{V}_{r}$, if $r\not\in\Theta$, then $r$ is not a reachable dimension. Thus, $x$ is not a reachable state of system (3.1). Otherwise, go to the next step.

5) If $r = r_{t}, t < t^{\ast}$, then compute $\mathrm{rank}(x, A^{t}\vec{\ltimes}\delta_{p}^{1}, A^{t}\vec{\ltimes}\delta_{p}^{2}, \ldots, A^{t}\vec{\ltimes}\delta_{p}^{p})$. If $\mathrm{rank}(x, A^{t}\vec{\ltimes}\delta_{p}^{1}, A^{t}\vec{\ltimes}\delta_{p}^{2}, \ldots,$ $A^{t}\vec{\ltimes}\delta_{p}^{p}) = \dim R_{t}$, then $x$ is a $t$-step reachable state. Otherwise, $x$ is not a $t$-step reachable state.

6) If $r = r_{t^{\ast}}$, then compute the minimum $A$-annihilator of $x$, denoted by $q_{x}(z)$. If $q_{x}(z)\neq q(z)$, then $x$ is not a reachable state. Otherwise, go to the next step.

7) For $t\geq t^{\ast}$, compute $\mathrm{rank}(x, A^{t}\vec{\ltimes}\delta_{p}^{1}, A^{t}\vec{\ltimes}\delta_{p}^{2}, \ldots, A^{t}\vec{\ltimes}\delta_{p}^{p})$. If a time $t$ satisfying $\mathrm{rank}(x, A^{t}\vec{\ltimes}\delta_{p}^{1}, A^{t}\vec{\ltimes}\delta_{p}^{2},$ $\ldots, A^{t}\vec{\ltimes}\delta_{p}^{p}) = \dim R_{t}$ can be found, then $x$ is a reachable state. Otherwise, $x$ is not a reachable state.

Before ending this subsection, an example is employed to show how to use the minimum annihilator polynomial to discuss reachability of dimension-bounded linear systems. In addition, this example also illustrates that there is not an inclusion relation between reachable subspaces at times $t^{\ast}+i$ and $t^{\ast}+j, \ i\neq j$. Furthermore, the intersection of $R_{t^{\ast}+i}$ and $R_{t^{\ast}+j}$ may not be an empty set.

Example 4.9. Consider dimension-bounded linear system (3.1) with initial space $\mathcal{V}_{3}$, where

From subsection 4.1, one sees that the system reaches the invariant space $\mathcal{V}_{6}$ after the invariant time point $t^{\ast} = 1$.

(1) We calculate the minimum $A$-annihilator of $\bigcup_{t\geq 1}R_{t}$. To begin with, $A^{j}\vec{\ltimes}\delta_{3}^{i}, i = 1, 2, 3,$ $j = 1, 2, 3, 4, 5$, can be computed. Because $\mathrm{rank}(A\vec{\ltimes}\delta_{3}^{2}, A^{2}\vec{\ltimes}\delta_{3}^{2},$ $A^{3}\vec{\ltimes}\delta_{3}^{2}) = 3$, and $\mathrm{rank}(A\vec{\ltimes}\delta_{3}^{i}, A^{2}\vec{\ltimes}\delta_{3}^{i},$ $A^{3}\vec{\ltimes}\delta_{3}^{i}, A^{4}\vec{\ltimes}\delta_{3}^{i}) = 4, \ i = 1, 3$, one obtains

Denote the minimum $A$-annihilator of $A\vec{\ltimes}\delta_{3}^{i}$ by $q_{i}(z), \ i = 1, 2, 3$. It is easy to see that

According to Theorem 4.6, the minimum $A$-annihilator of $\bigcup_{t\geq 1}R_{t}$ is

(2) From Proposition 2.8, we derive that the minimum $A$-annihilator of $\mathcal{V}_{6}$ is $f(z) = z^{6}-2z^{5}-2z^{4}+2z^{3}+z^{2}$. Because $f(z) = z^{2}q(z)$, we have $\bigcup_{t\geq 1}R_{t}\neq\mathcal{V}_{6}$.

(3) Take a subset $U = \mathrm{span}\{A\vec{\ltimes}\delta_{3}^{1}, A\vec{\ltimes}\delta_{3}^{2}\}$. The minimum $A$-annihilator of $U$ is $q(z)$. In addition, $q(z)$ is also the minimum $A$-annihilator of $A\vec{\ltimes}\delta_{3}^{3}$. Since $\mathrm{rank}(A\vec{\ltimes}\delta_{3}^{1}, A\vec{\ltimes}\delta_{3}^{2}, A\vec{\ltimes}\delta_{3}^{3}) = 3 > \dim U,$ one knows $A\vec{\ltimes}\delta_{3}^{3}\not\in U$, which implies that the condition that $q(z)$ is the minimum $A$-annihilator of $A\vec{\ltimes}\delta_{3}^{3}$ is not a sufficient condition of $A\vec{\ltimes}\delta_{3}^{3}\in U$. Furthermore, for any $x\in\mathcal{V}_{6}$, the condition that $q(z)$ is the minimum $A$-annihilator of $x$ is a necessary but not sufficient condition of $x\in\bigcup_{t\geq 1}R_{t}$.

(4) Take $y_{1} = [2\ 2\ 3\ 2\ 1\ 1]^{T}$. $y_{1} = A^{2}\vec{\ltimes}\delta_{3}^{2}$ implies $y_{1}\in R_{2}$. In addition, one has $y_{1} = A\vec{\ltimes}\delta_{3}^{1}+A\vec{\ltimes}\delta_{3}^{3}$, which means $y_{1}\in R_{1}$. Thus, we conclude $R_{1}\cap R_{2}\neq\emptyset$. Take $y_{2} = [3\ 3\ 3\ 2\ 3\ 3]^{T}$ and $y_{3} = [0\ 0\ 1\ 1\ -1\ -1]^{T}$. Because $y_{2} = A^{2}\vec{\ltimes}\delta_{3}^{3}$ and $y_{3} = A\vec{\ltimes}\delta_{3}^{1}-A\vec{\ltimes}\delta_{3}^{2}$, one sees $y_{2}\in R_{2}$ and $y_{3}\in R_{1}$. In addition, $y_{2}\not\in R_{1}$ and $y_{3}\not\in R_{2}$ hold because $\mathrm{rank}(y_{2}, A\vec{\ltimes}\delta_{3}^{1}, A\vec{\ltimes}\delta_{3}^{2}, A\vec{\ltimes}\delta_{3}^{3}) = 4$ and $\mathrm{rank}(y_{3}, A^{2}\vec{\ltimes}\delta_{3}^{1}, A^{2}\vec{\ltimes}\delta_{3}^{2}, A^{2}\vec{\ltimes}\delta_{3}^{3}) = 4$. Based on the analysis above, we conclude $R_{1}\not\subset R_{2}$ and $R_{2}\not\subset R_{1}$.

5.   Conclusions

The reachability of dimension-bounded linear systems has been studied in this paper. Based on the expression of state dimension at each time, a method for judging the reachability of a given vector space $\mathcal{V}_{r}$ has been proposed. Since the $t$-step reachable subset is a linear space, the $t$-step reachable subset has been calculated via the span of vectors $A^{t}\vec{\ltimes}\delta_{p}^{1}, \ldots, A^{t}\vec{\ltimes}\delta_{p}^{p}$, where $A$ is a system matrix. A rank condition has been given to verify the $t$-step reachability of a given state. To illustrate the relationship between the invariant space and the reachable subset after the invariant time point $t^{\ast}$, annihilator polynomials have been discussed. The obtained results have shown that $A$-annihilator of vector space $\mathcal{V}_{n}$ is the generalization of conventional annihilator polynomial, where $A$ is a given matrix. This paper has provided an example to explain the inclusion relation between reachable subsets at times $t^{\ast}+i$ and $t^{\ast}+j$.

There is no evidence to prove that the existing reachability analysis techniques are not suitable for dimension-bounded linear systems. It is worth noting that dimension-bounded linear systems are modelled via one of the Cheng operations, i.e., $V$-product, while the existing techniques are based on the conventional matrix product. Thus, the effectiveness of the existing reachability analysis techniques in studying dimension-bounded linear systems should be studied further. This is one of our future works. In addition, reachability and controllability of dimension-varying control systems will be focused on. A dimension-varying control system is described as

where $A\in\mathcal{M}_{m\times n}$ and $B\in\mathcal{M}_{p\times q}$. Due to the influence of control input, it is not clear that the results about the reachability of system (5.1) are the same as dimension-bounded linear systems. Thus, the reachability of a dimension-varying control system needs to be investigated. Based on the existing results, the reachability of dimension-varying control systems is summarized into two problems. For a given vector space $\mathcal{V}_{r}$, are there a time $t$ and control inputs such that state dimension $r(t)$ of system (5.1) is $r$? For a given state $x\in\mathcal{V}_{r}$, are there a time $t$ and control inputs such that the trajectory of system (5.1) can reach $x(t) = {\bf 0}$ from $x(0) = x$?

Acknowledgments

This work was supported by the National Natural Science Foundation of China (61877036, 62273201, 11871259).

Conflict of interest

The authors declare that there is no conflict of interest.