On the Controllability of Matrix-weighted Networks

Lulu Pan, Haibin Shao, Mehran Mesbahi, Yugeng Xi, Dewei Li

Abstract

This letter examines the controllability of consensus dynamics on matrix-weighed networks from a graph-theoretic perspective. Unlike scalar-weighted networks, the rank of the weight matrix introduces additional intricacies into characterizing the dimension of the controllable subspace. Specifically, we investigate how the definiteness of weight matrices influences the dimension of the controllable subspace. Graph-theoretic characterizations of the lower and upper bounds on the dimension of the controllable subspace are provided by employing distance partitions and almost equitable partitions, respectively. Furthermore, the structure of an uncontrollable input for such networks is examined, with examples provided to demonstrate the theoretical results.

Introduction

In traditional multi-agent systems, such as drone swarms or social networks, the strength of a connection between two nodes is usually represented by a single scalar value. However, many real-world systems—such as opinion dynamics involving multiple interdependent topics or bearing-based formation control—require matrix weights to capture how different components of an agent's state influence another.

While the controllability of scalar networks is well-understood, matrix-weighted networks introduce a major complication: the rank of the weight matrix. In scalar networks, an edge either exists or it doesn't. In matrix networks, an edge can exist but be "weak" in certain directions (low rank), which can silently break the controllability of the entire system. This research establishes mathematical rules for predicting these controllability limits based on the network's topology and the algebraic properties of its matrix weights.

Methodology: Graph-Theoretic Analysis

The study employs a graph-theoretic approach to analyze Laplacian dynamics, modeled as $\dot{x}(t) = -Lx(t) + Bu(t)$, where $L$ is the matrix-valued Laplacian. The primary tools for this analysis are:

  • Distance Partitions: Used to derive lower bounds. By grouping nodes based on their shortest-path distance from a leader node, the authors show how "positive definite" paths (where every matrix weight is full rank) allow control signals to propagate effectively.
  • Almost Equitable Partitions (AEP): Used to derive upper bounds. An AEP partitions a graph into cells where nodes share aggregate weights to other cells. This structural symmetry creates redundant dynamics that the control input cannot break, effectively capping the dimension of the controllable subspace.
Figure 2: A 5-node path graph used to illustrate distance-based partitioning and lower bounds on controllability.

Key Insights and Results

A pivotal finding is the "Definiteness" Threshold. In scalar networks, connectivity is often enough for controllability. In matrix networks, the definiteness of the weights is critical. If a path consists of positive semi-definite matrices (which may have a null space) rather than positive definite matrices (full rank), the dimension of the controllable subspace can drop, even if the graph appears perfectly connected.

Figure 1: A 6-node network topology used to demonstrate the impact of matrix weights and structural symmetry on the controllable subspace.

Formal Bounds

  • Lower Bound for Trees: For a matrix-weighted tree, if there is a positive definite path to the furthest node in a distance partition, the dimension of the controllable subspace is at least $d \times (\text{number of partitions})$, where $d$ is the state dimension.
  • Upper Bound via AEP: If the network has an AEP with $s$ cells and leader nodes are chosen symmetrically within those cells, the controllable dimension is at most $d \times s$.
  • Numerical Demonstration: In one example, changing a single edge weight from a positive definite matrix to a positive semi-definite matrix reduced the controllable dimension from 10 to 9, rendering the system uncontrollable.

Conclusion

This work successfully bridges the gap between the geometric layout of a graph and the algebraic properties of its weights. While the current analysis focuses on positive (semi-)definite weights and static topologies, it provides a foundation for future work on "signed" matrix-weighted networks, which would allow for modeling competitive or adversarial interactions between agents.

Summary updated

Abstract

This letter examines the controllability of consensus dynamics on matrix-weighed networks from a graph-theoretic perspective. Unlike the scalar-weighted networks, the rank of weight matrix introduces additional intricacies into characterizing the dimension of controllable subspace for such networks. Specifically, we investigate how the definiteness of weight matrices influences the dimension of the controllable subspace. In this direction, graph-theoretic characterizations of the lower and upper bounds on the dimension of the controllable subspace are provided by employing, respectively, distance partition and almost equitable partition of matrix-weighted networks. Furthermore, the structure of an uncontrollable input for such networks is examined. Examples are then provided to demonstrate the theoretical results.
BibTeX
@inproceedings{pan2020controllability,
  author = {Lulu Pan and Haibin Shao and Mehran Mesbahi and Yugeng Xi and Dewei Li},
  title = {{On the Controllability of Matrix-weighted Networks}},
  booktitle = {IEEE Control. Syst. Lett},
  year = {2020},
  url = {https://openreview.net/forum?id=CDTuF4xjXvK},
}
Figure