{'fraction_non_alphanumeric': 0.06170461298850339, 'fraction_numerical': 0.01664036723569072, 'mean_word_length': 3.278649715037264, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 57, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Structural Controllability on Graphs for Drifted Bilinear Systems over Lie Groups

In this paper, we study graphical conditions for structural controllability and accessibility of drifted bilinear systems over Lie groups. We consider a bilinear control system with drift and controlled terms that evolves over the special orthogonal group, the general linear group, and the special unitary group. Zero patterns are prescribed for the drift and controlled dynamics with respect to a set of base elements in the corresponding Lie algebra. The drift dynamics must respect a rigid zero-pattern in the sense that the drift takes values as a linear combination of base elements with strictly non-zero coefficients; the controlled dynamics are allowed to follow a free zero pattern with potentially zero coefficients in the configuration of the controlled term by linear combination of the controlled base elements. First of all, for such bilinear systems over the special orthogonal group or the special unitary group, the zero patterns are shown to be associated with two undirected or directed graphs whose connectivity and connected components ensure structural controllability/accessibility. Next, for bilinear systems over the special unitary group, we introduce two edge-colored graphs associated with the drift and controlled zero patterns, and prove structural controllability conditions related to connectivity and the number of edges of a particular color.

problem. Indeed classical control theories have established celebrated results on conditions for controllability of general dynamical systems. In the networked system era, graphical conditions that link notions of connectivity for the network topology to the controllability of the system are desired. Sparked by such a vision, a series of important understandings on graph-theoretic controllability were established for networked systems with linear dynamics [30,31,32,33,34]. Recently such developments have been pushed further to structural controllability [35,36,37], where instead of focusing on a specific system setup, controllability is defined as a structural property for generic configurations of the system parameters. The seminal work of Lin established that structural controllability is fully determined by the system zero-pattern, which specifies the locations of the potentially non-zero entries in the parameter space. It turns out that the structural controllability of linear networked systems can also be established from a graph-theoretic point of view, marking significant progress in the study of network controllability [35,36,37].
Controllability analysis from graph theory is a challenging question for multi-agent systems with general nonlinear dynamics. For systems with bilinear dynamics, however, graph-theoretic insights have been shown to be promising towards understanding controllability conditions [29,21]. In bilinear systems, the dynamical evolution of the system state is governed by the product of the system state and the control inputs. Therefore, bilinear systems are nonlinear systems with special geometric constraints and the bilinear property: the system state evolves in a Lie group, and the vector field is a bilinear function taking values in the corresponding Lie algebra with respect to the state and the input [9]. Despite its simplicity, bilinear systems have a wide range of applications in the fields of engineering, economic, and even quantum systems [19,13,14,18,23,38]; the study of controllability for bilinear system over Lie groups led to the discovery of the Lie algebra rank condition [10,11,12,15,16,17] as an important chapter in nonlinear system theory.
The Lie algebra rank condition has been shown to be related to the graphical perspective as well. In [29], a framework for the structural controllability of bilinear control systems was proposed, where it was shown that the connectivity of the underlying interaction graph determines the structural controllability of several classes of bilinear control systems over matrix groups. In [21], a graphical notion of permutation cycles was introduced to bilinear systems for the characterization of controllability over the special orthogonal group.
Although the result in [29] considered a special class of drifted systems, the results derived in [29,21] mostly focused on driftless systems. Later in [1,2], controllability and accessibility conditions for bilinear systems were extended to drifted dynamics, where the drift dynamics and controlled dynamics define two interaction graphs, respectively, and their joint connectivity was shown to be critical for ensuring controllability or accessibility of systems over different matrix Lie groups. It is worth emphasizing that for linear networked systems, the system graphs are motivated from agent interconnections often with a physical implication [30,31,32,33,34], while for bilinear systems the system graphs are artificially introduced in order to facilitate a graphical analysis.
In this paper, we study graph theoretic conditions for the structural controllability and accessibility of drifted bilinear systems over Lie groups. For a drifted bilinear system over the special orthogonal group, the general linear group, or the special unitary group, zero patterns are introduced for the drift dynamics and the controlled dynamics, respectively. The zero pattern associated with the drift is assumed to be rigid, as a linear combination with non-zero coefficients of several base elements in a finite subset of the corresponding Lie algebra. As a result, the parameters of the drift dynamics are possibly dependent, similar to the setup in [35] for linear networked systems. The zero pattern associated with the controlled terms is assumed to be free, where coefficients might take zero values for the linear combination of the base elements. First of all, for systems over the special orthogonal group and the general Lie group, two (undirected or directed) graphs are introduced, respectively, corresponding to the drift zero pattern and the controlled zero pattern; structural controllability/accessibility conditions are derived based on connectivity and sizes of connected components.
Next, for systems over the special unitary group, we introduced two edge-colored graphs corresponding to the zero patterns of the drift and controlled dynamics; and then conditions based on connectivity and number of edges in a particular color are established for the structural controllability of the system. Along with the theoretical results, various examples are presented to illustrate the intuitions behind. The technical proofs for all statements are put in the Appendix. The remainder of the paper is organized as follows. In Section 2, we present some preliminary material in graph theory. In Section 3, we define the problem of interest. In Section 4, the main results of the work are presented, followed by some concluding remarks in Section 5.

Undirected Graph
An undirected graph G = (V, E) consists of a finite set V of nodes and an edge set E, where E is a set of unordered pairs of elements in V. If there is an edge {v i , v j } ∈ E, we say that v i and v j are adjacent or neighbours. The number of neighbours of node v is called the degree of v, denoted by deg (v). A graph G is a bi-graph if there is a partition of the node set into V = V 1 V 2 with V 1 and V 2 being nonempty and mutually disjoint, where all edges are between V 1 and V 2 .
A path between two nodes v 1 and v k in G is a sequence of distinct nodes v 1 v 2 . . . v k such that for any m = 1, . . . , k − 1, there is an edge between v m and v m+1 . A pair of distinct nodes v i and v j is said to be reachable from each other if there is a path between them. A node is always assumed to be reachable from itself. We call a graph G connected if every pair of distinct nodes in V is reachable from each other. The subgraph of G derived from the node set V * ⊆ V, denoted by G| V * , is the graph

Directed Graph
consists of a finite set V of nodes and an arc set of v j and v j is an out-neighbor of v i . The number of in-neighbors and out-neighbors of v is called its in-degree and out-degree, denoted by deg + (v) and deg − (v), respectively.
A self-loop in a digraph is an arc starting from and pointing to the same node. A digraph G is simple if it The digraph obtained by removing the self-loop of G is called the simple digraph corresponding to G. A directed path from node v 1 ∈ V to v k ∈ V is a sequence of distinct nodes v 1 v 2 . . . v k such that for any m = 1, . . . , k − 1, (v m , v m+1 ) is a directed arc in E. We say that node v j is reachable from node v i if there is a directed path from v i to v j . A digraph G is strongly connected if every two nodes are mutually reachable. A weakly connected component of a digraph G is a component of G when the directions of links are ignored. Let

Edge-colored Multigraph
Let C = {1, 2, . . . , k} be a set with cardinality k, whose elements are called colors. An edge-colored multigraph G = (V, E ) consists of a finite set V of nodes and an edge set E , where an element e = i, j; c ∈ E denotes an edge with color c ∈ C between nodes i ∈ V and j ∈ V [8]. Each edge has a set of one or two nodes associated to it, which are called its endpoints. A self-loop {i, i; c} ∈ E is an edge that joins a single endpoint to itself.
A multi-edge is a collection of two or more edges having identical endpoints. The edges in a multi-edge are distinguished by different colors. We call an edge-colored multigraph simple if it has neither self-loops nor multi-edges. A complete edge-colored multigraph is a simple edge-colored multigraph such that every pair of nodes is joined by an edge. We say that an edge-colored multigraph G is empty if E is empty.
In an edge-colored multigraph G , a walk W = v 0 , e 1 , v 1 , e 2 , . . . , v k−1 , e k , v k from node v 0 to node v k is an alternating sequence of nodes and edges, such that the endpoints of e i is equal to {v i−1 , v i }, for i = 1, . . . , k.
A closed walk (or cycle) is a walk that begins and ends at the same node. Node v j is reachable from node v i if there is a walk from v i to v j . An edge-colored multigraph is connected if for every pair of nodes v i and v j , there is a walk from v i to v j . A subgraph of G is an edge-colored multigraph H whose nodes and edges are all in G . A maximal connected subgraph of G is called a connected component or simply a component of G .

Bilinear Control Systems over Lie Groups
Let G be a connected Lie group and g be its corresponding Lie algebra. We consider the following bilinear control system over G:Ẋ where X(t) ∈ G, B i ∈ g for i = 0, . . . , m, and u i (t) ∈ R are piecewise continuous control signals for i = 1, . . . , m. For T ≥ 0, the set R T (X 0 ) consists of the points in G that are attainable from X 0 at time T ; i.e., all terminal points X(T ) of solutions of system (1) originating at X(0) = X 0 under all possible The attainable set R(X 0 ) then is defined as the union of such sets R T (X 0 ) for The system Lie algebra of (1) is given as Lie subalgebra of B 0 , B 1 , . . . , B m . The algebraic criteria developed in [15,16,18] can be used to verify the accessibility and controllability of the system (1) by exploiting the algebraic structure of the system Lie algebra. That is, the system (1)

Zero Patterns
Let us assume that g is a finite dimensional vector space over R. Let g a := {g a 1 , . . . , g a k } be a subset of g, i.e., g as ∈ g for all s = 1, . . . , k with k ≥ 1. We introduce the following definition.
Definition 2. (i) The free zero pattern generated by g a , denoted by Σ f (g a ), is defined as the generated linear subspace of g a , i.e., l s g as : l s ∈ R, s = 1, . . . , k .
(ii) The rigid zero pattern generated by g a , denoted by Σ r (g a ), is defined as the set of linear combinations with nonzero coefficients of the elements in g a , i.e.,  (i) Let g a := {g a 1 , g a 2 , g a 3 } with g a 1 = E 12 , g a 2 = E 13 , and g a 3 = E 31 . Then an element G ∈ Σ f (g a ) may take value as E 12 or E 13 ; an element G ∈ Σ r (g a ) can neither be E 12 nor E 13 .
satisfies that G 13 = 2G 12 , G 31 = 3G 12 ; i.e., the zero pattern specified by g b imposes a linear equality constraints on the elements of the matrices therein.
Definition 3. The system (1) is called structurally controllable (accessible) on the Lie group G with respect to the pair of zero patterns Σ zero := (Σ r (g α ), Σ f (g β )) if there exist an integer m ≥ 1, B 0 ∈ Σ r (g α ) and B i ∈ Σ f (g β ), i = 1, . . . , m, such that the system (1) is controllable (accessible) on the Lie group G.

Structural Controllability over SO(n)
The special orthogonal group, SO(n), is the Lie group formed by all R n×n orthogonal matrices whose determinant is equal to one. The Lie algebra of SO(n), so(n), consists of n × n real skew-symmetric matrices, which has the dimension n(n − 1)/2. Define B ij = E ij − E ji . Then the set B = {B ij : 1 ≤ i < j ≤ n} forms a standard basis of so(n). Let A 1 , . . . , A d be d matrices in so(n). We introduce the pair of zero patterns By the compactness of the Lie group SO(n), the system (1) is controllable if and only if it is accessible.
Let V = {1, 2, . . . , n}. We first introduce the following graph representations of the zero patterns. A necessary condition for structural controllability of system (1) is that the union graph G α drift G β contr must be connected [1]. However, this condition is not sufficient. The following theorem gives a sufficient condition for system (1) to be structurally controllable on the Lie group SO(n) with respect to the pair of zero patterns Σ zero = Σ r (so(n) α ), Σ f (so(n) β ) .   It is clear that each connected component of G β contr contains at least three nodes, and the union graph G α drift G β contr is connected. As a result, the graphical condition of Theorem 1 has been met. Choose A = A 1 + 3A 2 + A 3 ∈ Σ r (so(6) α ), and by direct computation one can verify {A, B 12 , B 23 , B 45 , B 56 } LA = so (6). (2) This implies that the system (1) is structurally controllable on the Lie group SO(6) with respect to the pair of zero patterns Σ zero = Σ r (so(6) α ), Σ f (so(6) β ) , providing a validation of Theorem 1.

Structural Accessibility over GL + (n)
Recall that the Lie algebra of GL + (n) is gl(n), the set of all n × n real matrices. The set E = {E ij : 1 ≤ i, j ≤ n} forms a basis of gl(n). Let A 1 , . . . , A d be d matrices in gl(n). A pair of zero patterns Σ zero := Σ r (gl(n) α ), Σ f (gl(n) β ) is given by We similarly introduce the following graph representations of these zero patterns, which now have to be directed graphs.
Note that Lie group GL + (n) is connected, but not compact. A necessary condition for the system (1) to be controllable is that it is accessible. In the presence of the drift term B 0 , accessibility (plus the connectedness of GL + (n)) is not sufficient for controllability. In this case we give some sufficient conditions, and a necessary condition for the system (1) to be structurally accessible on the Lie group GL + (n) with respect to the pair of zero patterns Σ zero = Σ r (gl(n) α ), Σ f (gl(n) β ) .
When the union graph G α drift G β contr is not strongly connected, the system (1) cannot be structurally accessible on the Lie group GL + (n) with respect to the pair of zero patterns Σ zero = Σ r (gl(n) α ), Σ f (gl(n) β ) [1]. The following theorem establishes a sufficient condition under which the system (1) is structurally accessible.
Theorem 2. The system (1) is structurally accessible on the Lie group GL + (n) with respect to the pair of In particular, when gl(n) α is a subset of E, the condition that G β contr has at least one self-loop can be relaxed.
Theorem 3. Suppose gl(n) α ⊆ E. Then the system (1) is structurally accessible on the Lie group GL + (n) with respect to the pair of zero patterns Σ zero = Σ r (gl(n) α ), Σ f (gl(n) β ) if each weakly connected component of G β contr is strongly connected with at least two nodes, and the union graph G α drift G β contr is a strongly connected digraph with at least one self-loop. Example 3. Consider the system (1) evolving on GL + (4). Let gl (4) The drift graph associated with Σ r (gl(4) α ) and the controlled graph associated with Σ f (gl(4) β ) are shown, respectively, in  (i) It is easily seen that each weakly connected component of G β contr is strongly connected with two nodes. In addition, G β contr has one self-loop and the union graph G α drift G β contr is strongly connected. Hence, the graphical condition of Theorem 2 has been met. (4). Thus, the system (1) is structurally accessible on the Lie group GL + (4) with respect to the pair of zero patterns Σ zero = Σ r (gl(4) α ), Σ f (gl(4) β ) . This provides a validation of Theorem 2.
. This is to say, for any integer m ≥ 1, and for any B 0 ∈ Σ r (gl (4) Therefore, the system (1) is not structurally accessible on the Lie group GL + (4) with respect to the pair of zero patterns Σ zero = Σ r (gl(4) α ), Σ f (gl(4) β ) . Generally speaking, the self-loop of G α drift cannot replace the role of the self-loop of G β contr , which is why we require the set gl(n) α to be a subset of E in Theorem 3.
Example 4. Consider the system (1) evolving on GL + (4). Let gl (4) The drift graph associated with Σ r (gl(4) α ) and the controlled graph associated with Σ f (gl(4) β ) are shown, respectively, in Figure 4. Each weakly connected component of G β contr is strongly connected with two nodes. The union graph G α drift G β contr continues to be strongly connected. Moreover, G α drift has a self-loop. Therefore, the graphical condition of Theorem 3 is satisfied. For any A ∈ Σ r (gl(4) α ), we have A = l 1 E 12 +l 2 E 13 +l 3 E 31 +l 4 E 33 +l 5 E 42 This allows us to further obtain {A, E 12 , E 21 , E 34 , E 43 } LA = gl(4). As a result, the system (1) is structurally accessible on the Lie group GL + (4) with respect to the pair of zero patterns Σ zero = Σ r (gl(4) α ), Σ f (gl(4) β ) . This provides a validation of Theorem 3.

Structural Controllability over SU(n)
The special unitary group, SU(n), is the Lie group formed by all C n×n unitary matrices with determinant one. The Lie algebra of SU(n) is equal to su(n), the set of all C n×n skew-Hermitian matrices with trace zero. Lie algebra su(n) is a finite dimensional vector space over R. Let sym(n) denote the vector space containing all real traceless symmetric matrices. The Cartan-like decomposition of su(n) is given by su(n) = so(n)⊕i sym(n), where i is the imaginary unit. It follows easily that the dimension of su(n) is equal to n 2 −1.
The maximal linearly independent set of D, denoted by D L , contains n − 1 elements. Then B C D L forms a basis of su(n).
The graphs corresponding to the zero patterns Σ r (su(n) α ) and Σ f (su(n) β ) are edge-colored multigraphs.
Similar to SO(n), SU(n) is also connected and compact, the controllability analysis of the system (1) on SU(n) relies on the investigation of the equivalence between the system Lie algebra and the underlying Lie algebra su(n). In this section we shall look for necessary and sufficient conditions for the system (1) to be structurally controllable on the Lie group SU(n) with respect to the pair of zero patterns Σ zero = Note that, for the graph G   Example 5. Consider the system (1) evolving on SU(5). Let su (5) The drift graph associated with Σ r (su(5) α ) and the controlled graph associated with Σ f (su(5) β ) are shown, respectively, in contr is still connected, but it has no self-loops, and no cycles with an odd number of Red edges. We have {B 12 , C 13 , C 34 , B 14 , B 15 } LA = su (5), which is easy to check. However, G α drift has two self-loops.
and, in consequence, the system (1) is structurally controllable on the Lie group SU(5) with respect to the If we replace A 2 = 2B 12 + D 15 + 3B 45 with A 2 = 2B 12 + 3B 45 , then G α drift has no self-loops. However, G α drift G β contr has at least one cycle with an odd number of Red edges.  (5). Therefore, the system (1) is also structurally controllable on the Lie group SU(5) with respect to the pair of zero patterns Σ zero = Σ r (su(5) α ), Σ f (su(5) β ) . This example provides a validation of Theorem 4. Example 6. Consider the system (1) evolving on SU (6). Let su (6) The drift graph associated with Σ r (su(6) α ) and the controlled graph associated with Σ f (su(6) β ) are shown, respectively, in Figure 6.

Conclusions
We have established graphical conditions for structural controllability and accessibility of drifted bilinear systems over Lie groups. Bilinear control systems with drift and controlled terms that evolve over Lie groups were considered. Zero patterns prescribed the possible configuration of the drift and controlled dynamics with respect to a set of base elements in the corresponding Lie algebra. The drift dynamics was assumed to be fixed, taking values as a linear combination of the base elements with strictly nonzero coefficients; the controlled dynamics was assumed to be free with potentially zero coefficients in the configuration. For bilinear systems over the special orthogonal group or the special unitary group, the zero patterns were proven to be associated with two undirected or directed graphs whose connectivity and connected components ensure structural controllability/accessibility. For bilinear systems over the special unitary group, two edge-colored graphs associated with the drift and controlled zero patterns were proven to be critical for investigating structural controllability. Future work might include necessary and sufficient graphical conditions for structural controllability and accessibility, and a computational complexity analysis of the established connectivity conditions.

A. Proof of Theorem 1
We first recall a few auxiliary lemmas that are used in the proof. Consider G as the set of all undirected graphs over the node set V, and B as the class of all subsets of B. By identifying each edge {i, j} with the matrix B ij , we establish a natural 1 − 1 correspondence, between each element in G and each element in B.
We denote such a mapping which maps from B to G. For any A ∈ so(n), we can represent it uniquely in the form The following lemma holds [1].
Lemma 2. Consider a subset S ⊆ B with the associated graph G S := (S) and a matrix A ∈ so(n) with the associated graph G A . The following statements hold.
(i) The Lie algebra generated by {A} S is equal to so(n) if each connected component of G S contains at least three nodes and the union graph G A G S is connected.
(ii) If the Lie algebra generated by {A} S is equal to so(n), then the union graph G A G S is connected.
We are now in a position to show the detailed proof of Theorem 1. Since the union graph G α drift G β contr is connected, there must exist a matrix A ∈ Σ r (so(n) α ) such that G A G β contr is connected. Moreover, each connected component of G β contr contains at least three nodes. Lemma 2. (i) now leads to {A} so(n) β LA = so(n). Therefore, there exist A ∈ Σ r (so(n) α ) and so(n) β ⊂ Σ f (su(n) β ), such that system (1) is controllable on the Lie group SO(n). This is to say, the system (1) is structurally controllable on the Lie group SO(n) with respect to the pair of zero patterns Σ zero = Σ r (so(n) α ), Σ f (so(n) β ) . This is the desired conclusion.

B. Proof of Theorem 2
Before presenting the detailed proof for Theorem 2, we recall some auxiliary lemmas and definitions which will be useful for the analysis.  Consider D as the set of all digraphs over the node set V, and E as the set of all subsets of E. By identifying each arc (i, j) with the matrix E ij ∈ E, we establish a natural 1 − 1 correspondence between each element in D and each element in E. We denote such a mapping τ which maps from E to D. Denote Then with E = E 1 E 2 , for any S ⊆ E 1 , the digraph τ (S) is simple. The following lemmas, Lemma 5, 6, 7 appeared in [2]. We therefore collect them below and the details of their proofs are omitted.
Lemma 5. Given a subset S ⊆ E 1 , let S 0 ⊆ S 1 ⊆ S 2 · · · be an ascending chain of subsets of E 1 such that We denote by sl(n) the vector space of n × n real traceless matrices.
For any A ∈ gl(n), we can represent it uniquely in the form Define the map ϕ that takes a matrix A ∈ gl(n) to a digraph . . , (i * l , j * l ) . We will have established Theorem 2 if we prove the lemma below.
Lemma 8. Consider a subset S ⊆ E with the associated digraph τ (S) and a matrix A ∈ gl(n) with the associated digraph G A = (V, E A ). Let G S = (V, E S ) be τ (S). Then the Lie algebra generated by {A} S is equal to gl(n) if the following conditions hold: (i) Each weakly connected component of G S is strongly connected with at least two nodes; (ii) The digraph G S has at least one self-loop; (iii) The union graph G A G S is strongly connected.
Proof. Let G A = (V, E A ) and G S = (V, E S ) be the simple digraphs corresponding to G A and G S by ignoring the self-loops, respectively. Because the union graph G A G S is strongly connected, the union graph G A G S is strongly connected too. If G S is strongly connected, then by Lemma 6 the Lie algebra generated by {A} S is equal to gl(n). Now, assume that G S is the union of m weakly connected components with m ≥ 2.
Let G i S = (V i , E i S ) denote the i-th weakly connected component of G S for i = 1, . . . , m. It is easily seen that each G i S is strongly connected. According to Lemma 10, there exists an integer z i such that Lemma 5 shows that the elements in {E ij : (i, j) ∈ E * } can be generated by iterated Lie brackets of elements in S.
Define the digraph G valid by G valid := (V, E valid ), where E valid := E A \ E * . As the union graph G A G S is strongly connected while G S is not, we always have |E valid | ≥ 2. Because G A G S is strongly connected, G valid G S is also strongly connected by the definition of G valid . In addition, we can deduce that G valid satisfies: i) all arcs are between different V i and no arcs within each V i ; ii) each V i has at least one node with out-degree greater than zero; iii) each V i has at least one node with in-degree greater than zero.
In addition, the relationship between the Lie bracket [ A, E ij ] and the circumjacent closure at i, j of G valid satisfies for E ij ∈ {E ij : (i, j) ∈ E * }. To prove the statement, we need to consider the Lie algebra generated by {A} S. Since G S has at least one self-loop, without loss of generality we assume that the node v 11 ∈ V 1 has a self-loop, i.e., E v 11 v 11 ∈ S. The remainder of the proof contains two steps.
Step 1. We first prove that if G valid has arcs from the nodes in V 1 to the nodes in V k , k ∈ {2, . . . , m}, then all elements in the set {E ij : i ∈ V 1 , j ∈ V k } can be obtained by iterated Lie brackets of elements in { A} S.
Note that for any node v ∈ V 1 in G valid with deg − (v) > 0, Lemma 6 yields E vv ∈ {S} LA since G 1 S is a strongly connected digraph with self-loops. We only need to consider the case where the out-degree of node v 11 is greater than zero. The analysis for the other nodes in V 1 whose out-degree is greater than zero can be similarly established.
Let deg − (v 11 ) = k > 0, and v i 1 j 1 , . . . , v i k j k be the out-neighbors of v 11 . Apparently, these out-neighbors are in V 2 · · · V m . To be specific, let v i 1 j 1 , . . . , v irjr ∈ V 2 with 1 ≤ r ≤ k. Applying Lemma 3, we deduce that the digraph ϕ [ A, E v 11 v 11 ] satisfies: i) deg − (v 11 ) = k > 0; ii) other nodes in V 1 has zero degree. Fix v 12 ∈ V 1 and v 12 = v 11 . Using Lemma 7, we have Let v i * j * = v i 1 j 1 ∈ V 2 . By selecting the node pair v i 1 j 1 , v i * j * we can obtain Since (v 12 , v 11 ) and (v i 1 j 1 , v i * j * ) are in E * , i.e., E v 12 v 11 , E v i 1 j 1 v i * j * ∈ {S} LA , from (4) and (5) we conclude This implies that where a * is the coefficient generated during the operation of the Lie brackets.
Therefore, E v 12 v i * j * ∈ E 1 can be obtained by iterated Lie brackets of elements in { A} S. This, together with the strong connectivity of G 1 S and G 2 S , implies that all elements in the set {E ij : i ∈ V 1 , j ∈ V 2 } can be obtained by iterated Lie brackets of elements in { A} S.
Step 2. Analysis similar to that in the proof of Theorem 3 in [2] shows that all elements in set S * := {E ij :

C. Proof of Theorem 3
The statement in Theorem 3 will be proved once we prove the lemma below.
Lemma 9. Consider two subset A, S ⊆ E with the associated graphs G A = τ (A) and G S = τ (S), respectively.
There exists a matrix A ∈ Σ r (A) such that the Lie algebra generated by {A} S is equal to gl(n) if the following conditions hold: (i) Each weakly connected component of G S is strongly connected with at least two nodes; (ii) The union graph G A G S is a strongly connected digraph with self-loops.
Proof. Note that G A G S has self-loops. That is, G A or G S has self-loops. Using Lemma 8, for any A ∈ Σ r (A), the generated Lie algebra by {A} S is equal to gl(n) if G S has self-loops. Thus, in the rest of the proof, we consider the case where only G A has self-loops.
If G S is strongly connected, then by Lemma 6 the Lie algebra generated by S contains sl(n). Hence, for Therefore, when trA = 0, i.e., l k=1 a k = 0, we have E i 1 i 1 ∈ {A} S LA . Lemma 6 now yields {A} S LA = gl(n). Consequently, for all A ∈ Σ r (A) with trA = 0, the Lie algebra generated by {A} S is equal to gl(n). Now, let G S be the union of m weakly connected components with m ≥ 2. Consider A ∈ Σ r (A) with trA = 0. We continue to use the definitions of G A , G S , G * , G valid and A in the proof of Lemma 8. By the definition of A, one has Recall that all the elements in {E ij : (i, j) ∈ E * } can be generated by iterated Lie brackets of elements in S. Using Lemma 3, we have Without loss of generality, we assume where a * k = 0 if and only if l k j=l k−1 +1 a j = 0. There must exist a 1 ≤ k ≤ r + 1 such that a * k = 0 since trA = 0. From now on, we will write it simply as A + r+1 k=1 a k E i k i k when no confusion can arise. It is worth pointing out that node i k is in V k for k = 1, . . . , r + 1. The remainder of the proof will be divided into three steps.
Step 1. We first prove that the following relation holds: To this end, consider where A 1 is the part of the linear combination of elements of the form E ri * in A, A 2 is the part of the linear combination of elements of the form E j * t in A, and the remaining part is A 3 . The proof of (8) is based on the following computation.
The term A 3 + r+1 k=1 a k E i k i k can be handled in much the same way, the only difference being in the choice of E i * j * . Repeating this process, we can finally conclude that r+1 k=1 a k E i k i k ∈ {A} S LA .
Step 2. We next prove that for any v k ∈ V k , k = 1, . . . , r + 1, there holds Recall that i k ∈ V k , for k = 1, . . . , r + 1. Based on (7) and (8), it can be concluded that for any v 1 ∈ V 1 and v 1 = i 1 . It is sufficient to show that the statement in (9) holds.
Step 3. In this step, we prove that there must exist a matrix A * ∈ Σ r (A) such that {A * } S LA = gl(n).
As the step 1 in the proof of Lemma 8, we consider the digraph G valid . Let v 11 be the node in V 1 with deg − (v 11 ) = l > 0, and v i 1 j 1 , . . . , v i l j l be the out-neighbors of v 11 . Let v k1 and v k2 denote two different nodes in V k , for k = 1, . . . , r + 1. From (9) we obtain and

D. Proof of Proposition 1
Definition 9. (i) Let S 1 ⊆ B, S 2 ⊆ C and S 3 ⊆ D. The edge-colored multigraph G S 1 S 2 S 3 is given by (ii) Let G be an edge-colored multigraph without self-loops, i.e., there are S 1 ⊆ B and S 2 ⊆ C , such that Then the edge-colored multigraph transitive closure mapping, T (·), is defined as We then recursively define T k (G ) := T (T k−1 (G )) with T 0 (G ) := G . It is worth pointing out that there exists an integer z such that K n is a spanning subgraph of T z (G ) if and only if G is connected, where K n is the complete graph of n vertices. (ii) G S is a connected graph with self-loops; (iii) G S is a connected graph with a cycle containing an odd number of Red edges.
Our subsequent study will be based on the following lemma: Lemma 10. The Lie brackets among the basis elements of su(n) satisfy and for all 1 ≤ i, j, k, l ≤ n.
It is easy to prove this lemma directly, so we omit the proof. (i) Suppose G S has edges of at least two colors, and all the Blue edges together with the vertex set V form a connected graph. It is clear that the edge generated subgraph obtained from all Blue edges is the graph G S 1 . From Lemma 1, we conclude that all the elements in B can be generated by iterated Lie brackets of elements in S 1 , i.e., {S 1 } LA = so(n). Also G S has edges of at least two colors, i.e., S 2 S 3 = ∅. Note that There is no loss of generality in assuming D 12 ∈ S 3 . Notice that B ⊂ {S 1 } LA . By Lemma 10, we have Then it is evident that In addition, [B 2j , D 12 ] = C 2j for j = 3, . . . , n. This clearly forces Lemma 10 now gives D 23 ∈ {S 1 S 3 } LA since [B 23 , C 23 ] = 2D 23 . In the same manner, we can see that We continue in this fashion obtaining C i := {C ij : i + 1 ≤ j ≤ n} ⊂ {S 1 S 3 } LA for i = 4, . . . , n − 1.
Immediately there holds D ⊂ {S 1 S 3 } LA , and consequently, we (ii) Let G S be a connected graph with self-loops. Evidently, the subgraph G S 1 S 2 := V, E S 1 S 2 of G S is connected, and S 3 = ∅. We can certainly assume that D 12 ∈ S 3 . Based on (i), if we prove that the Lie algebra {S} LA contains so(n) as a Lie subalgebra, the statement {S} LA = su(n) follows.
It is worth noting from Lemma 10 and Definition 9 that taking first-order Lie brackets of the elements in S 1 S 2 corresponds to adding edges that connect the endpoints of incident edges in G S 1 S 2 . As G S 1 S 2 is connected, we conclude that there exists an integer z such that K n is a spanning subgraph of T z G S 1 S 2 .
In other words, for any 1 Fix i = 1. There are two cases: (a) if for all 2 ≤ j ≤ n, B 1j ∈ {S 1 S 2 } LA , then {B 12 , . . . , B 1n } is connected and thus {B 12 , . . . , B 1n } LA = so(n). It follows that so(n) shows that B 1j * ∈ {S 1 S 2 S 3 } LA , by taking Lie bracket of C 1j * and D 12 . Hence, for any 2 ≤ j ≤ n, In conclusion, the Lie algebra generated by S contains so(n) as a Lie subalgebra. Furthermore, with (iii) Let G S be a connected graph with a cycle containing an odd number of Red edges. By (ii) it is immediate that if there are self-loops in G S , then {S} LA = su(n). Thus, we focus on proving {S} LA = su(n) for G S without self-loops, i.e., S 3 = ∅.
containing an odd number of Red edges. The set of matrices corresponding to these edges in P will be denoted by S P . The proof is based on the following lemma.
Lemma 11. The Lie algebra generated by S P contains at least one element in D.
The proof is by induction on l, i.e., the cardinality of set S P . We divide our proof in three steps.
Step 1. Notice that the cardinality of set S P C is an odd number. If l = 2, then S Step 2. Let l = 3. There are two possibilities for elements in set S P : i) Induction Hypothesis. For l ≤ K − 1 with K > 2, the conclusion holds.
Step 3. Let l = K and |S P C | = q. Since q is odd, q ≥ 1. We can assume that We must have |S P | = K − 1 and |S P C | = q. By our induction hypothesis, the Lie algebra generated by S P contains at least one element in D. In addition, S P ⊂ {S P } LA . The desired result follows straightforwardly. This proves the desired lemma.
As in the proof of (ii), Lemma 11 gives {S} LA = su(n). We have thus proved the sufficiency.

D.2 Proof of Necessity for Proposition 1
Suppose the conditions in Proposition 1 are not true. Then for the graph G S , there are three possibilities: i) G S is not connected; ii) G S is a connected graph containing only Blue edges; iii) G S is a connected graph without self-loops, and there are no cycles with an odd number of Red edges. It is easy to check that when G S is not connected, the generated Lie algebra by S is not equal to su(n). If G S is a connected graph containing only Blue edges, then {S} LA = so(n). Now let G S be a connected graph without self-loops, and there are no cycles with an odd number of Red edges. The proof is completed by showing that {S} LA = su(n).
First, we establish the relationship between Lie bracket operations and transitive closure of the edgecolored multigraph G S . Since S 3 = ∅, then S = S 1 S 2 . Let S 0 ⊆ S 1 ⊆ S 2 · · · be an ascending chain of A, B ∈ S k . The following lemma holds.
Proof. It is evident that T 0 (G S ) = G S 0 . Thus, in the rest of the proof, we focus on proving T k (G S ) = G S k for k ≥ 1. By the definition of T (·) and S k , we conclude that T (G S k−1 ) = G S k if and only if G S k−1 has no multiple edges. From now on, the notation G R means that G does not have a cycle with an odd number of Red edges.
Recall that G S R. This implies that G S has no multiple edges, and thus T 1 (G S ) = G S 1 . It can be concluded that G S 1 has no multiple edges. If the assertion was false, then there must exist a cycle of length 3 containing an odd number of Red edges in the graph G S . This leads to a contradiction. Therefore, T (G S 1 ) = G S 2 , and, together with G S 1 = T 1 (G S ), we have T 2 (G S ) = G S 2 .
Our task now is to prove that G S 2 has no multiple edges. This result will be proved if we can show that G S 1 R. To this end, consider G S . There are two possibilities for G S : i) Each cycle in G S contains an even number of Red edges (We adopt the convention that 0 is even); ii) G S has no cycles.
• Proof under Case (i): Let each cycle in G S contain an even number of Red edges. Note that G S 1 = T (G S ). We only need to consider the newly generated cycles in G S 1 compared to G S . Let P = Therefore, the parity of the number of Red edges contained in P and P is always the same. It follows that the number of Red edges in P is even, if all edges in P are in G S . If not, we can use the above method to replace the edges of G S 1 in the circle P with the edges of G S , until all the edges in the obtained cycle P * are in G S . Furthermore, the Red edges contained in P and P * have the same parity.
Then it can be concluded that the number of Red edges in P is even.
On account of the arbitrariness of P, we have G S 1 R.
• Proof of Case (ii): if G S has no cycles, then the edge set of graph T (G S ) is the union of triangles like It can be easily verified that T (G S ) R. This gives G S 1 R.
We have thus proved T (G S ) = G S 1 R. In fact, the proof above gives more, namely T k (G S ) R holds for k = 0, 1, 2, .... This certainly guarantees T k (G S ) has no multiple edges for all k ≥ 1, and, in consequence, the proof is completed by an easy induction.
We are now in a position to show that {S} LA = su(n). Note that G S has finitely many vertices and edges, the ascending chain of graphs G S ⊆ G S 1 ⊆ · · · stabilizes in finite steps. That is, there exists a nonnegative integer z such that G S z = G S z+1 = · · · . In addition, G S is connected, and G S k has no multiple edges for all k ≥ 1. It follows that G S z is a complete graph with no multiple edges. From the definition of S k , we deduce that S z spans {S} LA . Hence, {S} LA is a n(n − 1)/2-dimensional subalgebra of su(n), and consequently We have now completed the proof of Proposition 1.

E. Proof of Theorem 4
For any A ∈ su(n), we can represent it in the form of where a k = 0 ∈ R, i k , j k ∈ V, and B i k j k ∈ B, C i k j k ∈ C , D i k j k ∈ D. Define the map ψ that takes a matrix A ∈ su(n) to an edge-colored multigraph Lemma 13. Suppose the graph G = (X Y, E) is a bi-graph with |X| ≥ 3, |Y| ≥ 3 and |E| ≥ 1. Then there exists a finite sequence of node pairs (i 1 , j 1 ), . . . , (i z , j z ) for some integer z ≥ 1 such that (i) Either i s , j s ∈ X or i s , j s ∈ Y for s = 1, 2, . . . , z; (ii) H izjz · · · H i 2 j 2 H i 1 j 1 (G) := X Y, E izjz is also a bi-graph with |E izjz | = 1.
The proof of this lemma appears in [2], and therefore we will omit it. In general, we have the following result, and it can be proved in much the same way as Lemma 13.
Lemma 14. Let G := (V, E) be an undirected graph with |E| ≥ 1. Then there exists a finite sequence of node pairs (i 1 , j 1 ), . . . , (i z , j z ) for some integer z ≥ 1, such that the cardinality of the edge set of graph If G is an edge-colored multigraph without self-loops and multiple edges, then G can be regarded as an undirected graph without considering the color of the edges, and the conclusions in Lemma 13 and 14 are still valid for G . The proof of Theorem 4 is based on the following lemma.
Lemma 15. Consider a subset S ⊆ B C D with the associated multigraph G S = (V, E S ) and a matrix A ∈ su(n) with the associated multigraph G A = (V, E A ). Let G S be connected. Then the Lie algebra generated by {A} S is equal to su(n) if and only if G A G S has a self-loop or a cycle with an odd number of Red edges.
Proof. (Sufficiency) Since G S is connected, Proposition 1 shows that the Lie algebra generated by S is equal to su(n) if G S has a self-loop or a cycle with an odd number of Red edges. Now, assume that G S has neither a self-loop nor a cycle containing an odd number of Red edges. Analysis similar to that in the proof of necessity for Proposition 1 shows that there exists a nonnegative integer z such that G S z = G S z+1 = · · · . In addition, is a complete graph with no self-loops or multiple edges. It follows that for any 1 i < j n, we have F ij ∈ S z , either F = B or F = C. Below we respectively prove that {A} S LA = su(n) under the condition that G A G S has a self-loop or a cycle with an odd number of Red edges. The proof falls naturally into two parts.
Let us first show that if G A G S has self-loops, i.e., G A has self-loops, then {A} S LA = su(n). Define has neither self-loops nor multiple edges, and |E | ≥ 1. With the notation A = [ A, F 12 ], we have G = ψ( A). Applying Lemma 14, there exists a finite sequence of node pairs (i 1 , j 1 ), . . . , (i w , j w ) for some integer w ≥ 1, such that the cardinality of the edge set of graph

It is immediate that
where a * is the coefficient generated during the operation of the Lie brackets. Since F isjs ∈ S z for s = 1, . . . , w, we have F i * j * ∈ { A} S z LA . In addition, with the definition of A, we have F i * j * / ∈ S z .
Therefore, G {F i * j * } S z has multiple edges. Proposition 1 now yields {F i * j * } S z LA = su(n). This implies that { A} S z LA = su(n), and thus {A} S LA = su(n).
• Proof of Case (ii): in G A , the nodes adjacent to node 1 except node 2 are denoted as i 1 , . . . , i m , and, the nodes adjacent to node 2 except node 1 are denoted as j 1 , . . . , j n , where m, n ≥ 0. If m = 0, let i ∈ V and i = 1 = 2. Then it is evident that graph ψ [ A, F 1i ] has neither self-loops nor multiple edges, and the cardinality of its edge set is greater than or equal to two. This is due to the fact that {1, i} / ∈ E A . neither self-loops nor multiple edges, and the cardinality of its edge set is greater than or equal to one.
In summarizing, there must exist a matrix A ∈ { A} S z LA such that ψ( A) has neither self-loops nor multiple edges, and the cardinality of its edge set is greater than or equal to one. Analysis similar to that in the proof of Case (i) shows that {A} S LA = su(n).
The proof above gives more, namely { A} S z LA = su(n) if A = 0. We next prove that if G A G S has a cycle with an odd number of Red edges, then {A} S LA = su(n).
We continue to use the definition of A in the above. Now A = 0, which is due to the fact that G S z dose not have a cycle with an odd number of Red edges, while G A G S has. It follows easily that {A} S LA = { A} S z LA = su(n). (Necessity) Assume that G A G S has neither self-loops nor a cycle with an odd number of Red edges. Proposition 1 shows that the Lie algebra generated by S is not equal to su(n). In addition, G S z is complete, and it has neither a self-loop nor a cycle with an odd number of Red edges. We must have E A ⊆ E S z , because G A G S z has neither a self-loop nor a cycle with an odd number of Red edges. This implies that {A} S LA = {S} LA = su(n). Therefore, if the Lie algebra generated by {A} S is equal to su(n), then G A G S must have a self-loop or a cycle with an odd number of Red edges. We have now completed the proof of Lemma 15.
We are now in a position to present the proof of Theorem 4. Let G β contr be connected. Since G α drift G β contr has a self-loop or a cycle with an odd number of Red edges, there must exist a matrix A ∈ Σ r (su(n) α ) such that G A G β contr has a self-loop or a cycle with an odd number of Red edges. Using Lemma 15, we see that {A} so(n) β LA = su(n). From this we conclude that the system (1) is structurally controllable on the Lie group SU(n) with respect to the pair of zero patterns Σ zero := Σ r (su(n) α ), Σ f (su(n) β ) .

F. Proof of Theorem 5
The statement in Theorem 5 will be proved once we prove the lemma below.
Lemma 16. Consider a subset S ⊆ B C D with the associated multigraph G S = (V, E S ) and a matrix A ∈ su(n) with the associated multigraph G A = (V, E A ). The Lie algebra generated by {A} S is equal to su(n) if the following conditions hold: (i) Each connected component of G S contains at least three nodes; (ii) G A has no multiple edges and the union graph G A G S is connected; (iii) G A G S has a self-loop or a cycle with an odd number of Red edges.
Proof. If G S is connected, then by Lemma 15, the Lie algebra generated by {A} S is equal to su(n). Now assume that G S has m connected components with m ≥ 2. Let G i = (V i , E i ) denote the i-th connected component of G S for i = 1, . . . , m. We continue to use the definition of S k in the proof of Proposition 1.
Write S = ∞ k=1 S k . There must exist a nonnegative integer z such that S z = S z+1 = . . . , which then implies S = S z . By the definition of S, we see that S z spans {S} LA . Since G S has m connected components, G S z has m connected components too. In addition, for any u < v ∈ V i , B uv ∈ S z or C uv ∈ S z .
We continue to use the definition of A in the proof of Lemma 15. As the union graph G A G S z is connected while G S z is not, we always have E A = ∅, i.e., A = 0. This allows us to further conclude that The remainder of the proof is divided into two steps.
Step 1. We first prove the statement when G S contains only two connected components, i.e., m = 2. Because G A G S is connected, G A G S z is also connected by the definition of G A and G S z . In addition, there must exist an edge {u, v} ∈ G A such that u ∈ V 1 , v ∈ V 2 . Let v 11 be the node in V 1 with deg(v 11 ) = k > 0, and v i 1 j 1 , . . . , v i k j k be its neighbors. For convenience, we let v i 1 j 1 , . . . , v irjr ∈ V 2 , 1 ≤ r ≤ k. Consider the node v 12 ∈ V 1 . We must have F v 11 v 12 ∈ S z , where F = B or F = C.
Let v i * j * = v i 1 j 1 ∈ V 2 . There holds F v i 1 j 1 v i * j * ∈ S z . Lemma 10 now shows that It is immediate that G = ψ( A). From Lemma 13, there is an integer z ≥ 1 and a finite sequence of node pairs either v s , u s ∈ V 1 or v s , u s ∈ V 2 for s = 1, 2, . . . , z, such that H vzuz · · · (H v 1 u 1 (G )) = V 1 V 2 , E vzuz is also a bi-graph with |E vzuz | = 1. Let Note that {v s , u s } ∈ E S z , we have F vsus ∈ S z for s = 1, . . . , z.
Based on Definition 10 and Lemma 10, it can be concluded without considering the color of the edges. This yields where a * is the coefficient generated during the operation of the Lie brackets. Therefore, F v * u * ∈ { A} S z LA , and, together with the connectivity of G {F v * u * } S z , Lemma 15 now leads to By (11) it is obvious that {A} S LA = su(n).
Step 2. In this step, we proceed to establish the result for the general case by induction on the number of connected components of G S .
Induction Hypothesis. If graph G S contains m ≥ 2 connected components, then {A} S LA = su(n).
We will prove it for m + 1.
To do this, consider G A . Let v 11 be the node in V 1 with deg(v 11 ) = k > 0, and v i 1 j 1 , . . . , v i k j k denote the nodes that are adjacent to v 11 . There is no loss of generality in assuming v i 1 j 1 , . . . , v irjr ∈ V 2 , with 1 ≤ r ≤ k. Analysis similar to that in the step 1 shows that where G a = (V 1 V 2 , E a ) is a bi-graph with |E a | ≥ 1, G b = ( m+1 i=3 V i , E b ) is a empty graph. Again we apply Lemma 13 to G a and obtain F v * u * ∈ { A} S z LA with v * ∈ V 1 , u * ∈ V 2 . It follows immediately that F v * u * ∈ {A} S LA . Now G {F v * u * } S has m connected components, and by our induction hypothesis, {A} {F v * u * } S LA = su(n). Thus we arrive at the conclusion that {A} S LA = su(n), and the proof is complete.