# Distributed algorithms for the least square solution of linear equations

Yi Huang and Ziyang Meng This work has been supported in part by the National
Natural Science Foundation of China under Grants U19B2029, 61873140, and
61833009, and the Institute for Guo Qiang of Tsinghua University under Grant
2019GQG1023. (Corresponding author: Ziyang Meng.) Yi Huang and Ziyang Meng are
with the Department of Precision Instrument, Tsinghua University, Beijing
100084, China (e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

This paper proposes distributed algorithms for solving linear equations to
seek a least square solution via multi-agent networks. We consider that each
agent has only access to a small and imcomplete block of linear equations
rather than the complete row or column in the existing literatures. Firstly,
we focus on the case of a homogeneous partition of linear equations. A
distributed algorithm is proposed via a single-layered grid network, in which
each agent only needs to control three scalar states. Secondly, we consider
the case of heterogeneous partitions of linear equations. Two distributed
algorithms with doubled-layered network are developed, which allows each
agent’s states to have different dimensions and can be applied to
heterogeneous agents with different storage and computation capability.
Rigorous proofs show that the proposed distributed algorithms collaboratively
obtain a least square solution with exponential convergence, and also own a
solvability verification property, i.e., a criterion to verify whether the
obtained solution is an exact solution. Finally, some simulation examples are
provided to demonstrate the effectiveness of the proposed algorithms.

###### Index Terms:

Distributed algorithms, least square solution, linear equations, multi-agent
networks

##  I Introduction

The problem of solving a linear algebraic equation has received significant
consideration due to its broad application in practical engineering including
wireless sensor network [1], simultaneous localization and mapping [2],
electromagnetism computations [3], PageRank problem of search engine [4], and
etc. Some classical algorithms including Jacobi method, Gauss-Seidel method,
are first developed in a centralized manner [5]. Nevertheless, due to the
limited computation, storage and communication resources of the central node,
these algorithms are not applicable to the case of large-scale linear
equations with a large number of unknown variables. Compared with these
centralized methods, distributed algorithms are more effective to solve the
large-scale linear equations [6]. By virtue of multi-agent networks,
distributed algorithm decomposes the large-scale linear equations into many
small-scale linear equations for each agent in the network. By exchanging the
information with local neighbors, all the agents can solve the original linear
equation in a collaborative way.

Based on consensus control and optimization method, many distributed
algorithms have been proposed to solve the linear equations $Ax=b$. For
instance, by considering each agent only has access to a few rows of $A$ and
$b$, discrete-time distributed algorithms are proposed in [7, 8, 9, 10, 11]
and continuous-time algorithms are developed in [12, 13, 14, 15]. However,
most of these existing algorithms are proposed for solving the linear
equations which have exact solutions. In the practical applications, many
linear equations are over-determined where the number of linear equations is
much larger than that of the unknown variables. In general, the over-
determined linear equation has no exact solution and only seeks a least square
solution. For the case of over-determined linear equations, above mentioned
algorithms can not achieve a least square solution.

To seek a least square solution of linear equations, some distributed
algorithms are proposed by transforming the least square problem into a
distributed optimization problem. For instance, a continuous-time distributed
algorithms is developed by using the classical Arrow-Hurwic-Uzawa flow to find
a least square solution and its discrete version is given in [16]. A
consensus-based sub-gradient continuous-time algorithms is proposed to compute
a least square solution in [17]. By considering each agent knows a few columns
of $A$ and $b$, a distributed algorithm by using saddle point dynamics is
proposed such that a least square solution is obtained in [18]. In addition,
several discrete-time distributed algorithms are developed in [19, 20, 21] to
obtain a least-square solution.

We note that most of above algorithms require that each agent knows at least
one complete row information of the overall linear equations and the estimated
state of each agent has same dimension as the unknown variables to be solved.
For the case of the large-scale linear equations with large dimension of the
unknown variables, above mentioned algorithms may fail by considering that
each agent only has limited storage, computation and communication resources.
Recently, in [22], a continuous-time distributed algorithm with scalar state
is proposed for solving linear equation, in which each agent has only access
to two scalar elements of $A$ and $b$, and the estimated states are also two
scalars. Furthermore, some scalable distributed algorithms for solving linear
equations are proposed by introducing double-layered multi-agent networks in
[23]. However, the proposed algorithms in [22, 23] are only effective for the
linear equations that have exact solutions, and cannot be applied for over-
determined linear equations to achieve a least square solution.

Motivated by above discussions, the objective of this paper is to develop
distributed algorithms with small state dimension for each agent to find a
least square solution of linear equations. Inspired by the work in [23], we
consider that one homogeneous partition and two different heterogeneous
partitions of linear equations, in which each agent has only access to a small
and imcomplete block of the linear equations (can be as small as two scalar
elements). Firstly, we develops a distributed algorithm via a single-layered
grid network for homogeneous partition case, in which each agent only needs to
control three scalar states. Secondly, two distributed algorithms via doubled-
layered network for two heterogeneous partitions are proposed, in which each
agent’s states are allowed to be different dimensions and even scalars.
Compared with the existing results, the main contributions of this paper are
three-fold:

(1) Unlike the existing algorithms in [12, 13, 14, 15, 16, 17, 18, 19, 20, 21]
that requires complete row or column information, we consider that each agent
has only access to two scalar elements when the considered linear equation is
partitioned as small as possible. In such a case, each agent only has three
scalar states and therefore has low requirements of computation, storage and
communication resources for solving the large-scale equations.

(2) In contrast with the distributed algorithms in [22, 23] that are only
effective for the linear equations that have at least one solution, the
proposed distributed algorithms can be applied for over-determined linear
equations to achieve a least-square solution. In particular, the ideas of
dynamic average consensus is introduced, and a crucial eigenvalue analysis of
the general block matrix is provided to show the exponential convergence of
the proposed algorithms.

(3) The proposed distributed algorithms do not require the assumption in [16,
21] that the least square solution of linear equation is unique. Most
importantly, the proposed algorithms are capable of verifying whether the
obtained least-square solution is an exact solution or not.

The rest of this paper is organized as follows. In Section II, we formulate
the least square problem of linear equation. Several distributed algorithms
under homogenous and heterogenous partitions are presented in Section III and
IV, respectively. Finally, conclusions are drawn in Section V.

##  II Preliminaries and problem formulation

Let $\mathbb{R}^{n\times n}$ and $\mathbb{R}^{n}$ be the sets of $n\times n$
real matrices and $n$ dimension real vectors. $\mathbb{C}$ denotes the complex
space. Let $I_{n}$ be a $n\times n$ identity matrix and $1_{n}$ be a
$n$-dimensional vector with all entries being 1. $(\cdot)^{T}$ represents the
transpose in the real space, and $(\cdot)^{H}$ denotes the conjugate transpose
in the complex space. $\|\cdot\|$ denotes the Euclidean norm of a vector or a
matrix. Let $\mathcal{I}_{n}=\\{1,2,\ldots,n\\}$ be a set of natural numbers
up to $n$. $\text{col}(x_{1},\ldots,x_{n})$ denotes a column stack of vectors
$x_{i},i\in\mathcal{I}_{n}$ and $\text{diag}(x_{1},x_{2},\ldots,x_{n})$
denotes the diagonal matrix with diagonal entries being $x_{1}$ to $x_{n}$.
$A\otimes B$ refers to the Kronecker product of the matrices $A$ and $B$.
$\text{ker}(M)$ and $\text{Image}(M)$ denote the kernel space and image space
of matrix $M$, respectively.

Consider the following linear algebraic equation

$\displaystyle Ax=b,x\in\mathbb{R}^{n},$ (1)

where $A\in\mathbb{R}^{m\times n}$ and $b\in\mathbb{R}^{m}$. Note that if
$b\in\text{Image}(A)$, linear equation (1) always has a solution. If
$b\notin\text{Image}(A)$, equation (1) has no solution and its least square
solution is defined by the following optimization problem

$\displaystyle\text{min}_{x\in\mathbb{R}^{n}}\|Ax-b\|^{2}.$ (2)

######  Lemma 1 ([20]).

The variable $x^{*}\in\mathbb{R}^{n}$ is a least square solution of equation
(1) if and only if $A^{T}(Ax^{*}-b)=0$.

##  III Distributed algorithms design under Homogenous partition

In this section, we consider a homogeneous partition of the linear equation
(1). The homogeneous partition means that all the complete row blocks of
matrix $A\in\mathbb{R}^{m\times n}$ have same column partitions or all the
complete column blocks also have same row partitions. To make the analysis
more intuitive, we consider the homogeneous partition of (1) with $m$ row
blocks and $n$ column blocks such that

$\displaystyle
A=\text{col}(A_{1},A_{2},\ldots,A_{m}),A_{i}=[A_{i1},A_{i2},\ldots,A_{in}],$
(3)

with the scalar $A_{ij},i\in\mathcal{I}_{m},j\in\mathcal{I}_{n}$.
Correspondingly, $b=\text{col}(b_{1},b_{2},\ldots,b_{m})$ and
$b_{i}=\sum^{n}_{j=1}b_{ij}$ with the scalar
$b_{ij},i\in\mathcal{I}_{m},j\in\mathcal{I}_{n}$. Note that $b_{i}$ is a
partition of $b$ and $b_{ij}$ can be chosen arbitrarily by satisfying
$b_{i}=\sum^{n}_{j=1}b_{ij}$.

Figure 1: Single-layered grid multi-agent network network

Inspired by the results given in [23], we introduce a single-layered grid
multi-agent network graph $\mathcal{G}$ consisting of $mn$ agents. Each agent
in the graph $\mathcal{G}$ is denoted as
$ij,i\in\mathcal{I}_{m},j\in\mathcal{I}_{n}$, and each agent $ij$ can
communicate with some other agents called its neighbors. The communication
relationship among the row agents
$\mathcal{V}^{R}_{i}=\\{i1,\ldots,in\\},\forall i\in\mathcal{I}_{m}$ is
denoted by an undirected graph
$\mathcal{G}^{R}_{i}=\\{\mathcal{V}^{R}_{i},\mathcal{E}^{R}_{i}\\}$ with the
edge set
$\mathcal{E}^{R}_{i}\subseteq\mathcal{V}^{R}_{i}\times\mathcal{V}^{R}_{i}$.
The row neighbors of agent $ij$ is denoted as
$\mathcal{N}^{R}_{ij}=\\{ik~{}|~{}(ik,ij)\in\mathcal{E}^{R}_{i}\\},\forall
i\in\mathcal{I}_{m}$. Similarly, the communication topology among the column
agents $\mathcal{V}^{c}_{j}=\\{1j,\ldots,mj\\},\forall j\in\mathcal{I}_{n}$ is
denoted by the undirected graph
$\mathcal{G}^{c}_{j}=(\mathcal{V}^{c}_{j},\mathcal{E}^{c}_{j})$ with the edge
set
$\mathcal{E}^{c}_{j}\subseteq\mathcal{V}^{c}_{j}\times\mathcal{V}^{c}_{j}$,
and the column neighbors of agent $ij$ are denoted as
$\mathcal{N}^{c}_{ij}=\\{kj~{}|~{}(kj,ij)\in\mathcal{E}^{c}_{j}\\},\forall
j\in\mathcal{I}_{n}$. Fig. 1 shows an example of such a grid multi-agent
network of homogeneous partition.

######  Assumption 1.

The graphs $\mathcal{G}^{R}_{i}$ and $\mathcal{G}^{c}_{j}$ for any
$i\in\mathcal{I}_{m},j\in\mathcal{I}_{n}$ are undirected and connected .

Suppose that each agent $ij,i\in\mathcal{I}_{m},j\in\mathcal{I}_{n}$ has only
access to two scalars $A_{ij},b_{ij}$. In this section, we target to propose a
distributed algorithm such that the least square problem (2) is solved. In
particular, the objective is to guarantee that each agent $ij$’s state
$x_{ij}$ converges exponentially to a constant scalar $x^{*}_{ij}$ satisfying
that

(i) All $x^{*}_{ij}$ in the same column achieve a consensus $x^{*}_{j}$, i.e.,

$\displaystyle
x^{*}_{1j}=x^{*}_{2j}=\ldots=x^{*}_{mj}=x^{*}_{j},j\in\mathcal{I}_{n}.$ (4)

(ii) The consensus values $x^{*}_{j},j\in\bm{n}$ among all the columns
satisfying that

$\displaystyle\sum^{m}_{i=1}A_{ij}\sum^{n}_{j=1}(A_{ij}x^{*}_{j}-b_{ij})=0.$
(5)

Note that $\sum^{n}_{j=1}A_{ij}x^{*}_{j}-b_{ij}=A_{i}x^{*}-b_{i}$ with
$x^{*}=\text{col}(x^{*}_{1}$ $,\ldots,x^{*}_{n})$. From (5), it follows that
$\sum^{m}_{i=1}A_{ij}(A_{i}x^{*}-b_{i})=0,\forall j\in\bm{n}$, which implies
that $A^{T}(Ax^{*}-b)=0$. Based on Lemma 1, we know that the constant value
$x^{*}_{ij},j\in\bm{n}$ collaboratively forms a least square solution of (1).

###  III-A Distributed algorithm

To ensure that all the agents’ states $x_{ij}$ converge to $x^{*}_{ij}$
satisfying (4) and (5), we introduce two extra variables
$y_{ij},z_{ij}\in\mathbb{R}$ for each agent $ij$. Then, a distributed
algorithm for each agent $ij,i\in\bm{m},j\in\bm{n}$ is given as

$\displaystyle\begin{cases}\dot{x}_{ij}=-(A_{ij}y_{ij}-\sum_{kj\in\mathcal{N}^{c}_{ij}}(z_{ij}-z_{kj}))\\\
~{}~{}~{}~{}~{}~{}~{}~{}-\sum_{kj\in\mathcal{N}^{c}_{ij}}(x_{ij}-x_{kj}),\\\
\dot{\xi}_{ij}=-\sum_{ik\in\mathcal{N}^{R}_{ij}}(y_{ij}-y_{ik}),y_{ij}=\xi_{ij}+\\\
~{}~{}~{}~{}~{}~{}~{}~{}~{}A_{ij}x_{ij}-b_{ij},\\\
\dot{z}_{ij}=A_{ij}y_{ij}-\sum_{kj\in\mathcal{N}^{c}_{ij}}(z_{ij}-z_{kj}),\end{cases}$
(6)

where $\xi_{ij}\in\mathbb{R}$ is an intermediate variable and its initial
value is selected to be zero. In fact, the second equation of (6) utilizes the
ideas of dynamic average consensus approach in [24, 25] such that the average
values $\frac{1}{n}\sum^{n}_{j=1}(A_{ij}x_{ij}-b_{ij})$. can be estimated by
$y_{ij}$ for all $i\in\bm{n}$. In addition, the term
$-\sum_{kj\in\mathcal{N}^{c}_{ij}}(x_{ij}-x_{kj})$ in the dynamics of $x_{ij}$
is introduced to achieve the column consensus (4), and the term
$A_{ij}y_{ij}-\sum_{kj\in\mathcal{N}^{c}_{ij}}(z_{ij}-z_{kj})$ in the dynamics
of $x_{ij}$ and $z_{ij}$ are used to guarantee that (5) is satisfied.

Define
$\bar{x}_{i}=\text{col}(x_{i1},\ldots,x_{in}),\bar{\xi}_{i}=\text{col}(\xi_{i1},\ldots,\xi_{in}),\bar{y}_{i}=\text{col}(y_{i1},\ldots,y_{in}),\bar{z}_{i}=\text{col}(z_{i1},\ldots,z_{in})\in\mathbb{R}^{n}$.
Let $\bar{A}_{i}=\text{diag}\\{A_{i1},\ldots,A_{in}\\}\in\mathbb{R}^{n\times
n}$, and $L_{\mathcal{G}^{R}_{i}}\in\mathbb{R}^{n\times n}$ is the Laplacian
matrix of the graph $\mathcal{G}^{R}_{i}$. Then, for each $i\in\bm{m}$, the
algorithm (6) can be written in the following compact form

$\displaystyle\begin{cases}\dot{\bar{x}}_{i}=-(\bar{A}_{i}\bar{y}_{i}-\bar{\psi}_{i})-\bar{\phi}_{i},\\\
\dot{\bar{y}}_{i}=-(L_{\mathcal{G}^{R}_{i}}+\bar{A}_{i}\bar{A}^{T}_{i})\bar{y}_{i}+\bar{A}_{i}\bar{\psi}_{i}-\bar{A}_{i}\bar{\phi}_{i},\\\
\dot{\bar{z}}_{i}=\bar{A}_{i}\bar{y}_{i}-\bar{\psi}_{i},\end{cases}$ (7)

where $\bar{\psi}_{i}=\text{col}(\psi_{i1},\ldots,\psi_{in})\in\mathbb{R}^{n}$
with $\psi_{ij}=\sum_{kj\in\mathcal{N}^{c}_{ij}}(z_{ij}$ $-z_{kj})$,
$\bar{\phi}_{i}=\text{col}(\phi_{i1},\ldots,\phi_{in})\in\mathbb{R}^{n}$ with
$\phi_{ij}=\sum_{kj\in\mathcal{N}^{c}_{ij}}(x_{ij}$
$-x_{kj}),i\in\bm{m},j\in\bm{n}$. According to the definition of the Laplacian
matrix $L_{\mathcal{G}^{c}_{j}}\in\mathbb{R}^{m\times m}$ of
$\mathcal{G}^{c}_{j}$, one can derive that

$\displaystyle\begin{bmatrix}\psi_{1j}\\\ \psi_{2j}\\\ \ldots\\\
\psi_{mj}\end{bmatrix}=L_{\mathcal{G}^{c}_{j}}\begin{bmatrix}z_{1j}\\\
z_{2j}\\\ \ldots\\\ z_{mj}\end{bmatrix},\begin{bmatrix}\phi_{1j}\\\
\phi_{2j}\\\ \ldots\\\
\phi_{mj}\end{bmatrix}=L_{\mathcal{G}^{c}_{j}}\begin{bmatrix}x_{1j}\\\
x_{2j}\\\ \ldots\\\ x_{mj}\end{bmatrix}.$ (8)

Define
$\hat{x}=\text{col}(\bar{x}_{1},\ldots,\bar{x}_{m}),\hat{z}=\text{col}(\bar{z}_{1},\ldots,\bar{z}_{m})\in\mathbb{R}^{mn},$
$\hat{\psi}=\text{col}(\bar{\psi}_{1},\ldots,\bar{\psi}_{m})\in\mathbb{R}^{mn}$
and $\phi=\text{col}(\bar{\phi}_{1},\ldots,\bar{\phi}_{m})\in\mathbb{R}^{mn}$.
Let $P\in\mathbb{R}^{mn\times mn}$ be a row permutation matrix with
$P^{T}P=I_{mn\times mn}$ such that

$\displaystyle
P\hat{x}=\text{col}(x_{11},x_{21},\ldots,x_{m1},\ldots,x_{1n},x_{2n},\ldots,x_{mn}).$
(9)

It then from (8) and (9) that

$\displaystyle
P\hat{\psi}=\hat{L}_{c}P\hat{z},P\hat{\phi}=\hat{L}_{c}P\hat{x},$ (10)

with
$\hat{L}_{c}=\text{diag}(L_{\mathcal{G}^{c}_{1}},\ldots,L_{\mathcal{G}^{c}_{n}})\in\mathbb{R}^{mn\times
mn}$. Let $\hat{A}=\text{diag}(\bar{A}_{1}$
$,\ldots,\bar{A}_{m}),\hat{y}=\text{col}(\bar{y}_{1},\ldots,\bar{y}_{m}),\hat{L}_{R}=\text{diag}(L_{\mathcal{G}^{R}_{1}},$
$\ldots,L_{\mathcal{G}^{R}_{m}})$ and $\tilde{L}_{c}=P^{T}\hat{L}_{c}P$. It
then follows that (7) can be written as

$\displaystyle\begin{cases}\dot{\hat{x}}=-(\hat{A}\hat{y}-\tilde{L}_{c}\hat{z})-\tilde{L}_{c}\hat{x},\\\
\dot{\hat{y}}=-(\hat{L}_{R}+\hat{A}\hat{A})\hat{y}+\hat{A}\tilde{L}_{c}(\hat{z}-\hat{x}),\\\
\dot{\hat{z}}=\hat{A}\hat{y}-\tilde{L}_{c}\hat{z},\end{cases}$ (11)

which is equivalent as

$\displaystyle\begin{bmatrix}\dot{\hat{x}}\\\ \dot{\hat{y}}\\\
\dot{\hat{z}}\end{bmatrix}=\begin{bmatrix}-\tilde{L}_{c}&-\hat{A}&\tilde{L}_{c}\\\
-\hat{A}\tilde{L}_{c}&-(\hat{L}_{R}+\hat{A}\hat{A})&\hat{A}\tilde{L}_{c}\\\
0&\hat{A}&-\hat{A}\tilde{L}_{c}\end{bmatrix}\begin{bmatrix}\hat{x}\\\
\hat{y}\\\ \hat{z}\end{bmatrix}.$ (12)

To analyze the convergence of system (12), we provide the following Lemma to
characterize the eigenvalues of the system matrix of (12).

######  Lemma 2.

Let

$\displaystyle M=\begin{bmatrix}-L_{1}&-Y&L_{1}\\\
-Y^{T}L_{1}&-Y^{T}Y-L_{2}&Y^{T}L_{1}\\\ 0&Y&-L_{1}\end{bmatrix}$ (13)

where $L_{1},L_{2},Y$ are real and positive semi-definite, $Y$ is a real
matrix with appropriate dimension. Then, we can obtain that

(i) any non-zero eigenvalues of $M$ has negative real part.

(ii) zero eigenvalue must be non-defective, that is, its algebraic
multiplicity is equal to its geometric multiplicity.

The proof of Lemma 2 can be seen in Appendix A. Based on Lemma 2, the
convergence result of the system (12) is given in the following theorem and
its proof can be seen in Appendix B.

######  Theorem 1.

Suppose that Assumption 1 holds and the initial value of
$\xi_{ij},i\in\bm{m},j\in\bm{n}$ selected to be zero. The proposed distributed
algorithm (6) guarantees that all the agents’ state
$x_{ij}(t),i\in\bm{m},j\in\bm{n}$ converge exponentially to a constant value
$x^{*}_{ij}$ satisfying (4) and (5), which collaboratively forms a least
square solution $x^{*}$ of equation (1). Moreover, $x^{*}$ is an exact
solution of (1) if and only if $\lim_{t\to\infty}y_{ij}(t)=0$.

######  Remark 1.

Note that the distributed algorithms in [23] can be only applied to the
determined linear equation with an exact solution and cannot be used to the
over-determined linear equation. In contrast, we propose a new distributed
algorithm to obtain a least square solution of determined linear equation.
Compared with the results in [23], the main technical difficulties are given
as follows: (1) in general, seeking a least square solution is more complex
than an exact solution. To achieve a least square solution in a distributed
manner, we utilize the dynamic average consensus approach to estimate the sum
term $\frac{1}{n}\sum^{n}_{j=1}(A_{ij}x_{ij}-b_{ij})$ through the variable
$y_{ij}$. (2) Since one extra variable is introduced, the system matrix of the
proposed algorithm (6) is three-by-three block matrices rather than two-by-two
block matrices in [23]. This leads to that the eigenvalue analysis of the
proposed algorithm (6) is more difficult. To deal with this issue, we provide
a detailed eigenvalue analysis for more general block matrices shown in Lemma
2, which is crucial to show the exponential convergence of the proposed
algorithm.

######  Remark 2.

For the problem of solving linear equation $Ax=b$, the distributed algorithms
in [12, 13, 14, 15, 16, 17, 18, 19, 20, 21] that requires complete rows or
columns for each agent are involved with vector operation rather than matrix
operation such that the computation complexity for each agent can be reduced.
In contrast with the existing algorithms given in [12, 13, 14, 15, 16, 17, 18,
19, 20, 21], we propose scalable distributed algorithm (6) only involving with
scalar operation for each agent rather than vector operation. Thus, the
computation, storage and communication burden of each agent can be reduced
effectively and can be applied to the large-scale linear equations.

###  III-B Simulation

In this section, some simulation examples are provided to verify the
effectiveness of the proposed algorithm (6) for solving $Ax=b$ under
homogenous partitions in (3), where $Ax=b$ is given as

$\displaystyle A=\begin{bmatrix}1&2&1\\\ 2&-1&-1\\\ 1&-2&4\\\
2&2&-2\end{bmatrix},b=\begin{bmatrix}3\\\ 2\\\ 1\\\ 2\end{bmatrix}.$ (14)

Since $\text{rank}(A)=3<\text{rank}(A,b)=4$, it follows that above linear
equation $Ax=b$ has no exact solution and its least square solution is given
as $x^{*}=(A^{T}A)^{-1}A^{T}b=[1.1310,0.4947,0.2992]^{T}$. From (3), one can
derive that $A_{ij}$ is the $ij$th entry of $A$. In addition, we choose
$b_{ij}=b_{i}$ if $j=i$ while $b_{ij}=0$ if $j\neq i$. We utilize the grid
multi-agent network $\mathcal{G}$ in Fig. 1 to solve collaboratively the
solution $x^{*}$. Let
$E_{1}(t)=\sum^{m}_{i=1}\sum^{n}_{j=1}\|x_{ij}(t)-x^{*}_{i}\|^{2},x^{*}=\text{col}(x^{*}_{1},\ldots,x^{*}_{n})$
be the total estimated error, and
$Y_{e}(t)=\sum^{m}_{i=1}\sum^{n}_{j=1}\|y_{ij}(t)\|^{2}$ is equal to
$\|\hat{y}(t)\|^{2}$. Fig. 2 shows that $E_{1}(t)$ converges exponentially
fast to zero. It is illustrated that all the states $x_{ij}(t)$ converge
exponentially to the constant value $x^{*}_{ij}$, which consists of the
solution $x^{*}=\text{col}(x^{*}_{i1},\ldots,x^{*}_{in})$. Fig. 2 also shows
that $Y_{e}(t)$ finally converges a non-zero value, which implies that
$\lim_{t\to\infty}\hat{y}(t)\neq 0$. Based on the results of Theorem 1, we can
verify that the obtained solution $x^{*}$ is not an exact solution of (14).

Figure 2: Evolutions of $E_{1}(t)$ and $Y_{e}(t)$ under algorithm (6)

##  IV Distributed algorithm design under heterogeneous partitions

In this section, we consider heterogeneous partitions of (1), which includes
two cases: Case 1 is that each complete row block of $A$ has different column
partitions, and Case 2 is that each complete column has different row
partitions. One example of these two partition cases is shown in Fig. 3.

Figure 3: Two heterogeneous partitions of matrix $A$: left graph illustrates
Case 1 and right graph illustrates Case 2

###  IV-A Heterogeneous partition of Case 1

We first consider Case 1, where $A$ is partitioned into $c$ complete column
blocks and each column block is partitioned into $c_{i}$ row subblocks, i.e.,

$\displaystyle
A=[A_{1},A_{2},\ldots,A_{c}],A_{i}=\text{col}(A_{i1},A_{i2},\ldots,A_{ic_{i}}),$
(15)

with $A_{i}\in\mathbb{R}^{m\times n_{i}},i\in\bm{c}$ and
$A_{ij}\in\mathbb{R}^{m_{ij}\times n_{i}},j\in\bm{c}_{i}$. It follows that

$\displaystyle\sum^{c}_{i=1}n_{i}=n,\sum^{c_{i}}_{j=1}m_{ij}=m,i\in\bm{c}.$
(16)

Accordingly, the vector $b$ is partitioned by

$\displaystyle
b=\sum^{c}_{i=1}b_{i},b_{i}=\text{col}(b_{i1},\ldots,b_{ic_{i}}),b_{ij}\in\mathbb{R}^{m_{ij}}.$

In this case, $b_{i}$ is chosen arbitrarily such that $b=\sum^{c}_{i=1}b_{i}$,
but $b_{ij}$ is derived from a partition of $b_{i}$.

Figure 4: Double-layered multi-agent network

Different from homogenous partition in (3) where single-layered grid multi-
agent network is introduced, we consider a double-layered multi-agent network
for heterogeneous partition, which is composed of $c$ clusters. Each cluster
$i\in\bm{c}$ is composed of $c_{i}$ agents labelled by
$i_{1},i_{2},\ldots,i_{c_{i}}$. Each cluster does not involve with any
computation, only collects and distributes all the agents information in the
same cluster. The communication of all the clusters
$\mathcal{V}=\\{1,2,\ldots,c\\}$ is described by the graph
$\mathbb{G}=\\{\mathcal{V},\mathcal{E}\\}$ with the edge set
$\mathcal{E}=\mathcal{V}\times\mathcal{V}$, and the neighbors of cluster $i$
is denoted by $\mathcal{N}_{i}=\\{j\in\mathcal{V}|(j,i)\in\mathcal{E}\\}$. The
communication among all the agents in the same cluster $i$ is described by the
graph $\mathbb{G}_{i}=\\{\mathcal{V}_{i},\mathcal{E}_{i}\\},i\in\bm{c}$, where
$\mathcal{V}_{i}=\\{i_{1},\ldots,i_{c_{i}}\\}$ is the node set and
$\mathcal{E}_{i}=\mathcal{V}_{i}\times\mathcal{V}_{i}$ is the edge set, and
the neighbors of agent $i_{j}$ in the cluster $i$ is denoted by
$\mathcal{N}_{ij}=\\{i_{k}\in\mathcal{V}_{i}|(i_{k},i_{j})\in\mathcal{E}_{i}\\}$.
Fig. 4 shows such a double-layered multi-agent network, which corresponds to
the example in left graph in Fig. 3.

######  Assumption 2.

The graph $\mathbb{G}$ is undirected and connected, and the graph
$\mathbb{G}_{i},i\in\bm{c}$ is undirected and connected.

Suppose that each agent $i_{j}$ in the cluster $i$ knows
$A_{ij}\in\mathbb{R}^{m_{ij}\times n_{i}}$ and $b_{ij}\in\mathbb{R}^{m_{ij}}$.
In this section, we aim to develop a distributed algorithm such that each
agent $i_{j}$’s state $x_{ij}\in\mathbb{R}^{n_{i}}$ exponentially converges to
a constant vector $x^{*}_{ij}$ satisfying that

(i) All $x^{*}_{ij}$ in the same cluster $i$ achieve a consensus
$x^{*}_{i},i\in\bm{c}$, i.e.,

$\displaystyle x_{i1}=x_{i2}=\ldots=x_{ic_{i}}=x^{*}_{i},i\in\bm{c}.$ (17)

(ii) The consensus value $x^{*}_{i}$ of all the clusters satisfy that

$\displaystyle A^{T}_{i}\sum^{c}_{i=1}(A_{i}x^{*}_{i}-b_{i})=0,\forall
i\in\bm{c}.$ (18)

Note that $\sum^{c}_{i=1}(A_{i}x^{*}_{i}-b_{i})=Ax^{*}-b$ with
$x^{*}=\text{col}(x^{*}_{1},\ldots,$ $x^{*}_{c})$ and it follows from (18)
that $A^{T}_{i}(Ax^{*}-b)=0,\forall i\in\bm{c}$, which implies that
$A^{T}(Ax^{*}-b)=0$. Thus, we have that $x^{*}_{ij}$ collaboratively forms a
least square solution of (1).

####  IV-A1 Distributed algorithm

To ensure that all the agents’ states $x_{ij}$ converge to $x^{*}_{ij}$
satisfying (17) and (18), we introduce two extra variables
$y_{ij}\in\mathbb{R}^{m_{ij}},z_{ij}\in\mathbb{R}^{n_{i}}$ for each agent
$i_{j},i\in\bm{c},j\in\bm{c}_{i}$. Then, a distributed algorithm for each
agent $i_{j}$ is developed as

$\displaystyle\begin{cases}\dot{x}_{ij}=-(A^{T}_{ij}y_{ij}-\sum_{i_{k}\in\mathcal{N}_{ij}}(z_{ij}-z_{ik}))\\\
~{}~{}~{}~{}~{}~{}~{}~{}-\sum_{i_{k}\in\mathcal{N}_{ij}}(x_{ij}-x_{ik})\\\
\dot{\xi}_{ij}=-\sum_{k\in\mathcal{N}_{i}}(y_{ij}-E_{ij}y_{k}),y_{ij}=\xi_{ij}\\\
~{}~{}~{}~{}~{}~{}~{}~{}+A_{ij}x_{ij}-b_{ij}\\\
\dot{z}_{ij}=A^{T}_{ij}y_{ij}-\sum_{i_{k}\in\mathcal{N}_{ij}}(z_{ij}-z_{ik})\end{cases}$
(19)

where $\xi_{ij}\in\mathbb{R}^{m_{ij}}$ is an intermediate variable and its
initial value is selected as zero, $E_{ij}\in\mathbb{R}^{m_{ij}\times m}$
denotes a row partition of the identity matrix $I_{m}$ with
$\text{col}(E_{i1},\ldots,E_{ic_{i}})=I_{m}$. In particular,
$E_{ij}\in\mathbb{R}^{m_{ij}\times m}$ is introduced such that
$\frac{1}{c}\sum^{c}_{i=1}(\bar{A}_{i}\bar{x}_{i}-b_{i})$ can be estimated by
the average consensus approach, where
$\bar{A}_{i}=\text{diag}(A_{i1},\ldots,A_{ic_{i}})\in\mathbb{R}^{m\times
n_{i}c_{i}}$ and
$\bar{x}_{i}=\text{col}(x_{i1},\ldots,x_{ic_{i}})\in\mathbb{R}^{n_{i}c_{i}}$.

Define
$\bar{y}_{i}=\text{col}(y_{i1},\ldots,y_{ic_{i}})\in\mathbb{R}^{m},\bar{z}_{i}=\text{col}(z_{i1},\ldots,$
$z_{ic_{i}})\in\mathbb{R}^{n_{i}c_{i}}$,
$\bar{L}_{G_{i}}=L_{\mathbb{G}_{i}}\otimes I_{n_{i}}$ and
$L_{\mathbb{\mathbb{G}}_{i}}\in\mathbb{R}^{c_{i}\times c_{i}}$ is the
Laplacian matrix of the graph $\mathbb{G}_{i}$. Then, the algorithm (19) is
written as

$\displaystyle\begin{cases}\dot{\bar{x}}_{i}=-\bar{A}^{T}_{i}\bar{y}_{i}+\bar{L}_{\mathbb{G}_{i}}(\bar{z}_{i}-\bar{x}_{i})\\\
\dot{\bar{y}}_{i}=-\sum_{k\in\mathcal{N}_{i}}(\bar{y}_{i}-\bar{y}_{k})+\bar{A}_{i}\dot{\bar{x}}_{i}\\\
\dot{\bar{z}}_{i}=\bar{A}^{T}_{i}\bar{y}_{i}-\bar{L}_{\mathbb{G}_{i}}\bar{z}_{i}\end{cases}$
(20)

Let $\hat{x}=\text{col}(\bar{x}_{1},\ldots,\bar{x}_{c})$,
$\hat{y}=\text{col}(\bar{y}_{1},\ldots,\bar{y}_{c})$,
$\hat{z}=\text{col}(\bar{z}_{1},$ $\ldots,\bar{z}_{c})$,
$\hat{A}=\text{diag}(\bar{A}_{1},\ldots,\bar{A}_{c})$,
$\hat{L}=\text{diag}(\bar{L}_{\mathbb{G}_{1}},\ldots,\bar{L}_{\mathbb{G}_{c}})$,
$\hat{L}_{\mathbb{G}}=L_{\mathbb{G}}\otimes I_{n}$ and
$L_{\mathbb{G}}\in\mathbb{R}^{c\times c}$ is the Laplacian matrix of the graph
$\mathbb{G}$. The compact form of (20) in terms of $(\hat{x},\hat{y},\hat{z})$
is given as

$\displaystyle\begin{cases}\dot{\hat{x}}=-\hat{A}^{T}\hat{y}+\hat{L}\hat{z}-\hat{L}\hat{x},\\\
\dot{\hat{y}}=-(\hat{L}_{\mathbb{G}}+\hat{A}\hat{A}^{T})\hat{y}+\hat{A}\hat{L}(\hat{z}-\hat{x}),\\\
\dot{\hat{z}}=\hat{A}^{T}\hat{y}-\hat{L}\hat{z}.\end{cases}$ (21)

which is equivalent as

$\displaystyle\begin{bmatrix}\dot{\hat{x}}\\\ \dot{\hat{y}}\\\
\dot{\hat{z}}\end{bmatrix}=\begin{bmatrix}-\hat{L}_{\mathbb{G}}&-\hat{A}^{T}&\hat{L}_{\mathbb{G}}\\\
-\hat{A}\hat{L}_{\mathbb{G}}&-(\hat{L}+\hat{A}\hat{A}^{T})&\hat{A}\hat{L}_{\mathbb{G}}\\\
0&\hat{A}^{T}&-\hat{L}_{\mathbb{G}}\end{bmatrix}\begin{bmatrix}\hat{x}\\\
\hat{y}\\\ \hat{z}\end{bmatrix}.$ (22)

The following Theorem presents the convergence results of (22), and its proof
is given in Appendix C.

######  Theorem 2.

Suppose that Assumption 2 holds and the initial value of
$\xi_{ij},i\in\bm{c},j\in\bm{c}_{i}$ selected to be zero. The proposed
distributed algorithm (19) guarantees that all the agents’s states $x_{ij}(t)$
converge exponentially to a constant value $x^{*}_{ij}$ satisfying (17) and
(18), which collaboratively forms a least square solution $x^{*}$ of equation
(1). Moreover, $x^{*}$ is an exact solution of (1) if and only if
$\lim_{t\to\infty}\hat{y}(t)=0$.

###  IV-B Heterogeneous partition of Case 2

In this section, we consider the heterogeneous partition of Case 2, where $A$
is partitioned into $c$ complete row blocks and each row block is partitioned
into $c_{i}$ column subblocks, i.e.,

$\displaystyle
A=\text{col}(A_{1},A_{2},\ldots,A_{c}),A_{i}=[A_{i1},A_{i2},\ldots,A_{ic_{i}}],$
(23)

with $A_{i}\in\mathbb{R}^{m_{i}\times n}$ and
$A_{ij}\in\mathbb{R}^{m_{i}\times n_{ij}}$. Then, it follows that

$\displaystyle\sum^{c}_{i=1}m_{i}=m,\sum^{c_{i}}_{j=1}n_{ij}=n,i\in\bm{c}.$
(24)

Accordingly, the vector $b$ is partitioned by

$\displaystyle
b=\text{col}(b_{1},b_{2},\ldots,b_{c}),b_{i}=\sum^{c_{i}}_{j=1}b_{ij},b_{ij}\in\mathbb{R}^{m_{i}},$

In this case, $b_{i}$ results from a partition of $b$ and $b_{ij}$ is chosen
arbitrarily such that $b_{i}=\sum^{c_{i}}_{j=1}b_{ij}$.

Note that all the agents in the same cluster of Case 1 collectively know a
complete column block. In this section, we also employ the double-layered
multi-agent network $\mathbb{G}$ given in Fig. 4 while all the agents in the
same cluster collectively know the complete row block. For the heterogenous
partition of Case 2, suppose that each agent $i_{j}$ in the cluster $i$ knows
$A_{ij}\in\mathbb{R}^{m_{i}\times n_{ij}}$ and $b_{ij}\in\mathbb{R}^{m_{i}}$.
We aim to develop a distributed algorithm such that each agent $i_{j}$’s state
$x_{ij}\in\mathbb{R}^{n_{ij}}$ converges exponentially to a constant vector
$x^{*}_{ij}$ satisfying that

(i) All
$\bar{x}^{*}_{i}=\text{col}(x^{*}_{i1},x^{*}_{i2},\ldots,x^{*}_{ic_{i}})\in\mathbb{R}^{n}$
among all the clusters reach a consensus $x^{*}$, i.e.,

$\displaystyle\bar{x}^{*}_{1}=\bar{x}^{*}_{2}=\ldots=\bar{x}^{*}_{c}=x^{*}.$
(25)

(ii) The consensus value $x^{*}$ satisfies that

$\displaystyle\sum^{c}_{i=1}A^{T}_{i}(A_{i}x^{*}-b_{i})=0$ (26)

Note from (26) that $A^{T}(Ax^{*}-b)=0$, and we get that $x^{*}_{ij}$
collaboratively forms a least square solution of (1).

####  IV-B1 Distributed algorithm

To ensure that all the agents’ states $x_{ij}$ converge to $x^{*}_{ij}$
satisfying (25) and (26), we develop a distributed algorithm for each agent
$i_{j}$ is given as

$\displaystyle\begin{cases}\dot{x}_{ij}=-(c_{i}A^{T}_{ij}y_{ij}-\sum_{k\in\mathcal{N}_{i}}(z_{ij}-E_{ij}z_{k}))\\\
~{}~{}~{}~{}~{}~{}~{}~{}-\sum_{k\in\mathcal{N}_{i}}(x_{ij}-E_{ij}x_{k}),\\\
\dot{\xi}_{ij}=-\sum_{i_{k}\in\mathcal{N}_{ij}}(y_{ij}-y_{ik}),y_{ij}=\xi_{ij}+\\\
~{}~{}~{}~{}~{}~{}~{}~{}~{}(A_{ij}x_{ij}-b_{ij}),\\\
\dot{z}_{ij}=c_{i}A^{T}_{ij}y_{ij}-\sum_{k\in\mathcal{N}_{i}}(z_{ij}-E_{ij}z_{k}),\end{cases}$
(27)

where the second equation of (27) aims to estimate the average values
$\frac{1}{c_{i}}\sum^{c_{i}}_{j=1}(A_{ij}x_{ij}(t)-b_{ij})$, and
$E_{ij}\in\mathbb{R}^{n_{ij}\times n}$ denotes denotes a row partition of the
identity matrix $I_{n}$ such that
$\text{col}(E_{i1},E_{i2},\ldots,E_{ic_{i}})=I_{n}$. Let
$\bar{x}_{i}=\text{col}(x_{i1},\ldots,x_{ic_{i}})\in\mathbb{R}^{n},\bar{y}_{i}=\text{col}(y_{i1},\ldots,y_{ic_{i}})\in\mathbb{R}^{m_{i}c_{i}},\bar{z}_{i}=\text{col}(z_{i1},\ldots,z_{ic_{i}})\in\mathbb{R}^{n},\bar{A}_{i}=\text{diag}(A_{i1},\ldots,A_{ic_{i}})\in\mathbb{R}^{m_{i}c_{i}\times
n}$, $\bar{L}_{G_{i}}=L_{\mathbb{G}_{i}}\otimes
I_{m_{i}}\in\mathbb{R}^{m_{i}c_{i}\times m_{i}c_{i}}$ and
$L_{\mathbb{\mathbb{G}}_{i}}\in\mathbb{R}^{c_{i}\times c_{i}}$ is the
Laplacian matrix of the graph $\mathbb{G}_{i}$. Then, the algorithm (27) is
written as

$\displaystyle\begin{cases}\dot{\bar{x}}_{i}=-c_{i}\bar{A}^{T}_{i}\bar{y}_{i}+\sum_{k\in\mathcal{N}_{i}}(\bar{z}_{i}-\bar{z}_{k}-(\bar{x}_{i}-\bar{x}_{k}))\\\
\dot{\bar{y}}_{i}=-\bar{L}_{\mathbb{G}_{i}}\bar{y}_{i}+\bar{A}_{i}\dot{\bar{x}}_{i}\\\
\dot{\bar{z}}_{i}=c_{i}\bar{A}^{T}_{i}\bar{y}_{i}-\sum_{k\in\mathcal{N}_{i}}(\bar{z}_{i}-\bar{z}_{k})\end{cases}$
(28)

Let $\hat{x}=\text{col}(\bar{x}_{1},\ldots,\bar{x}_{c})$,
$\hat{y}=\text{col}(\bar{y}_{1},\ldots,\bar{y}_{c})$,
$\hat{z}=\text{col}(\bar{z}_{1},$ $\ldots,\bar{z}_{c})$,
$\Gamma=\text{diag}(c_{1}I_{n},\ldots,c_{c}I_{n})$,
$\hat{A}=\text{diag}(\bar{A}_{1},\ldots,\bar{A}_{c})$,
$\hat{L}=\text{diag}(\bar{L}_{\mathbb{G}_{1}},\ldots,\bar{L}_{\mathbb{G}_{c}})$,
$\hat{L}_{\mathbb{G}}=L_{\mathbb{G}}\otimes I_{n}$ and
$L_{\mathbb{G}}\in\mathbb{R}^{c\times c}$ is the Laplacian matrix of the graph
$\mathbb{G}$. A compact of (28) in terms of $(\hat{x},\hat{y},\hat{z})$ is
given as

$\displaystyle\begin{cases}\dot{\hat{x}}=-\Gamma\hat{A}^{T}\hat{y}+\hat{L}_{\mathbb{G}}\hat{z}-\hat{L}_{\mathbb{G}}\hat{x},\\\
\dot{\hat{y}}=-(\hat{L}+\hat{A}\Gamma\hat{A}^{T})\hat{y}+\hat{A}\hat{L}_{\mathbb{G}}(\hat{z}-\hat{x}),\\\
\dot{\hat{z}}=\Gamma\hat{A}^{T}\hat{y}-\hat{L}_{\mathbb{G}}\hat{z}.\end{cases}$
(29)

which is equivalent as

$\displaystyle\begin{bmatrix}\dot{\hat{x}}\\\ \dot{\hat{y}}\\\
\dot{\hat{z}}\end{bmatrix}=\begin{bmatrix}-\hat{L}_{\mathbb{G}}&-\Gamma\hat{A}^{T}&\hat{L}_{\mathbb{G}}\\\
-\hat{A}\hat{L}_{\mathbb{G}}&-(\hat{L}+\hat{A}\Gamma\hat{A}^{T})&\hat{A}\hat{L}_{\mathbb{G}}\\\
0&\Gamma\hat{A}&-\hat{L}_{\mathbb{G}}\end{bmatrix}\begin{bmatrix}\hat{x}\\\
\hat{y}\\\ \hat{z}\end{bmatrix}.$ (30)

Since $\Gamma$ is added in the system (30), the results of Lemma 2 cannot be
used directly. The following Lemma shows the eigenvalues of the system matrix
of (30), and its proof is given in Appendix D.

######  Lemma 3.

All the non-zero eigenvalues of system matrix of (30) have negative real part,
and its zero eigenvalue must be non-defective.

Based on the result of Lemma 3, the converge analysis of system (30) is given
in the following theorem, and its proof is given in Appendix E.

######  Theorem 3.

Suppose that Assumption 2 holds and the initial value of $\xi_{ij}$ selected
to be zero. The proposed distributed algorithm (27) guarantees that all the
agents’s states $x_{ij}(t)$ converge exponentially to a constant value
$x^{*}_{ij}$ satisfying (25) and (26), which collaboratively forms a least
square solution $x^{*}$ of equation (1). Moreover, $x^{*}$ is an exact
solution of (1) if and only if $\lim_{t\to\infty}\hat{y}(t)=0$.

######  Remark 3.

From the compact form (12), (22) and (30) of the proposed three distributed
algorithms (6), (19) and (27) , we observe that the algorithm (6) has same
system structure as (19), but the algorithm (27) has different system
structure with the others. The main reason is that the number of agents
$c_{i}$ in the cluster $i$ is involved in (27) but is not contained in the
other algorithms. In fact, when $c_{i}$ is same for all $i\in\bm{c}$, this
parameter $c_{i}$ can be removed in (27), which also implies that the
algorithm (6) can be regarded a special case of the algorithm (27).

######  Remark 4.

Different from consensus-based distributed algorithms in [12, 13, 14, 15]
where all the agents’ states have same dimension as the unknown variables, the
proposed distributed algorithms (19) and (27) allow all the agents’ states to
have different dimensions that are much smaller than that of the unknown
variables to be solved. This implies that the proposed algorithms (19) and
(27) can be applied for heterogeneous agents with different storage and
computation capability. In particular, when the number of the cluster and the
number of the agents are sufficiently large, all the agents states are
scalars, which is equivalent to the algorithm (6).

###  IV-C Simulation

In this section, we show the effectiveness of the proposed algorithms (19) and
(27) by solving the linear equation $Ax=b$ in (14). Firstly, we consider the
heterogeneous partition of Case 1 with
$A_{11}=1,A_{12}=[2,1]^{T},A_{13}=2,A_{21}=[2,-1]^{T},A_{22}=[-2,2]^{T},A_{31}=[1,-1]^{T},A_{32}=4,A_{33}=-3$.
In addition, $b_{1}=b,b_{2}=0_{4\times 1},b_{3}=0_{4\times 1}$ is chosen such
that $b=\sum^{3}_{i=1}b_{i}$, and $b_{ij}$ derives from a partition of
$b_{i}$. We utilize the double-layered multi-agent network $\mathbb{G}$ in
Fig. 4 to verify the distributed algorithm (19). Define
$E_{2}(t)=\sum^{c}_{i=1}\sum^{c_{i}}_{j=1}\|x_{ij}(t)-x^{*}_{i}\|^{2},x^{*}=\text{col}(x^{*}_{1},\ldots,x^{*}_{c})$
be the total estimated error and
$Y_{e}(t)=\sum^{c}_{i=1}\sum^{c_{i}}_{j=1}\|y_{ij}(t)\|^{2}$. Fig. 5 shows
that $E_{2}(t)$ converges exponentially fast to zero, which implies that all
the states $x_{ij}(t)$ converge to the constant value $x^{*}_{i}$ as the $i$th
sub-block of $x^{*}$. Fig. 5 also shows that $Y(t)$ converges a nonzero value,
which implies that $\lim_{t\to\infty}\hat{y}(t)\neq 0$ and verifies that the
solution $x^{*}$ is not an exact solution of (14).

Figure 5: Evolutions of $E_{2}(t)$ and $Y_{e}(t)$ under algorithm (19)

We further consider the heterogeneous partition of Case 2 with
$A_{11}=[1,2]^{T},A_{12}=[2,-1]^{T},A_{13}=[1,-1]^{T},A_{21}=[1,-2],A_{22}=4,A_{31}=2,A_{32}=2,A_{33}=-2$.
In addition, $b_{i},i=1,2,3$ is derived from a partition of $b$.
$b_{11}=b_{1},b_{22}=b_{2},b_{33}=b_{3}$ are chosen and the others $b_{ij}$
are zeros such that $b_{i}=\sum^{c_{i}}_{j=1}b_{ij}$. The double-layered
multi-agent network $\mathbb{G}$ in Fig. 4 is also utilized to demonstrate the
distributed algorithm (27). Define
$E_{3}(t)=\sum^{c}_{i=1}\|\bar{x}_{i}(t)-x^{*}\|^{2},\bar{x}_{i}=\text{col}(x_{i1},\ldots,x_{ic_{i}})$
and $Y_{e}(t)=\sum^{c}_{i=1}\sum^{c_{i}}_{j=1}\|y_{ij}(t)\|^{2}$. Fig. 6 shows
that $E_{3}(t)$ converges exponentially fast to zero, which implies that all
the states $x_{ij}(t)$ converge to the constant value $x^{*}_{ij}$, and
consists of a solution $x^{*}=\text{col}(x^{*}_{i1},\ldots,x^{*}_{ic_{i}})$.
Fig. 6 also shows that $Y_{e}(t)$ finally converges a non-zero value, which
verifies that $x^{*}$ is not exact solution of (1).

Figure 6: Evolutions of $E_{1}(t)$ and $Y_{e}(t)$ under algorithm (27)

##  V Conclusion

This paper proposes three kinds of distributed algorithms via multi-agent
networks to achieve a least square solution of linear equation under different
partition structures. In particular, each agent has only access to a small
block of linear equations, and only needs to control three scalar states when
the linear equation is partitioned as small as possible. These advantages can
be utilized to reduce the burdens of computation, storage and communication
for solving the large-scale equations. Future works includes extending the
proposed distributed algorithm to the time-varying network or a general
directed graph.

##  Appendix A Proof of Lemma 2

Firstly, we prove the result of (i). Let $\lambda_{m}\in\mathbb{C}$ denote any
eigenvalue of $M$, there exists a non-zero eigenvector
$u=\text{col}(u_{1},u_{2},u_{3})$ in the complex vector space such that

$\displaystyle\begin{bmatrix}-L_{1}&-Y&L_{1}\\\
-Y^{T}L_{1}&-Y^{T}Y-L_{2}&Y^{T}L_{1}\\\
0&Y&-L_{1}\end{bmatrix}\begin{bmatrix}u_{1}\\\ u_{2}\\\
u_{3}\end{bmatrix}=\lambda_{m}\begin{bmatrix}u_{1}\\\ u_{2}\\\
u_{3}\end{bmatrix}.$ (31)

We then have that

$\displaystyle-L_{1}u_{1}=\lambda_{m}(u_{1}+u_{3}),$ (32a) $\displaystyle-
L_{2}u_{2}=\lambda_{m}(-Y^{T}u_{1}+u_{2}),$ (32b) $\displaystyle-
L_{1}u_{3}=\lambda_{m}u_{3}-Yu_{2}.$ (32c)

Since $u$ belongs to the complex vector space, its conjugate transpose $u^{H}$
is introduced. Note that $Y^{T}=Y^{H}$ since $Y$ is a real matrix. By left
multiplying $u^{H}_{2}$ of (32b), one can derive that

$\displaystyle-u^{H}_{2}L_{2}u_{2}=-\lambda_{m}u^{H}_{2}Y^{H}u_{1}+\lambda_{m}u^{H}_{2}u_{2}.$
(33)

Substituting (32c) and (32a) into (33), it follows that

$\displaystyle-u^{H}_{2}L_{2}u_{2}$
$\displaystyle=-\lambda_{m}(\lambda_{m}u_{3}+L_{1}u_{3})^{H}u_{1}+\lambda_{m}u^{H}_{2}u_{2}$
$\displaystyle=-\lambda_{m}u^{H}_{3}L_{1}u_{1}-\lambda_{m}\lambda^{H}_{m}u^{H}_{3}u_{1}+\lambda_{m}u^{H}_{2}u_{2}$
$\displaystyle=\lambda^{2}_{m}(u_{1}+u_{3})^{H}(u_{1}+u_{3})-\lambda^{2}_{m}u^{H}_{1}(u_{1}+u_{3})$
$\displaystyle~{}~{}~{}-\lambda_{m}\lambda^{H}_{m}u^{H}_{3}u_{1}+\lambda_{m}u^{H}_{2}u_{2}.$
(34)

In addition, by using (32a) again, one can derive that

$\displaystyle-\lambda^{2}_{m}u^{H}_{1}(u_{1}+u_{3})=\lambda_{m}u^{H}_{1}L_{1}u_{1},$
(35a)
$\displaystyle-\lambda_{m}\lambda^{H}_{m}u^{H}_{3}u_{1}=\lambda_{m}u^{H}_{1}L_{1}u_{1}+\lambda_{m}\lambda^{H}_{m}u^{H}_{1}u_{1}.$
(35b)

Substituting (35) into (A), we have that

$\displaystyle\lambda^{2}_{m}(u_{1}$
$\displaystyle+u_{3})^{H}(u_{1}+u_{3})+\lambda_{m}(2u^{H}_{1}L_{1}u_{1}$
$\displaystyle+u^{H}_{2}u_{2})+\lambda_{m}\lambda^{H}_{m}u^{H}_{1}u_{1}+u^{H}_{2}L_{2}u_{2}=0.$
(36)

Define
$a=(u_{1}+u_{3})^{H}(u_{1}+u_{3}),b=2u^{H}_{1}L_{1}u_{1}+u^{H}_{2}u_{2},c_{1}=u^{H}_{1}u_{1},c_{2}=u^{H}_{2}L_{2}u_{2}$.
We easily know that $a,b,c_{1},c_{2}$ are all nonnegative real numbers. Then,
equation (A) is simplified as

$\displaystyle
a\lambda^{2}_{m}+b\lambda_{m}+\lambda_{m}\lambda^{H}_{m}c_{1}+c_{2}=0.$ (37)

Let $\lambda_{m}=\beta_{1}+\beta_{2}\bm{i}$, where $\beta_{1},\beta_{2}$ are
the real part and imaginary part, and $\bm{i}$ is imaginary unit. Then, (37)
can be written as

$\displaystyle
a(\beta^{2}_{1}-\beta^{2}_{2})+\beta_{1}b+(\beta^{2}_{1}+\beta^{2}_{2})c_{1}+c_{2}=0,$
(38a) $\displaystyle 2a\beta_{1}\beta_{2}+\beta_{2}b=0.$ (38b)

For any non-zero eigenvalue $\lambda_{m}\neq 0$, the results of (i) is
equivalent to show $\beta_{1}<0$. To this end, we consider two cases:
$\beta_{2}=0$ for Case 1 and $\beta_{2}\neq 0$ for Case 2.

Case 1: by considering $\beta_{2}=0$, (38) is arranged as

$\displaystyle(a+c_{1})\beta^{2}_{1}+\beta_{1}b+c_{2}=0.$ (39)

(1) Firstly, we consider that $a+c_{1}=0$. It is obvious that $a=c_{1}=0$
since $a\geq 0,c_{1}\geq 0$. According to the expressions of $a,c$, we have
that $u_{1}=0,u_{3}=0$. This implies that $u_{2}\neq 0$ since $u\neq 0$, which
further derive $b>0$. Thus, it follows that $\beta_{1}=-\frac{c_{2}}{b}\leq
0$. Since $\lambda_{m}\neq 0$, we obtain that $\beta_{1}<0$.

(2) Secondly, we consider that $a+c_{1}\neq 0$. We first show $b>0$ by a a
contradiction argument. Note that if $b=0$, we have $u_{2}=0$ and $c_{2}=0$.
It follows from (39) that $\beta_{1}=0$, which induces a contradiction with
$\lambda_{m}=0$. Then, we have that $a+c>0,b>0$ and $c_{2}\geq 0$. According
to the quadratic function root formula, it follows that the nonzero real root
of (39) is always negative when $a+c>0,b>0$ and $c_{2}\geq 0$. This implies
that $\beta_{1}<0$.

Case 2: By considering $\beta_{2}\neq 0$, it follows from (38b) that

$\displaystyle 2a\beta_{1}+b=0.$ (40)

We first show that $a\neq 0$ by a contradiction argument. If $a=0$, it follows
from (40) that $b=0$. According to the expressions of $a,b$, we have that
$u_{1}+u_{3}=0$ and $u_{2}=0$. In addition, substituting $a=0,b=0,u_{2}=0$
into (38a), it follows that $(\beta^{2}_{1}+\beta^{2}_{2})c_{1}=0$. Since
$\beta^{2}_{1}+\beta^{2}_{2}\neq 0$, one can derive that $c_{1}=0$ and
$u_{1}=0$. This implies $u_{i}=0,i=1,2,3$, which induces a contradiction with
$u\neq 0$. Then, we get that $a>0$. It follows from (40) that
$\beta_{1}=-\frac{b}{2a}\leq 0$. Next, we show that $b>0$ by a contradiction
argument. If $b=0$, we have that $L_{1}u_{1}=0$. It follows from
$\eqref{A2.1}$ that $u_{1}+u_{3}=0$ since $\lambda_{m}\neq 0$, which induces a
contradiction with $a=(u_{1}+u_{3})^{H}(u_{1}+u_{3})\neq 0$. Since $b>0$, we
obtain that $\beta_{1}<0$.

Secondly, we prove the result of (ii). By contradiction, we suppose that zero
eigenvalue $\lambda_{m}=0$ of $M$ is defective, that is, its algebraic
multiplicity is strictly greater than its geometric multiplicity. Then there
exists a nonzero generalized eigenvector $v=\text{col}(v_{1},v_{2},v_{3})$
such that

$\displaystyle Mv=u,Mu=0.$ (41)

Note that $Mu=0$ corresponds to $\lambda_{m}=0$ in (31) and (32), and then we
get that

$\displaystyle L_{1}u_{1}=0,L_{2}u_{2}=0,L_{1}u_{3}=Yu_{2}.$ (42)

In addition, it follows from $Mv=u$ that

$\displaystyle-L_{1}v_{1}-Yv_{2}+L_{1}v_{3}=u_{1},$ (43a)
$\displaystyle-Y^{T}L_{1}v_{1}-(Y^{T}Y+L_{2})v_{2}+Y^{T}L_{1}v_{3}=u_{2},$
(43b) $\displaystyle Yv_{2}-L_{1}v_{3}=u_{3}.$ (43c)

From (43a) and (43c), it follows that $-L_{1}v_{1}=u_{1}+u_{3}$. By
substituting $-L_{1}v_{1}=u_{1}+u_{3}$ and (43c) into (43b) yields

$\displaystyle Y^{T}u_{1}-L_{2}v_{2}=u_{2}.$ (44)

From $Yu_{2}=L_{1}u_{3}$ and $L_{1}u_{1}=0$ in (42), we have that
$u^{H}_{1}Yu_{2}=u^{H}_{1}L_{1}u_{3}=0$. By left multiplying $u^{H}_{2}$ of
(44), one can derive that $u^{H}_{2}u_{2}=u^{H}_{2}Y^{H}u_{1}=0$. This implies
that $u_{2}=0$, and then we derive that $L_{1}u_{3}=Yu_{2}=0$. Based on the
facts that $-L_{1}v_{1}=u_{1}+u_{3}$, $L_{1}u_{3}=0$ and $L_{1}u_{1}=0$, we
get that $(u_{1}+u_{3})^{H}(u_{1}+u_{3})=0$. This implies that
$u_{1}+u_{3}=0$. In addition, by left multiplying $u^{H}_{3}$ of (43c), it
follows that $u^{H}_{3}Yv_{2}=u^{H}_{3}u_{3}$. Since $u_{1}=-u_{3}$ and
$u_{2}=0$, (44) is written as $Y^{T}u_{3}+L_{2}v_{2}=0$. By left multiplying
$v^{H}_{2}$, we have that

$\displaystyle
v^{H}_{2}Y^{H}u_{3}+v^{H}_{2}L_{2}v_{2}=u^{H}_{3}u_{3}+v^{H}_{2}L_{2}v_{2}=0.$
(45)

This implies that $u_{3}=0$ and $u_{1}=0$, which induces a contradiction with
$u\neq 0$. Thus, we can conclude that zero eigenvalue of $M$ is non-defective.

##  Appendix B Proof of Theorem 1

Since homogeneous partition (3) is regarded as a special case of heterogeneous
partition of Case 1 in Section IV when $c=n$ and $c_{i}=m$ for any
$i\in\bm{c}$. Thus, the proof of Theorem 1 is similar to that of Theorem 2,
which is given in Appendix C.

##  Appendix C Proof of Theorem 2

Firstly, we show that an equilibrium of system (22) exists and is represented
as $\tilde{\xi}^{*}=\text{col}(\tilde{x}^{*},\tilde{y}^{*},\tilde{z}^{*})$.
Based on Lemma 1, we have that there must exists a constant vector
$\eta\in\mathbb{R}^{n}$ such that $A^{T}(A\eta-b)=0$. By virtue of
heterogeneous partition of Case 1 in (15) and
$\eta=\text{col}(\eta_{1},\ldots,\eta_{c})$ with
$\eta_{i}\in\mathbb{R}^{n_{i}}$, one can further derive that

$\displaystyle A^{T}_{i}\sum^{c}_{i=1}(A_{i}\eta_{i}-b_{i})=0.$ (46)

Let
$\tilde{y}^{*}=\text{col}(\tilde{y}^{*}_{1},\ldots,\tilde{y}^{*}_{c})=1_{c}\otimes\frac{1}{c}(A\eta-b)$
and $\tilde{x}^{*}=\text{col}(\tilde{x}^{*}_{1},\ldots,\tilde{x}^{*}_{c})$
with $\tilde{x}^{*}_{i}=1_{c_{i}}\otimes\eta_{i},i\in\bm{c}$. Under Assumption
2, we have that $\bar{L}_{\mathbb{G}_{i}}\tilde{x}^{*}_{i}=0,i\in\bm{c}$. It
then follows that

$\displaystyle\hat{L}\tilde{x}^{*}=0,\hat{L}_{\mathbb{G}}\tilde{y}^{*}=0.$
(47)

From the chosen $\tilde{y}^{*}$, we have that
$\tilde{y}^{*}_{i}=\frac{1}{c}(A\eta-b)=\frac{1}{c}\sum^{c}_{i=1}(A_{i}\eta_{i}-b_{i})$,
and it follows from (46) that $A_{i}\tilde{y}^{*}_{i}=0$. By virtue of
partition in (15) and
$\tilde{y}^{*}_{i}=\text{col}(\tilde{y}^{*}_{i1},\ldots,\tilde{y}^{*}_{ic_{i}})$
with $\tilde{y}^{*}_{ij}\in\mathbb{R}^{m_{ij}}$, we get that
$\sum^{c_{i}}_{j=1}A_{ij}\tilde{y}_{ij}=0$, which can be written as

$\displaystyle(1^{T}_{c_{i}}\otimes
I_{m_{i}})\bar{A}^{T}_{i}\tilde{y}^{*}_{i}=0,\forall i\in\bm{c}.$ (48)

Under Assumption 2, one has that
$\text{Image}(\bar{L}_{\mathbb{G}_{i}})=\text{ker}(1^{T}_{c_{i}}\otimes
I_{m_{i}})$. Then, there exists a constant vector
$\tilde{z}^{*}_{i}\in\mathbb{R}^{m}$ such that

$\displaystyle\bar{A}^{T}_{i}\tilde{y}^{*}_{i}-\bar{L}_{\mathbb{G}_{i}}\tilde{z}^{*}_{i}=0,\forall
i\in\bm{c}.$ (49)

Define $\tilde{z}^{*}=\text{col}(\tilde{z}^{*}_{1},\ldots,\tilde{z}^{*}_{c})$,
and it follows that

$\displaystyle\hat{A}^{T}\tilde{y}^{*}-\hat{L}\tilde{z}^{*}=0.$ (50)

Based on (47) and (50), we have that
$\xi=\text{col}(\tilde{x}^{*},\tilde{y}^{*},\tilde{z})$ is an equilibrium of
system (22).

Secondly, we analyze the convergence of the system state
$(\hat{x}(t),\hat{y}(t),\hat{z}(t))$ with respect to the equilibrium
$\tilde{\xi}^{*}$. Let $\xi(t)=\text{col}(\hat{x}(t),\hat{y}(t),\hat{z}(t))$
and the error $e(t)=\xi(t)-\tilde{\xi}^{*}$. Denote the system matrix of (22)
as $Q$, and one has that

$\displaystyle\dot{e}(t)=Qe(t).$ (51)

From Lemma 2, we have that all the nonzero eigenvalues of $Q$ have negative
real parts and zero eigenvalue is nondefective. Thus, there exists a constant
vector $q\in\text{ker}(Q)$ such that $e(t)$ converges to $q$ with exponential
convergence rate [26]. Also, it follows that $\xi(t)$ converges exponentially
to a constant vector $\hat{\xi}^{*}$, which satisfies that

$\displaystyle\hat{\xi}^{*}=\tilde{\xi}^{*}+q,$ (52)

with $\hat{\xi}^{*}=\text{col}(\hat{x}^{*},\hat{y}^{*},\hat{z}^{*})$.

Finally, we only need to show that
$\hat{x}^{*}=\text{col}(\bar{x}^{*}_{1},\ldots,\bar{x}^{*}_{c})$ and
$\bar{x}^{*}_{i}=\text{col}(x^{*}_{i1},\ldots,x^{*}_{ic_{i}})$ satisfy (17)
and (18). From (52), one can derive that $\hat{\xi}^{*}$ is also an
equilibrium of (22). Based on (20), we get that

$\displaystyle\bar{A}^{T}_{i}\bar{y}^{*}_{i}-\bar{L}_{\mathbb{G}_{i}}\bar{z}^{*}_{i}+\bar{L}_{\mathbb{G}_{i}}\bar{x}^{*}_{i}=0,$
(53a)
$\displaystyle\sum_{k\in\mathcal{N}_{i}}(\bar{y}^{*}_{i}-\bar{y}^{*}_{k})=0,$
(53b)
$\displaystyle\bar{A}^{T}_{i}\bar{y}^{*}_{i}-\bar{L}_{\mathbb{G}_{i}}\bar{z}^{*}_{i}=0,$
(53c)

for any $i\in\bm{c}$. Under Assumption 2, from (53a) and (53c), one has that
$\bar{x}^{*}_{i}=1_{c_{i}}\otimes x^{*}_{i}$ with a constant vector
$x^{*}_{i}$, which implies that (17) is satisfied. In addition, from (53b), it
follows that $\bar{y}^{*}_{1}=\ldots=\bar{y}^{*}_{c}$. Moreover, with the
initial condition $\xi_{ij}(0)=0,i\in\bm{c},j\in\bm{c}_{i}$, one has that
$\bar{y}_{i}(0)=\bar{A}_{i}\bar{x}_{i}(0)-b_{i}$. Summing the second equation
(20) from $i=1$ to $c$ can yield
$\sum^{c}_{i=1}\dot{\bar{y}}_{i}(t)=\sum^{c}_{i=1}\bar{A}_{i}\dot{\bar{x}}_{i}$.
Integrating it from $t_{0}$ to $t$, under the condition
$\bar{y}_{i}(0)=\bar{A}_{i}\bar{x}_{i}(0)-b_{i}$, we have that
$\sum^{c}_{i=1}\bar{y}_{i}(t)=\sum^{c}_{i=1}(\bar{A}_{i}\bar{x}_{i}(t)-b_{i})$
always holds for $\forall t\geq 0$. Noting that
$\bar{y}^{*}_{1}=\ldots=\bar{y}^{*}_{c}$ and $\bar{x}^{*}_{i}=1_{c_{i}}\otimes
x^{*}_{i}$, one can derive that
$\bar{y}^{*}_{i}=\frac{1}{c}\sum^{c}_{i=1}(A_{i}x^{*}_{i}-b_{i}),\forall
i\in\bm{c}$. By left multiplying $1^{T}_{c_{i}}\otimes I_{n_{i}}$ of (53a), we
have that $(1^{T}_{c_{i}}\otimes
I_{n_{i}})\bar{A}^{T}_{i}\bar{y}^{*}_{i}=A^{T}_{i}\bar{y}^{*}_{i}=\frac{1}{c}A^{T}_{i}\sum^{c}_{i=1}(A_{i}x^{*}_{i}-b_{i})=\frac{1}{c}A^{T}_{i}(Ax^{*}-b)=0$.
This implies that (18) holds. Thus, we have shown that $x_{ij}(t)$ converge
exponentially to $x^{*}_{ij}$, which collaboratively forms a least square
solution of equation (1).

In addition, from above results, we have obtained that $\hat{y}(t)$ converges
exponentially to $\hat{y}^{*}=1_{c}\otimes\frac{1}{c}(Ax^{*}-b)$. It is clear
that $x^{*}$ is an exact solution of (1) if and only if $\hat{y}^{*}=0$. It is
indicated that the final convergence values of $y_{ij}(t)$ can be employed to
verify whether the obtained solution $x^{*}$ is an exact solution.

##  Appendix D Proof of Lemma 3

Denote the system matrix of system (30) as $Q$, and we first show that all the
non-zero eigenvalues $Q$ have negative real part. With the same eigenvalue and
eigenvector notion in the proof of Lemma 2, it follows from $Q$ that

$\displaystyle-\hat{L}_{\mathbb{G}}u_{1}=\lambda_{m}(u_{1}+u_{3}),$ (54a)
$\displaystyle-\hat{L}u_{2}=\lambda_{m}(-\hat{A}u_{1}+u_{2}),$ (54b)
$\displaystyle T\hat{A}^{T}u_{2}-\hat{L}_{\mathbb{G}}u_{3}=\lambda_{m}u_{3}.$
(54c)

Let
$u_{1}=\text{col}(\bar{u}_{1i},\ldots,\bar{u}_{1c}),u_{2}=\text{col}(\bar{u}_{2i},\ldots,\bar{u}_{2c})$
and $u_{3}=\text{col}(\bar{u}_{3i},\ldots,\bar{u}_{3c})$. From (54b) and
(54c), it follows that

$\displaystyle-\bar{L}_{\mathbb{G}_{i}}\bar{u}_{2i}=\lambda_{m}(-\bar{A}_{i}\bar{u}_{1i}+\bar{u}_{2i}),$
(55a) $\displaystyle
c_{i}\bar{A}^{T}_{i}\bar{u}_{2i}-\sum_{j\in\mathcal{N}_{i}}(\bar{u}_{3i}-\bar{u}_{3j})=\lambda_{m}\bar{u}_{3i},$
(55b)

with $i\in\bm{c}$. By left multiplying $\bar{u}^{T}_{2i}$ of (55a),
substituting (55b) into (55a) can yield

$\displaystyle-
c_{i}\bar{u}^{H}_{2i}\bar{L}_{\mathbb{G}_{i}}\bar{u}_{2i}=-\lambda_{m}c_{i}\bar{u}^{H}_{2i}\bar{A}_{i}\bar{u}_{1i}+\lambda_{m}c_{i}\bar{u}^{H}_{2i}\bar{u}_{2i}$
$\displaystyle=-\lambda_{m}(\sum_{j\in\mathcal{N}_{i}}(\bar{u}_{3i}-\bar{u}_{3j}))^{H}\bar{u}_{1i}-\lambda_{m}\lambda^{H}_{m}\bar{u}^{H}_{3i}\bar{u}_{1i}+\lambda_{m}c_{i}\bar{u}^{H}_{2i}\bar{u}_{2i}.$

By summing above equation from $i=1$ to $c$, it follows that

$\displaystyle-u^{H}_{2}\tilde{L}u_{2}=-\lambda_{m}u^{H}_{3}\hat{L}_{\mathbb{G}}u_{1}-\lambda_{m}\lambda^{H}_{m}u^{H}_{3}u_{1}+\lambda_{m}u^{T}_{2}\Xi
u_{2},$

with
$\tilde{L}=\text{diag}(c_{1}\bar{L}_{\mathbb{G}_{1}},\ldots,c_{c}\bar{L}_{\mathbb{G}_{c}})\geq
0$ and $\Xi=\text{diag}(c_{1}I_{c_{1}m_{1}},$ $\ldots,c_{c}I_{c_{c}m_{c}})>0$.
By using (54a) and (55b), we have that

$\displaystyle\lambda^{2}_{m}(u_{1}$
$\displaystyle+u_{3})^{H}(u_{1}+u_{3})+\lambda_{m}(2u^{H}_{1}\hat{L}_{\mathbb{G}}u_{1}+u^{H}_{2}\Xi
u_{2})$
$\displaystyle+\lambda_{m}\lambda^{H}_{m}u^{H}_{1}u_{1}+u^{H}_{2}\tilde{L}u_{2}=0.$
(56)

Note that (D) is almost same as (A). Thus, similar to the analyse of the Lemma
2, we easily get that all the nonzero eigenvalues of $Q$ have negative real
part.

Next, we show that $\lambda_{m}=0$ of $Q$ is defective. The proof process is
similar to that of Lemma 2 and here only some crucial steps are given. Similar
to Lemma 2, we have that $Mv=u$ and $Mu=0$. It follows from $Mu=0$ that
$\hat{L}_{G}u_{1}=0,\hat{L}u_{2}=0,T\hat{A}^{T}u_{2}=\hat{L}_{\mathbb{G}}u_{3}$.
In addition, from $Mv=u$, we have that

$\displaystyle-\hat{L}_{\mathbb{G}}v_{1}-T\hat{A}^{T}v_{2}+\hat{L}_{\mathbb{G}}v_{3}=u_{1},$
(57a)
$\displaystyle-\hat{A}\hat{L}_{\mathbb{G}}v_{1}-(\hat{A}T\hat{A}^{T}+\hat{L})v_{2}+\hat{A}\hat{L}_{\mathbb{G}}v_{3}=u_{2},$
(57b) $\displaystyle T\hat{A}^{T}v_{2}-\hat{L}_{\mathbb{G}}v_{3}=u_{3}.$ (57c)

From above (57), we get that $-\hat{L}_{\mathbb{G}}v_{1}=u_{1}+u_{3}$ and
$\hat{A}u_{1}-\hat{L}_{2}v_{2}=u_{2}$. This implies that
$c_{i}\bar{A}_{i}\bar{u}_{1i}-c_{i}\bar{L}_{\mathbb{G}_{i}}\bar{v}_{2i}=c_{i}\bar{u}_{2i},\forall
i\in\bm{c}$, which is arranged as

$\displaystyle\hat{A}Tu_{1}-\tilde{L}v_{2}=\Xi u_{2}.$ (58)

Since $\hat{L}u_{2}=0,T\hat{A}^{T}u_{2}=\hat{L}_{\mathbb{G}}u_{1}$ and
$T^{H}=T$, we have that $\tilde{L}u_{2}=0$ and $u^{H}_{1}T\hat{A}^{T}u_{2}=0$.
By left multiplying $u^{H}_{2}$ of (58), we have that $u^{H}_{2}\Xi u_{2}=0$,
which implies that $u_{2}=0$. Then, we also get that

$\displaystyle u_{1}=-u_{3},u^{H}_{3}u_{3}+v^{H}_{2}\tilde{L}v_{2}=0.$ (59)

This implies that $u_{1}=u_{3}=0$, which occurs a contradiction. Then we
conclude that $\lambda_{m}=0$ is defective.

##  Appendix E Proof of Theorem 3

The proof process of Theorem 3 is similar to that of Theorem 2, and only some
crucial steps are provided. Firstly, with the same notation in Theorem 2, we
show that there exists a constant vector
$\tilde{\xi}^{*}=\text{col}(\tilde{x}^{*},\tilde{y}^{*},\tilde{z}^{*})$ as an
equilibrium of system (30). Since there exists $\eta\in\mathbb{R}^{n}$
satisfying $A^{T}(A\eta-b)=0$, we choose that
$\tilde{x}^{*}=1^{T}_{c}\otimes\eta,\tilde{y}=\text{col}(\tilde{y}^{*}_{1},\ldots,\tilde{y}^{*}_{c})$
with $\tilde{y}^{*}_{i}=1^{T}_{c_{i}}\otimes\frac{1}{c_{i}}(A_{i}\eta-
b_{i}),i\in\bm{c}$. Under Assumption 2, it follows that

$\displaystyle\hat{L}_{\mathbb{G}}\tilde{x}^{*}=0,\hat{L}\tilde{y}^{*}=0.$
(60)

According to heterogeneous partition in (23) and the chosen $\tilde{y}^{*}$,
we have that $A^{T}(A\eta-b)=\sum^{c}_{i=1}A^{T}_{i}(A_{i}\eta-
b_{i})=\sum^{c}_{i=1}c_{i}\bar{A}^{T}_{i}\tilde{y}^{*}_{i}=0$, and the last
equation is written as

$\displaystyle(1^{T}_{c}\otimes I_{n})\Gamma\hat{A}^{T}\tilde{y}^{*}=0.$ (61)

Since $\text{ker}(1^{T}\otimes I_{n})=\text{Image}(\hat{L}_{\mathbb{G}})$,
then there exists a constant vector $\tilde{z}^{*}\in\mathbb{R}^{nc\times nc}$
such that

$\displaystyle\Gamma\hat{A}^{T}\tilde{y}^{*}-\hat{L}_{\mathbb{G}}\tilde{z}^{*}=0.$
(62)

From (60) and (60), one can derive that $\tilde{\xi}^{*}$ is an equilibrium of
system (30).

Similar to the proof of Theorem 2, we have that $\hat{\xi}(t)$ converges
exponentially fast to a constant vector
$\hat{\xi}^{*}=\text{col}(\hat{x}^{*},\hat{y}^{*},\hat{z}^{*})$ satisfying
that $\hat{\xi}^{*}=\tilde{\xi}^{*}+q$ with $q\in\text{ker}(Q)$. Next, we show
that $\hat{x}^{*}=\text{col}(\bar{x}^{*}_{1},\ldots,\bar{x}^{*}_{c})$
satisfies (25) and (26). Note that $\hat{\xi}^{*}$ is also an equilibrium of
(30), and it then follows that

$\displaystyle\sum_{k\in\mathcal{N}_{i}}(\bar{x}^{*}_{i}-\bar{x}^{*}_{k})=0,$
(63a) $\displaystyle\bar{L}_{\mathbb{G}_{i}}\bar{y}^{*}_{i}=0,$ (63b)
$\displaystyle
c_{i}\bar{A}^{T}_{i}\bar{y}^{*}_{i}-\sum_{k\in\mathcal{N}_{i}}(\bar{z}^{*}_{i}-\bar{z}^{*}_{k})=0.$
(63c)

for $i\in\bm{c}$. Under Assumption 2, it follows from (63a) that
$\bar{x}^{*}_{1}=\ldots=\bar{x}^{*}_{c}=x^{*}$ with a constant vector $x^{*}$,
which implies that (25) holds. In addition, from (63b), we get that
$y^{*}_{i1}=\ldots=y^{*}_{ic_{i}}$. Under the initial condition
$\xi_{ij}(0)=0$, similar to the analysis in Theorem 2, we have that
$\sum^{c_{i}}_{j=1}y_{ij}(t)=\sum^{c_{i}}_{j=1}(A_{ij}x_{ij}(t)-b_{ij})$
always holds for $\forall t\geq 0$, and one further derive that
$y^{*}_{ij}=\frac{1}{c_{i}}\sum^{c_{i}}_{j=1}(A_{ij}x^{*}_{ij}-b_{i})=\frac{1}{c_{i}}(A_{i}x^{*}-b_{i})$
and $\bar{y}^{*}_{i}=1_{c_{i}}\otimes\frac{1}{c_{i}}(A_{i}x^{*}-b_{i})$. From
(63c), one has that
$\sum^{c}_{i=1}c_{i}\bar{A}^{T}_{i}\bar{y}^{*}_{i}=\sum^{c}_{i=1}A^{T}_{i}(A_{i}x^{*}-b)=0$,
which implies that (26). Thus, we have shown that $x_{ij}(t)$ converge
exponentially to $x^{*}_{ij}$. In addition, we obtain that $\hat{y}(t)$
converges exponentially to
$\hat{y}^{*}=\text{col}(\bar{y}^{*}_{1},\ldots,\bar{y}^{*}_{c})$ with
$\bar{y}_{i}=1_{c_{i}}\otimes\frac{1}{c_{i}}(A_{i}x^{*}-b_{i}),i\in\bm{c}$.
Then we have that $x^{*}$ is an exact solution if and only if $\hat{y}^{*}=0$.

## References

  * [1] I. D. Schizas, G. Mateos, and G. B. Giannakis, “Distributed LMS for consensus-based in-network adaptive processing,” IEEE Trans. Signal Proces., vol. 57, no. 6, pp. 2365-2382, 2009.
  * [2] S. Choudhary, L. Carlone, C. Nieto, et al, “Distributed mapping with privacy and communication constraints: Lightweight algorithms and object-based models,” Int. J. Robot. Res., vol. 36, no. 12, pp. 1286-1311, 2017.
  * [3] B. Carpentieri, I. S. Duff, L. Giraud, and M. Magolu monga Made, “Sparse symmetric preconditioners for dense linear systems in electromagnetism,” Numer. Linear Algebra, vol. 11, pp. 753-771, 2004.
  * [4] D. Silvestre, J. Hespanha, and C. Silvestre, “A pagerank algorithm based on asynchronous Gauss-Seidel iterations,” IEEE Proc. American Control Conf., pp. 484-489, 2018.
  * [5] W. Hackbusch, “Iterative solution of large sparse systems of equations,” New York: Springer, 1994.
  * [6] P. Wang, S. Mou, J. Lian, and W. Ren, “Solving a system of linear equations: From centralized to distributed algorithms,” Annu. Rev. Control, vol. 47, pp. 306-322, 2019.
  * [7] S. Mou, J. Liu, and A. S. Morse, “A distributed algorithm for solving a linear algebraic equation,” IEEE Trans. Autom. Control, vol. 60, no. 11, pp. 2863-2878, 2015.
  * [8] J. Liu, A. S. Morse, A. Nedic, and T. Basar, “Exponential convergence of a distributed algorithm for solving linear algebraic equations,” Automatica, vol. 83, pp. 37-46, 2017.
  * [9] J. Liu, S. Mou, and A. S. Morse, “Asynchronous distributed algorithms for solving linear algebraic equations,” IEEE Trans. Autom. Control, vol. 63, no. 2, pp. 372-385, 2017.
  * [10] J. Lu, C. Y. Tang, “A distributed algorithm for solving positive definite linear equations over networks with membership dynamics,” IEEE Trans. Control Netw. Syst., vol. 5, no. 1, pp. 215-227, 2016.
  * [11] P. Wang, W. Ren, and Z. Duan, “Distributed algorithm to solve a system of linear equations with unique or multiple solutions from arbitrary initializations,” IEEE Trans. Control Netw. Syst., vol. 6, no. 1, pp. 82-93, 2018.
  * [12] B. D. O. Anderson, S. Mou, A. S. Morse, and U. Helmke, “Decentralized gradient algorithm for solution of a linear equation,” Numer. Algebra, Control Optim., vol. 6, no. 3, pp. 319-328, 2016.
  * [13] G. Shi, B. D. O. Anderson, and U. Helmke, “Network flows that solve linear equations,” IEEE Trans. Autom. Control, vol. 62, no. 6, pp. 2659-2674, 2017.
  * [14] J. Zhou, X. Wang, S. Mou, and B. D. O. Anderson, “Finite-time distributed linear equation solver for solutions with minimum $l_{1}$-norm,” IEEE Trans. Autom. Control, vol. 65, no. 4, pp. 1691-1696, 2019.
  * [15] X. Shi, X. Yu, J. Cao, and G. Wen, “Continuous distributed algorithms for solving linear equations in finite time,” Automatica, vol. 113, pp. 108755, 2020.
  * [16] Y. Liu, C. Lageman, B. D. O. Anderson, and G. Shi, “An Arrow-Hurwicz-Uzawa type flow as least squares solver for network linear equations,” Automatica, vol. 100, pp. 187-193, 2019.
  * [17] Y. Liu, Y. Lou, B. D. O. Anderson, and G. Shi, “Network flows that solve least squares for linear equations,” Automatica, vol. 120, pp. 109108, 2020.
  * [18] X. Zeng, and K. Cao, “Computation of linear algebraic equations with solvability verification over multi-agent networks,” Kybernetika, vol. 53, no. 5, pp. 803-819, 2017.
  * [19] J. Wang, and N. Elia, “Distributed least square with intermittent communications,” IEEE Proc. American Control Conf., pp. 6479-6484, 2012.
  * [20] X. Wang, J. Zhou, S. Mou, and M. J. Corless, “A distributed algorithm for least squares solutions,” IEEE Trans. Autom. Control, vol. 64, no. 10, pp. 4217-4222, 2019.
  * [21] T. Yang, J. George, J. Qin, et al, “Distributed least squares solver for network linear equations,” Automatica, vol. 113, pp. 108798, 2020.
  * [22] X. Wang, S. Mou, and B. D. O. Anderson, “A distributed algorithm with scalar states for solving linear equations,” Proc. IEEE Conf. Decis. Control, pp. 2861-2865, 2018.
  * [23] X. Wang, S. Mou, and B. D. O. Anderson, “Scalable, distributed algorithms for solving linear equations via double-layered networks,” IEEE Trans. Autom. Control, vol. 65, no. 3, pp. 1132-1143, 2019.
  * [24] R. A. Freeman, P. Yang, and K. M, Lynch, “Stability and convergence properties of dynamic average consensus estimators,” Proc. IEEE Conf. Decis. Control, pp. 338-343, 2006.
  * [25] S. S. Kia, B. V. Scoy, J. Cortes, et al, “Tutorial on dynamic average consensus: The problem, its applications, and the algorithms,” IEEE Trans. Control Syst. Mag., vol. 39, no. 3, pp. 40-72, 2019.
  * [26] H. L. Trentelman, A. A. Stoorvogel, and M. Hautus, “Control Theory for Linear Systems,” Springer Science and Business Media, 2012.


unique left Haar measure and of $G$. A similar statement holds for right Haar
measure.

Given a locally compact group $G$, and $\mu$ is a left Haar measure on $G$.
For every $x\in G$, recall that $\Delta_{G}:x\mapsto\mu_{x}/\mu$ is the
_modular function_ of $G$, where $\mu_{x}$ is a left Haar measure on $G$
defined by $\mu_{x}(A)=\mu(Ax)$, for every measurable set $A$. When the image
of $\Delta_{G}$ is always $1$, we say $G$ is _unimodular_. In general,
$\Delta_{G}(x)$ takes values in $\mathbb{R}^{>0}$. We use
$(\mathbb{R}^{>0},\times)$ to denote the multiplicative group of positive real
number together with the usual Euclidean topology. The next fact records some
basic properties of the modular function; See [9, Section 2.4].

######  Fact B.2.

Let $G$ be a locally compact group. Assuming $\mu$ is a left Haar measure and
$\nu$ is a right Haar measure.

  1. (1)

Suppose $H$ is a normal closed subgroup of $G$, then $\Delta_{H}=\Delta_{G}$.
In particular, if $H=\ker\Delta_{G}$, then $H$ is unimodular.

  2. (2)

The function $\Delta_{G}:G\to(\mathbb{R}^{>0},\times)$ is a continuous
homomorphism.

  3. (3)

For every $x\in G$ and every measurable set $A$, we have
$\mu(Ax)=\Delta_{G}(x)\mu(A)$, and $\nu(xA)=\Delta_{G}^{-1}(x)\nu(A)$.

  4. (4)

There is a constant $c$ such that
$\int_{G}f\,\mathrm{d}\mu=c\int_{G}f\Delta_{G}\,\mathrm{d}\nu$ for every $f\in
C_{c}(G)$.

We use the following integral formula [9, Theorem 2.49] in our proofs.

######  Fact B.3 (Quotient integral formula).

Let $G$ be a locally compact group, and let $H$ be a closed normal subgroup of
$G$. Given $\mu_{G}$, $\mu_{H}$ left Haar measures on $G$ and on $H$. Then
there is a unique left Haar measure $\mu_{G/H}$ on $G/H$, such that for every
$f\in C_{c}(G)$,

$\int_{G}f(x)\,\mathrm{d}\mu_{G}(x)=\int_{G/H}\int_{H}f(xh)\,\mathrm{d}\mu_{H}(h)\,\mathrm{d}\mu_{G/H}(x).$

The following fact is a consequence of a result about Haar measure on closed
subgroups and quotients [4, Proposition VII. 2.7.10].

######  Fact B.4.

Suppose $G$ is nonunimodular, and $\Delta_{G}:G\to(\mathbb{R}^{>0},\times)$ is
the modular function of $G$, then we have the following:

  1. (1)

If $K\vartriangleleft G$ is a compact normal subgroup of $G$, $\Delta_{G/K}$
is the modular function of $G/K$, and $\pi:G\to G/K$ is the quotient map, then
we have $\Delta_{G}=\Delta_{G/K}\circ\pi$.

  2. (2)

If $H\vartriangleleft G$ is a closed unimodular group, and $\mu_{H}$ is a Haar
measure on $H$. Suppose $G/H$ is unimodular, and $X$ is a compact subset of
$H$. Then for every $g\in G$, $\mu_{H}(gXg^{-1})=\Delta_{G}(g)\mu_{H}(X)$.

##  Appendix C Almost-Lie groups and the Gleason–Yamabe Theorem

In our proof we need the solution of Hilbert’s 5th problem, which is known as
the Gleason–Yamabe Theorem [11, 31], to reduce the problem into Lie groups.
For convenience, we introduce the following terminology. A locally compact
group $G$ is an almost-Lie group if every open neighborhood $U$ of the
identity in $G$ contains a compact $H\vartriangleleft G$ such that $G/H$ is a
Lie group.

######  Lemma C.1.

Suppose $G$ is an almost-Lie group. Then every open subgroup of $G$ and every
quotient of $G$ by a closed normal subgroup is an almost-Lie group.

###### Proof.

We first show that every open subgroup of $G$ is almost-Lie. Let $S$ be an
open subgroup of $G$, and $U$ is an open neighborhood of identity in $S$. We
need to find a compact subgroup $K$ of $S$ such that $K\subseteq U$ and $S/K$
is a Lie group. Since $U$ is also a neighborhood of identity in $G$, $U$
contains a compact normal subgroup $K$ of $G$ such that $G/K$ is a Lie group.
Note that $K\vartriangleleft S$. As $S$ is open, $S/K$ is open in $G/K$ and
hence a Lie group as desired.

Next, suppose $H$ is a closed normal subgroup of $G$, and $\pi:G\to G/H$ is
the quotient map. If $U$ is an open neighborhood of the identity in $G/H$,
then $\pi^{-1}(U)$ is an open neighborhood of identity in $G$. Hence, we can
get a normal compact subgroup $K$ of $G$ such that $K\subseteq\pi^{-1}(U)$ and
that $G/K$ is a Lie group. Then $\pi(K)$ is a compact subgroup of $U$. With
$S=\pi^{-1}(\pi(K))$, we have $\pi(K)=S/H$. Since $K$ is normal in $G$ we have
$\pi(K)$ is normal in $G/H$ and thus $S$ is normal in $G$. Whence by the third
isomorphism theorem (Fact A.1.3), we conclude that $(G/H)/\pi(K)\cong G/S$. By
the third isomorphism theorem again, we have $G/S\cong(G/K)/(S/K)$, thus $G/S$
is a Lie group. ∎

We use the following strong version of the Gleason–Yamabe Theorem.

######  Fact C.2.

We have the following:

  1. (1)

_(Gleason–Yamabe Theorem)_ Suppose $G$ is a locally compact group. Then there
is an open subgroup of $G$ which is an almost-Lie group.

  2. (2)

An almost-Lie group $G$ is a Lie group if and only if there is an open
neighborhood $U$ of the identity in $G$ that contains no nontrivial compact
subgroup of $G$.

Fact C.2.2 is not officially part of the Gleason–Yamabe Theorem. However, the
forward direction is an easy fact about the no small subgroup property of Lie
groups, and the and backward direction is a direct consequence of Fact C.2.1.

##  Appendix D Some results about Lie groups

In this section we gather some facts and lemmas about Lie groups and Lie
algebras. Throughout the paper, all the Lie groups are finite dimensional
second countable _real_ Lie groups.

######  Fact D.1.

Closed subgroups and quotient groups of Lie groups are Lie groups.

The identity component of a topological group $G$ is the connected component
containing the identity element. The identity component of a topological group
$G$ might not be open even if $G$ is locally compact. For instance, there are
nondiscrete totally disconnected locally compact groups. For these groups, the
identity component only consists of the identity element, and it is not open
because the topology is not discrete. Nevertheless, the following holds for
Lie groups [14, Proposition 9.1.15].

######  Fact D.2.

If $G$ is a Lie group, then the identity component of $G$ is open and is
contained in every open subgroups of $G$.

In Fact A.1, we introduce the three isomorphism theorems of topological
groups. When $G$ is a Lie group, we can weaken the assumption required for the
first two isomorphism theorems; see [2, Proposition 3.11.2, Proposition 3.31].

######  Fact D.3.

Suppose $G$ is a Lie group, and $H$ is a closed normal subgroup of $G$. Then
we have the following:

  1. (1)

_(First isomorphism theorem for Lie groups)_ If $Q$ is a Lie group, $\phi:G\to
Q$ is a surjective and continuous group homomorphism, and $G$ has countably
many connected components. Then $Q$ is isomorphic as a topological group to
$G/H$.

  2. (2)

_(Second isomorphism theorem for Lie groups)_ Suppose $G$ is a finite
dimensional Lie group, and $S$ is a closed subgroup of $G$, and $SH$ is a
closed subgroup of $G$. Then $S/(S\cap H)$ is canonically isomorphic to the
image of $SH/H$ as Lie groups. This is also equivalent to saying that we have
the exact sequence of Lie groups

$1\to H\to SH\to S/(S\cap H)\to 1.$

We also need the following fact about maximal compact subgroups consisting of
Theorem 14.1.3 (iii) and Theorem 14.3.13 (i) (a) of [14]:

######  Fact D.4.

Suppose $G$ is a Lie group with finitely many connected components. Then we
have the following:

  1. (1)

All maximal compact subgroups of $G$ are conjugate.

  2. (2)

If $0\to H\to G\overset{\pi\ }{\to}G/H\to 0$ is an exact sequence of connected
Lie groups, and $K$ is a maximal compact subgroup of $G$, then $K\cap H$ is a
maximal compact subgroup of $H$, and $\pi(K)$ is a maximal compact subgroup of
$G/H$.

We also use the following simple classification results for Lie groups.

######  Fact D.5.

Let $G$ be a connected Lie group.

  1. (1)

If $G$ has dimension $1$, then it is isomorphic to either $\mathbb{R}$ or
$\mathbb{T}$ as topological groups.

  2. (2)

If $G$ is a solvable group with dimension $d$, and the maximal compact
subgroups of $G$ have dimension $m$. Then $G$ is diffemorphic to
$\mathbb{T}^{m}\times\mathbb{R}^{d-m}$. Moreover, if $G$ is compact, then
$G\cong\mathbb{T}^{d}$.

We say that a topological group $G$ is a covering group of a topological group
$G$ with covering homomorphism $\rho$ if $\rho:G\to G^{\prime}$ is a
topological group homomorphism which is also a covering map. The following is
a consequence of [14, Theorem 9.5.4]:

######  Fact D.6.

Suppose that $G$ and $G^{\prime}$ are connected Lie groups and that $G$ is a
covering group of $G^{\prime}$ with covering homomorphism $\rho$. Then
$\ker\rho$ is a closed normal subgroup of the center $Z(G)$ of $G$.

We end this section with a lemma about conjugate actions on compact sets in
Lie groups.

######  Lemma D.7.

For a Lie group $G$ and a closed normal subgroup $H$, if a precompact
$A\subseteq H$ such that the closure of $A$ is in $B$ and $B$ is a relative
open subset in $H$, then the following holds: When $g\in G$ is sufficiently
close to $\mathrm{id}_{G}$, we have $gAg^{-1}\subseteq B$.

###### Proof.

We prove the lemma by contradiction. Assuming there exist sequences
$g_{n}\rightarrow\mathrm{id}$ and $\\{h_{n}\\}\subseteq A$ such that
$g_{n}h_{n}g_{n}^{-1}\notin B$. Since $A$ is precompact we may assume
$h_{n}\rightarrow h\in\overline{A}$. But then $g_{n}h_{n}g_{n}^{-1}\rightarrow
h\in\overline{A}$. This contradicts the fact that each $g_{n}h_{n}g_{n}^{-1}$
is in the closed set $H\setminus B$ that does not meet $\overline{A}$. Hence
the assumption is false and the conclusion holds. ∎

##  Appendix E Solvable and Semisimple Lie groups

From [14, Section 9.1], there is a functor $\bm{\mathrm{L}}$ from the category
of Lie groups to the category of Lie algebras that assigns each Lie group $G$
to its Lie algebra $\bm{\mathrm{L}}(G)$ and a Lie group morphism $\phi:G\to H$
to its tangent morphism
$\bm{\mathrm{L}}(\phi):\bm{\mathrm{L}}(G)\to\bm{\mathrm{L}}(H)$ of Lie
algebras. We will adopt a more colloquial language in this paper, invoking
this functor implicitly.

######  Fact E.1.

Suppose $G$ and $H$ are Lie groups, and $\mathfrak{g}$ and $\mathfrak{h}$ are
their Lie algebras. If $H$ is a subgroup of $G$, then $\mathfrak{h}$ is a
subalgebra of $\mathfrak{g}$. If $H$ is a normal subgroup of $G$, then
$\mathfrak{h}$ is an ideal in $\mathfrak{g}$, and $\mathfrak{g}/\mathfrak{h}$
is canonically isomorphic to the Lie algebra of $G/H$.

Suppose $\mathfrak{g}$ is the Lie algebra of $G$. The exponential function
$\mathrm{exp}:\mathfrak{g}\to G$ is defined as in [14, Section 9.2]. We will
use the functoriality of the exponential function [14, Proposition 9.2.10]

######  Fact E.2.

Suppose $G$ and $H$ are Lie groups, $\phi:G\to H$ is a homomorphism of Lie
groups, $\mathfrak{g}$ and $\mathfrak{h}$ are the Lie algebras of $G$ and $H$,
$\alpha:\mathfrak{g}\to\mathfrak{h}$ is the tangent morphism of $\phi$, and
$\mathrm{exp}_{G}:\mathfrak{g}\to G$ and $\mathrm{exp}_{H}:\mathfrak{h}\to H$
are the exponential maps. Then
$\mathrm{exp}_{H}\circ\alpha=\mathrm{exp}_{G}\circ\phi$. In other words, the
following diagram commutes:

${G}$${H}$${\mathfrak{g}}$${\mathfrak{h}}$$\scriptstyle{\phi}$$\scriptstyle{\alpha}$$\scriptstyle{\mathrm{exp}_{G}}$$\scriptstyle{\mathrm{exp}_{H}}$

Suppose $\mathfrak{g}$ is a Lie algebra. The derived Lie algebra
$[\mathfrak{g},\mathfrak{g}]$ of $\mathfrak{g}$ is the subalgebra of
$\mathfrak{g}$ generated by the Lie brackets of the pairs of elements of
$\mathfrak{g}$. We say that $\mathfrak{g}$ is solvable if the derived sequence

$\mathfrak{g}\geq[\mathfrak{g},\mathfrak{g}]\geq[[\mathfrak{g},\mathfrak{g}],[\mathfrak{g},\mathfrak{g}]]\geq\ldots$

eventually arrive at the $0$-algebra. A Lie group is solvable if its Lie
algebra is solvable. The following is a consequence of [14, Proposition
5.4.3]:

######  Fact E.3.

Every subalgebra and quotient algebra of a solvable Lie algebra is solvable.
Hence, every closed subgroup and quotient group of a solvable Lie group is
solvable.

The following is another consequence of [14, Proposition 5.4.3]:

######  Fact E.4.

Suppose $\mathfrak{g}$ is a Lie algebra. Then $\mathfrak{g}$ has a largest
solvable subalgebra $\mathfrak{q}$. If $G$ is a Lie group with Lie algebra
$\mathfrak{g}$ and $\mathrm{exp}:\mathfrak{g}\to G$ is the exponential map,
then $Q=\langle\mathrm{exp}(\mathfrak{q})\rangle$ is the largest closed
connected solvable subgroup of $G$. Hence, $Q$ is a characteristic subgroup of
$G$.

The subalgebra $\mathfrak{q}$ as in Fact E.4 is called the radical of
$\mathfrak{g}$, and the subgroup $Q$ as in Fact E.4 is called the radical of
$G$. A Lie algebra is semisimple if it has trivial radical. A lie group is
semisimple if its Lie algebra is semisimple, or equivalently, if it has
trivial radical. The following results follows from [14, Proposition 5.4.3]:

######  Fact E.5.

Let $G$ be a connected Lie group. Let $Q$ be the radical of $G$. Then $S=G/Q$
is a semisimple Lie group.

A Lie group is simple if its Lie algebra is simple. Note that a simple Lie
group needs not to be simple as a group. We use the following fact for simple
Lie groups.

######  Fact E.6.

A connected Lie group $G$ is a simple Lie group if and only if all its normal
proper subgroups are discrete, and contained in $Z(G)$.

Suppose $\mathfrak{g}$ is a finite dimensional Lie algebra. For
$x\in\mathfrak{g}$, let
$\text{ad}x:\mathfrak{g}\to\mathfrak{g},y\mapsto[x,y]$. Then ad is an
endomorphism of $\mathfrak{g}$. The Cartan–Killing form of
$\kappa_{\mathfrak{g}}:\mathfrak{g}\times\mathfrak{g}\to\mathbb{R}$ is given
by

$\kappa_{\mathfrak{g}}(x,y)=\text{tr}(\text{ad}x\ \text{ad}y).$

The Cartan–Killing form is invariant under an automorphism of $\mathfrak{g}$
as this corresponds to a change of basis. The following fact is from [14,
Lemma 5.5.8]

######  Fact E.7.

Suppose $\mathfrak{g}$ is a Lie algebra, $\kappa_{\mathfrak{g}}$ is the
Cartan–Killing form of $\mathfrak{g}$, and $\mathfrak{h}$ is an ideal of
$\mathfrak{g}$. Then the orthogonal space $\mathfrak{h}^{\perp}$ of
$\mathfrak{h}$ with respect to $\kappa_{\mathfrak{g}}$ is also an ideal. If
$\mathfrak{g}$ is semisimple, then
$\mathfrak{g}=\mathfrak{h}\oplus\mathfrak{h}^{\perp}$ and
$\kappa_{\mathfrak{g}}=\kappa_{\mathfrak{h}}\oplus\kappa_{\mathfrak{h}^{\perp}}$
where $\kappa_{\mathfrak{h}}$ and $\kappa_{\mathfrak{h}^{\perp}}$ are the
Cartan–Killing form of $\mathfrak{h}$ and $\mathfrak{h}^{\perp}$.

The following fact follows from [14, Lemma 5.5.13]. It is also a consequence
of Fact E.7 and the alternative characterization of semisimple Lie algebras as
those whose Cartan–Killing form is nondegenerate.

######  Fact E.8.

Every ideal and quotient algebra of a semisimple Lie algebra is semisimple.
Hence, every normal subgroup and quotient group of a semisimple Lie group is
semisimple.

The first and second assertions in the following fact are immediate
consequences of Facts E.4, E.3, E.8

######  Fact E.9.

If $G$ is a connected semisimple Lie group, then its center $Z(G)$ is a
finitely generated discrete group, the quotient map $\rho:G\to G/Z(G)$ is a
covering map.

The following fact is a consequence of [14, Proposition 9.5.2 and Theorem
9.5.4].

######  Fact E.10.

If $G$ and $G^{\prime}$ are connected Lie groups, $\rho:G\to G^{\prime}$ is
covering map, $Z(G)$ and $Z(G^{\prime})$ are the centers of $G$ and
$G^{\prime}$. Then we have $\ker\rho\leq Z(G)$ and
$Z(G^{\prime})=Z(G)/\ker\rho$.

The first assertion in the following fact is known as Weyl’s theorem on Lie
groups with semisimple compact Lie algebra [14, Theorem 12.1.17].

######  Fact E.11.

If $G$ is a connected semisimple Lie group with compact Lie algebra, then $G$
is compact and $Z(G)$ is finite.

The following Fact is a consequence of Fact E.11 and the result in [29]. This
can also be proven directly using [14, Proposition 13.1.10 (ii)]; we thank
Jinpeng An for pointing this out to us.

######  Fact E.12.

If $G$ is a simply connected simple Lie group, then the center $Z(G)$ of $G$
has rank at most $1$.

Suppose $\mathfrak{g}$ is a finite dimensional Lie algebra with Cartan–Killing
form $\kappa_{\mathfrak{g}}$. A Lie algebra automorphism $\tau$ of
$\mathfrak{g}$ is a Cartan involution if $\tau^{2}=\mathrm{id}_{\mathfrak{g}}$
and $(x,y)\mapsto-\kappa_{\mathfrak{g}}(x,\tau(y))$ is a positive definite
bilinear form. The following fact is [14, Theorem 13.2.10]

######  Fact E.13.

Let $\mathfrak{g}$ be a semisimple Lie algebra. Then $\mathfrak{g}$ has a
Cartan involution $\tau$.

We refer the reader to [20, Section 6.4] for the full definition of Iwasawa
decomposition; we will need the following fact which is a consequence of [20,
Theorem 6.31, Theorem 6.46] and [14, Corollary 12.2.3].

######  Fact E.14 (Iwasawa decomposition).

Suppose $G$ is a connected semisimple Lie group with Lie algebra
$\mathfrak{g}$, $\tau$ is a Cartan’s involution of $\mathfrak{g}$,
$\mathfrak{k}$ the subalgebra of $\mathfrak{g}$ fixed by $\tau$, and
$\mathrm{exp}:\mathfrak{g}\to G$ is the exponential map. Then there is an
Iwasawa decomposition $G=KAN$ such that the following holds:

  1. (1)

the multiplication map

$\Phi:K\times A\times N\rightarrow G:(k,a,n)\mapsto kan$

is a diffeomorphism.

  2. (2)

$K=\mathrm{exp}(\mathfrak{k)}$ is a connected closed subgroup of $G$,
$Z(G)\subseteq K$, and $K$ is a maximal compact subgroup of $G$ if $Z(G)$ is
finite.

  3. (3)

$A$ is an abelian closed subgroup of $G$, $N$ is a nilpotent closed subgroup
of $G$, and both $A$ and $N$ are simply connected.

  4. (4)

$Q=AN$, we have that $Q$ is a solvable closed subgroup of $G$, and
$N\vartriangleleft Q$.

The following fact is a consequence of the definition of Iwasawa decomposition
in [20, Section 6.4].

######  Fact E.15.

If $G$ is a noncompact semisimple Lie group with Iwasawa decomposition
$G=KAN$, then $AN$ has dimension at least $2$.

## Acknowledgements

The authors would like to thank Ehud Hrushovski for introducing the authors to
this problem, József Balogh and Anand Pillay for helpful discussions, Richard
Gardner, Vitali Milman, and Rolf Schneider for several historical remarks, and
Guoxian Song for drawing the figure. Special thanks to Jinpeng An for
suggesting many useful references, and for carefully reading the paper and
pointing out an important error in the first version of the manuscript.

## References

  * [1] Elías Baro, Eric Jaligot, and Margarita Otero, _Commutators in groups definable in o-minimal structures_ , Proc. Amer. Math. Soc. 140 (2012), no. 10, 3629–3643. MR 2929031
  * [2] Nicolas Bourbaki, _Lie groups and Lie algebras. Chapters 1–3_ , Elements of Mathematics (Berlin), Springer-Verlag, Berlin, 1989, Translated from the French, Reprint of the 1975 edition. MR 979493
  * [3] by same author, _General topology. Chapters 1–4_ , Elements of Mathematics (Berlin), Springer-Verlag, Berlin, 1998, Translated from the French, Reprint of the 1989 English translation. MR 1726779
  * [4] by same author, _Integration. II. Chapters 7–9_ , Elements of Mathematics (Berlin), Springer-Verlag, Berlin, 2004, Translated from the 1963 and 1969 French originals by Sterling K. Berberian. MR 2098271
  * [5] Hermann Brunn, _Über Ovale und Eiflächen_ , Inaugural Dissertation, München: Akademische Buchdruckerei von F. Straub. (1887).
  * [6] Michael Christ, _Near equality in the Brunn-Minkowski inequality_ , arXiv:1207.5062 (2012).
  * [7] Alessio Figalli and David Jerison, _Quantitative stability for sumsets in $\mathbb{R}^{n}$_, J. Eur. Math. Soc. (JEMS) 17 (2015), no. 5, 1079–1106. MR 3346689
  * [8] by same author, _Quantitative stability for the Brunn-Minkowski inequality_ , Adv. Math. 314 (2017), 1–47. MR 3658711
  * [9] Gerald B. Folland, _A course in abstract harmonic analysis_ , Studies in Advanced Mathematics, CRC Press, Boca Raton, FL, 1995. MR 1397028
  * [10] Richard J. Gardner, _The Brunn-Minkowski inequality_ , Bull. Amer. Math. Soc. (N.S.) 39 (2002), no. 3, 355–405. MR 1898210
  * [11] Andrew M. Gleason, _Groups without small subgroups_ , Ann. of Math. (2) 56 (1952), 193–212. MR 49203
  * [12] Mikhael Gromov, _Isoperimetry of waists and concentration of maps_ , Geom. Funct. Anal. 13 (2003), no. 1, 178–215. MR 1978494
  * [13] Ralph Henstock and Murray Macbeath, _On the measure of sum-sets. I. The theorems of Brunn, Minkowski, and Lusternik_ , Proc. London Math. Soc. (3) 3 (1953), 182–194. MR 56669
  * [14] Joachim Hilgert and Karl-Hermann Neeb, _Structure and geometry of Lie groups_ , Springer Monographs in Mathematics, Springer, New York, 2012. MR 3025417
  * [15] Ehud Hrushovski, _personal communication_.
  * [16] by same author, _Stable group theory and approximate subgroups_ , J. Amer. Math. Soc. 25 (2012), no. 1, 189–243. MR 2833482
  * [17] Yifan Jing and Chieu-Minh Tran, _Minimal and nearly minimal measure expansions in connected unimodular groups_ , arXiv:2006.01824 (2020).
  * [18] Johannes Kemperman, _On products of sets in a locally compact group_ , Fund. Math. 56 (1964), 51–68. MR 202913
  * [19] Anthony W. Knapp, _Representation theory of semisimple groups_ , Princeton Mathematical Series, vol. 36, Princeton University Press, Princeton, NJ, 1986, An overview based on examples. MR 855239
  * [20] by same author, _Lie groups beyond an introduction_ , second ed., Progress in Mathematics, vol. 140, Birkhäuser Boston, Inc., Boston, MA, 2002. MR 1920389
  * [21] Martin Kneser, _Summenmengen in lokalkompakten abelschen Gruppen_ , Math. Z. 66 (1956), 88–110. MR 81438
  * [22] Gian Paolo Leonardi and Simon Masnou, _On the isoperimetric problem in the Heisenberg group ${\mathbb{H}}^{n}$_, Ann. Mat. Pura Appl. (4) 184 (2005), no. 4, 533–553. MR 2177813
  * [23] Lazar’ A. Lyusternik, _Die Brunn–Minkowskische ungleichnung für beliebige messbare mengen_ , Comptes Rendus de l’Académie des Sciences de l’URSS. Nouvelle Série. III (1935), 55–58.
  * [24] Murray Macbeath, _On the measure of product sets in a topological group_ , J. London Math. Soc. 35 (1960), 403–407. MR 126501
  * [25] Michael McCrudden, _On the Brunn-Minkowski coefficient of a locally compact unimodular group_ , Proc. Cambridge Philos. Soc. 65 (1969), 33–45. MR 233921
  * [26] by same author, _On critical pairs of product sets in a certain matrix group_ , Proc. Cambridge Philos. Soc. 67 (1970), 569–581. MR 269811
  * [27] Hermann Minkowski, _Geometrie der Zahlen_ , Leipzig: Teubner. (1896).
  * [28] Roberto Monti, _Brunn-Minkowski and isoperimetric inequality in the Heisenberg group_ , Ann. Acad. Sci. Fenn. Math. 28 (2003), no. 1, 99–109. MR 1976833
  * [29] A. I. Sirota, _Centers of non-compact simple Lie groups_ , Soviet Math. Dokl. 1 (1960), 1021–1024. MR 0133401
  * [30] Terence Tao, _The Brunn-Minkowski inequality for nilpotent groups_ , available at https://terrytao.wordpress.com/2011/09/16/ (2011).
  * [31] Hidehiko Yamabe, _A generalization of a theorem of Gleason_ , Ann. of Math. (2) 58 (1953), 351–365. MR 58607