pith. sign in

arxiv: 1906.11551 · v1 · pith:GPUBA77Gnew · submitted 2019-06-27 · 🧮 math.OC

Controllability of Kronecker Product Networks

Yuqing Hao , Qingyun Wang , Zhisheng Duan , Guanrong Chen This is my paper

Pith reviewed 2026-05-25 15:05 UTC · model grok-4.3

classification 🧮 math.OC
keywords Kronecker productcontrollabilitydirected graphsmulti-agent systemsnetworked control systemsalgebraic conditionslinear systems
0
0 comments X

The pith

A necessary and sufficient condition determines controllability of Kronecker product networks from their factor graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper derives a necessary and sufficient condition for the controllability of networks formed as the Kronecker product of two general directed graphs. This condition makes explicit how the controllability of each factor network determines that of the composite network. For the special case in which at least one factor network is diagonalizable, the condition reduces to an easily verifiable test. The work also examines higher-dimensional multi-agent systems, shows that a previously reported controllability criterion does not hold, and supplies a corrected necessary and sufficient condition. The results are illustrated through examples.

Core claim

The authors derive a necessary and sufficient condition for controllability of the Kronecker product of two directed graphs that directly relates the rank properties of the controllability matrices of the factors to the composite system. When one factor network is diagonalizable an explicit and simpler form of the condition is obtained. In addition a prior necessary and sufficient condition for the controllability of higher-dimensional multi-agent systems is shown to be incorrect and is replaced by a corrected version.

What carries the argument

The Kronecker product of the system matrices of the factor networks, which encodes how their individual controllability properties interact in the composite system.

Load-bearing premise

Controllability of the composite network is completely determined by algebraic rank conditions on the matrices of the factor networks under the standard linear state-space model.

What would settle it

A small directed graph pair where the proposed condition is satisfied but direct computation of the controllability matrix of the Kronecker product shows it has deficient rank.

Figures

Figures reproduced from arXiv: 1906.11551 by Guanrong Chen, Qingyun Wang, Yuqing Hao, Zhisheng Duan.

Figure 1
Figure 1. Figure 1: Factor graphs G1 and G2 and their Kronecker product G = G1 × G2 1, 2, · · · , n. Moreover, the roles of uk and vk in the above statement can be exchanged. Definition 1 [22] A row vector xm is called the mth￾order generalized left eigenvector of matrix A corre￾sponding to its eigenvalue λ if xm(A − λI) m = 0, and xm(A − λI) m−1 6= 0. Moreover, x1, · · ·, xg form a left Jordan chain of A on top of x1, where … view at source ↗
Figure 2
Figure 2. Figure 2: Graph G1 easy to verify that A(G1) =     8.5 4 −0.5 3.5 8 0.5 3.5 3 5.5     . The eigen￾values of A(G1) are λ1 = 12, λ2 = 5. The left eigenvector associated with λ1 is v1 = −e1 − e2 and the left Jordan chain corresponding to λ2 is v 1 2 = e2 −e3, v 2 2 = −e1 +e2. It is easy to obtain that A(G1) is non-diagonalizable. Assume that the second node of G1 is under control. Thus, one has B1 = e T 2 . Let… view at source ↗
Figure 4
Figure 4. Figure 4: Factor graphs G1 and G2     1 1 2 0 2 0 0 1 3     and A(G2) =     6 1 2 0 2 0 0 5 3     . The eigenvalues of A(G1) are λ1 = 2, λ2 = 1 and λ3 = 3 with the cor￾responding left eigenvectors v1 = e2, v2 = e1 − e3 and v3 = e2 + e3, respectively. The eigenvalues of A(G2) are µ1 = 2, µ2 = 3 and µ3 = 6 with the correspond￾ing left eigenvectors w1 = e2, w2 = 5e2 + e3, w3 = 3/2e1 + 13/8e2 + e3, respe… view at source ↗
Figure 3
Figure 3. Figure 3: Factor graphs G1 and G2     8.5 6 −2.5 3.5 6 2.5 3.5 6 2.5     and A(G2) =     8.5 4 −0.5 3.5 8 0.5 3.5 3 5.5     . Note that A(G1) is diagonalizable. The eigenvalues of A(G1) are λ1 = 12, λ2 = 5 and λ3 = 0 with the corresponding left eigenvectors v1 = e1 + e2, v2 = −e1 + e3 and v3 = −e2 +e3, respectively. Moreover, the eigenvalues of A(G2) are µ1 = 12, µ2 = 5. The left eigenvector associ￾a… view at source ↗
Figure 5
Figure 5. Figure 5: A path network Consider the undirected path network with three nodes depicted in [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
read the original abstract

A necessary and sufficient condition is derived for the controllability of Kronecker product networks, where the factor networks are general directed graphs. The condition explicitly illustrates how the controllability of the factor networks affects the controllability of the composite network. For the special case where at least one factor network is diagonalizable, an easily-verifiable condition is explicitly expressed. Furthermore, the controllability of higher-dimensional multi-agent systems is revisited, revealing that some controllability criterion reported in the literature does not hold. Consequently, a modified necessary and sufficient condition is established. The effectiveness of the new conditions is demonstrated through several examples.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript derives a necessary and sufficient condition for controllability of the Kronecker product of two general directed graphs under the standard linear-system definition, explicitly relating the controllability properties of the factor networks to those of the composite network. It supplies a simplified, easily verifiable condition when at least one factor is diagonalizable and corrects an existing controllability criterion for higher-dimensional multi-agent systems, with several examples provided to illustrate the results.

Significance. If the algebraic conditions hold, the work supplies a practical tool for analyzing controllability in composite networked systems, directly extending classical rank conditions on the controllability matrix via Kronecker-product identities. The explicit dependence on factor controllability and the correction to prior multi-agent literature are useful contributions; the paper's use of standard linear-algebra operations without additional ad-hoc assumptions is a strength.

major comments (2)
  1. [Theorem on general directed graphs] The central necessary-and-sufficient condition (stated after the preliminaries) is obtained by mapping the rank of the composite controllability matrix to algebraic properties of the factors; however, the derivation does not explicitly address whether the rank condition remains necessary when the input matrix of the composite system is formed by a non-standard embedding rather than the pure Kronecker structure.
  2. [Multi-agent correction] In the section revisiting higher-dimensional multi-agent systems, the claim that a prior criterion does not hold is supported by a counter-example, but the modified condition is not shown to be tight on the same example (i.e., the new rank condition is verified but the gap between the old and new criteria is not quantified).
minor comments (2)
  1. [Preliminaries] Notation for the controllability matrix of the Kronecker product network should be introduced with an explicit equation number so that later references to its rank are unambiguous.
  2. [Numerical examples] The examples section would benefit from a table summarizing the factor graphs, their individual controllability ranks, and the composite rank for each case.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and the recommendation of minor revision. We address each major comment below and have revised the manuscript accordingly where appropriate.

read point-by-point responses

  1. Referee: [Theorem on general directed graphs] The central necessary-and-sufficient condition (stated after the preliminaries) is obtained by mapping the rank of the composite controllability matrix to algebraic properties of the factors; however, the derivation does not explicitly address whether the rank condition remains necessary when the input matrix of the composite system is formed by a non-standard embedding rather than the pure Kronecker structure.

    Authors: The theorem and its proof are derived specifically for the standard Kronecker product network, in which the composite input matrix is the Kronecker product of the factor input matrices. The rank identities used in the derivation hold under this exact structure. The manuscript does not claim the condition for non-standard embeddings of the input matrix; such cases lie outside the problem formulation. We will add a clarifying remark immediately after the theorem statement to emphasize that the result applies only to the pure Kronecker structure. revision: yes

  2. Referee: [Multi-agent correction] In the section revisiting higher-dimensional multi-agent systems, the claim that a prior criterion does not hold is supported by a counter-example, but the modified condition is not shown to be tight on the same example (i.e., the new rank condition is verified but the gap between the old and new criteria is not quantified).

    Authors: The counter-example is used to show that the earlier criterion is not necessary. The new condition is proven to be both necessary and sufficient in the general theorem, so it is tight by construction and holds on the example. To make the comparison more explicit, we will expand the example discussion to include a direct comparison of the rank values obtained under the old versus new conditions. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper derives a necessary and sufficient controllability condition for Kronecker product networks of general directed graphs by applying standard linear-algebraic rank conditions on the composite controllability matrix. This maps factor-network properties to the composite system using the definition of the Kronecker product and the PBH test or controllability matrix rank, without any step that defines the output in terms of itself, renames a fitted quantity as a prediction, or relies on a load-bearing self-citation chain. The correction to a prior literature criterion is presented as an independent algebraic counter-example rather than a self-referential loop. The derivation is therefore self-contained against external linear-control benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on the standard definition of controllability for linear time-invariant systems and the algebraic properties of the Kronecker product; no free parameters, invented entities, or ad-hoc axioms are mentioned in the abstract.

axioms (1)
  • standard math Controllability of a linear system is equivalent to the rank condition on the controllability matrix formed from the system and input matrices.
    This is the classical definition invoked when the abstract speaks of necessary and sufficient conditions for controllability.

pith-pipeline@v0.9.0 · 5625 in / 1238 out tokens · 30418 ms · 2026-05-25T15:05:22.201485+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages · 1 internal anchor

  1. [1]

    O., & Gharesifard, B

    Aguilar, C. O., & Gharesifard, B. (2017). Almost equitab le partitions and new necessary conditions for network controllability. Automatica, 80, 25–31

    work page 2017

  2. [2]

    Asavathiratham, C., Roy, S., Lesieutre, B., & Verghese, G. (2001). The influence model. IEEE Control Systems Magazine, 21(6), 52–64

    work page 2001

  3. [3]

    Cai, N., Zhang, Y. S. (2010). Formation controllability of high-order linear time-invariant swarm systems. IET Control Theory and Applications , 4(4), 646–654

    work page 2010

  4. [4]

    Chapman, A., Mesbahi, M. (2014). Kronecker product of networked systems and their approximates. In 21st International Symposium on the Mathematical Theory of Networks and Systems . Groningen, the Netherlands (pp. 1426–1431)

    work page 2014

  5. [5]

    Chapman, A., Nabi-Abdolyousefi, M., & Mesbahi, M. (2014) . Controllability and observability of network-of-network s 9 via Cartesian products. IEEE Transactions on Automatic Control, 59(10), 2668–2679

    work page 2014

  6. [6]

    Chen, G. R. (2017). Pinning control and controllability of complex dynamical networks. International Journal of Automation and Computing , 14(1), 1–9

    work page 2017

  7. [7]

    R., W ang, X

    Chen, G. R., W ang, X. F., & Li, X. (2014). Fundamentals of Complex Networks: Models, Structures and Dynamics . Wiley Press

    work page 2014

  8. [8]

    Hammack, R., Imrich, W., & Klavzar, S. (2011). Handbook of Product Graphs . CRC Press

    work page 2011

  9. [9]

    Q., Duan, Z

    Hao, Y. Q., Duan, Z. S., & Chen, G. R. (2018). Further on the controllability of networked MIMO LTI systems. International Journal of Robust and Nonlinear Control , 28(5), 1778–1788

    work page 2018

  10. [10]

    Hautus. M. L. J. (1969). Controllability and observabi lity conditions of linear autonomous systems. Nederlandse Akademie van Wetenschappen Proceedings Series A- Mathematical Sciences, 72(5), 443–448

    work page 1969

  11. [11]

    A., & Johnson, C

    Horn, R. A., & Johnson, C. R. (1991). Topics in matrix analysis. Cambridge, U.K.: Cambridge Univ. Press

    work page 1991

  12. [12]

    Hsu, S.-P. (2017). A necessary and sufficient condition f or the controllability of single-leader multi-chain systems . Int. J. Robust Nonlinear Control , 27(1), 156–168

    work page 2017

  13. [13]

    Kalman, R. E. (1962). Canonical structure of linear dynamical systems. Proceedings of the National Academy of Sciences of the United States of America , 48(4), 596–600

    work page 1962

  14. [14]

    Leskovec, J. (2010). Kronecker graphs: an approach to modeling networks. Journal of Machine Learning Research , 11, 985–1042

    work page 2010

  15. [15]

    Y., Slotine, J

    Liu, Y. Y., Slotine, J. J., & Barabasi, A. L. (2011). Controllability of complex networks. Nature, 473(7346), 167– 173

    work page 2011

  16. [16]

    Loan, C. F. Van (2000). The ubiquitous Kronecker produc t. Journal of Computational and Applied Mathematics , 123, 85–100

    work page 2000

  17. [17]

    Nabi-Abdolyousefi, M., & Mesbahi, M. (2013). On the controllability properties of circulant networks. IEEE Transactions on Automatic Control , 58(12), 3179–3184

    work page 2013

  18. [18]

    Notarstefano, G., & Parlangeli, G. (2013). Controllab ility and observability of grid graphs via reduction and symmetries. IEEE Transactions on Automatic Control , 58(7), 1719–1731

    work page 2013

  19. [19]

    Parlangeli, G., & Notarstefano, G. (2012). On the reachability and observability of path and cycle graphs. IEEE Transactions on Automatic Control , 57(3), 743–748

    work page 2012

  20. [20]

    Pasqualetti, F., Zampieri, S., & Bullo, F. (2014). Controllability metrics, limitations and algorithems for complex networks. IEEE Transactions on Network Systems , 1(1), 40–52

    work page 2014

  21. [21]

    & Egerstedt, M

    Rahmani, A., Ji, M., Mesbahi, M. & Egerstedt, M. (2009). Controllability of multi-agent systems from a graph-theor etic perspective. SIAM Journal on Control and Optimization , 48(1), 162–186

    work page 2009

  22. [22]

    Roman, M. (2005). Advanced Linear Algebra . New York: Springer

    work page 2005

  23. [23]

    Q., & Xie, L

    Sun, C., Hu, G. Q., & Xie, L. H. (2017). Controllability o f multi-agent networks with antagonistic interactions. IEEE Transactions on Automatic Control , 62(10), 5457–5462

    work page 2017

  24. [24]

    A., & Hautus, M

    Trentelman, H., Stoorvogel, A. A., & Hautus, M. (2012). Control Theory for Linear Systems . New York: Springer

    work page 2012

  25. [25]

    R., W ang, X

    W ang, L., Chen, G. R., W ang, X. F., & Tang, W. K. S. (2016) Controllability of networked MIMO systems. Automatica, 69, 405–409

    work page 2016

  26. [26]

    M (1962)

    W eichsel, P. M (1962). The Kroneker product of graphs. Proceedings of the American Mathematical Society , 13(1), 47–52

    work page 1962

  27. [27]

    Upper and lower bounds for controllable subspaces of networks of diffusivel y coupled agents

    Xue, M. R., & Roy, S. (2018). Comments on “Upper and lower bounds for controllable subspaces of networks of diffusivel y coupled agents”. IEEE Transactions on Automatic Control , 63(7), 2306

    work page 2018

  28. [28]

    R., & Roy, S

    Xue, M. R., & Roy, S. (2017). Input-output properties of linearly-coupled dynamical systems: Interplay between lo cal dynamics and network interactions. In 56th IEEE conference on decision and control . Melbourne, Australia (pp. 487–492)

    work page 2017

  29. [29]

    R., & Roy, S

    Xue, M. R., & Roy, S. (2012). Kronecker products of defec tive matrices: some spectral properties and their implications on observability. In 2012 American Control Conference . Montreal, Canada (pp. 5202–5207)

    work page 2012

  30. [30]

    Modal Barriers to Controllability in Networks with Linearly-Coupled Homogeneous Subsystems

    Xue, M. R., & Roy, S. (2018). Modal barriers to controlla bility in networks with linearly-coupled homogeneous subsystems . arXiv preprint arXiv:1805.01995

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  31. [31]

    Z., Zhao, C., Di, Z

    Yuan, Z. Z., Zhao, C., Di, Z. R., W ang, W. X., & Lai, Y. C. (2013). Exact controllability of complex networks. Nature Communication, 4, 2447

    work page 2013

  32. [32]

    Zhang, S., Cao, M, & Camlibel, M. K. (2014). Upper and lower bounds for controllable subspaces of networks of diffusively coupled agents. IEEE Transactions on Automatic Control, 59(3), 745–750

    work page 2014

  33. [33]

    Zhang, Y., & Zhou, T. (2017). Controllability analysis for a networked dynamic system with autonomous subsystems. IEEE Transactions on Automatic Control , 62(7), 3408–3415

    work page 2017

  34. [34]

    Zhou, T. (2015). On the controllability and observabil ity of networked dynamic systems. Automatica, 52, 63–75. 10

    work page 2015