# Modelling and Kron reduction of power flow networks in directed graphs

Ruohan Wang
Department of Electrical Engineering
Technische Universiteit Eindhoven
Eindhoven, Netherlands
<EMAIL_ADDRESS>
&Zhiyong Sun
Department of Electrical Engineering
Technische Universiteit Eindhoven
Eindhoven, Netherlands
<EMAIL_ADDRESS>

###### Abstract

Electrical grids are large-sized complex systems that require strong computing
power for monitoring and analysis. Kron reduction is a general reduction
method in graph theory and is often used for electrical circuit
simplification. In this paper, we propose a novel formulation of the weighted
Laplacian matrix for directed graphs. The proposed matrix is proved to be
strictly equivalent to the conventionally formulated Laplacian matrix and is
verified to well model a lossless DC power flow network in directed graphs. We
as well present significant properties of the proposed weighted Laplacian and
conditions of Kron reduction in directed graphs and in lossless DC power flow
networks. The reduction method is verified via simulation models of IEEE-3,
IEEE-5, IEEE-9, IEEE-14, and IEEE RTS-96 test system.

_K_ eywords Directed graphs $\cdot$ Laplacian matrix $\cdot$ Incidence matrix
$\cdot$ Kron reduction $\cdot$ Schur complement $\cdot$ DC power flow

##  1 Introduction

###  1.1 Background and motivations

Large-scale systems such as electrical grids require a heavy computing
workload due to their sizes and complexity. It is only natural to think of
applying model reduction techniques to ease the workload. Kron reduction is a
ubiquitous reduction method in electrical circuit analysis. Kron reduction is
widely used in control theory and engineering to simplify and analyze large-
scale systems, particularly in the design of control systems for electric
power grids, aircraft, and other complex systems. It is also used in other
fields, such as biology and economics, where it can be used to reduce the
complexity of models and make them more tractable for analysis and simulation.
Originally proposed in [1] as purely algebraic Gaussian elimination of certain
vertices in electrical circuits, Kron reduction can also be viewed from the
standpoint of graph theory. By the nature of electrical circuit modeling, most
of the existing model reduction work in the field of control theory is based
on undirected graphs. However, in many applications including networked
control systems, directed graphs arise just as naturally as undirected ones,
hence before the reduction process, it is of interest to think about using
directed graphs for electrical power network modeling.

###  1.2 Literature review

In this subsection, we review some existing research work on the analysis and
model reduction of electrical networks.

An algorithm for maximizing power flows within a power network to prevent
catastrophic power outages was proposed and verified in [2]. A parallel
distributed memory structure exploiting framework which accelerates the
solution of the Security Constrained Optimal Power Flow (SCOPF) problems was
proposed in [3]. Basic graph theories were used to lay the foundation for
further discussion in [2] and [3]. However, in both papers, the main focus was
the development of the proposed algorithms for a full-sized network, where the
model reduction technique was not taken into consideration.

A novel notion termed _cutset angle_ was eloquently proposed by Dobson in [4]
with the purpose of monitoring power flow network stress. The formulation of
_cutset angle_ by Dobson could be viewed as a two-stage treatment: add a
synthetic vertex being the algebraically weighted sum of all other vertices to
the network, and apply Kron reduction to the network eliminating all vertices
except for the synthetic vertex. Undirected graphs were used by Dobson for
modelling electrical circuits in [4]. Similarly, the terminal voltage/current
behavior of a purely linear resistive circuit was derived in [5] by J. C.
Willems and E.I. Verriest, followed by [6], where A. van der Schaft
characterized the input-output behaviors of a linear resistive circuit before
and after the removal of certain vertices. The heavy usage of the symmetric
weighted Laplacian of a graph was the highlight of [6].

Meanwhile, Dörfler et al. provided a detailed graph-theoretic analysis of the
Kron reduction process in [7], which was followed by the application of Kron
reduction on resistive circuits in [8]. Purely algebraic conditions that
relate synchronization and transient stability of a power network were derived
by Dörfler et al. in [9]. Then in [10], Dörfler et al. further proposed
analytical approaches to phase and frequency synchronization in Kron-reduced
networks. In [11], Dörfler et al. surveyed both historic and recent results on
electrical network analysis based on algebraic graph theory. Dörfler et al.
concluded [11] by a series of open questions at the intersection of algebraic
graph theory and electrical networks. Based on Dörfler’s work, the Kron-
reduced model was used to analyze both the transient and steady-state behavior
of unreduced electrical networks in [12]. Also based on Dörfler’s work, a
time-domain generalization of Kron reduction for purely resistive and
inductive networks was put forth in [13]. However, despite the fact that the
mentioned series of work on Kron reduction and its application on electrical
networks were comprehensive and enlighting, all of them were still solely
targeting undirected graphs.

Young et al. introduced a pairwise property of vertices that only depends on
connections between the vertices in [14], which is a novel generalized notion
of effective resistances that apply to both undirected and directed graphs.
The focus of the very paper was the development of the foundation of effective
resistances for their application involving directed graphs. In [15], Sugiyama
et al. extensively elaborated on Kron reduction to directed graphs. Despite
that modelling electrical networks as directed graphs was briefly mentioned in
[14] and [15], little physical interpretation of electrical networks had been
covered, unfortunately.

###  1.3 Contributions

Contributions of this paper are summarized as follows:

  * •

Modelling power flow networks in directed graphs is justified. A novel
expression for the weighted directed Laplacian matrix using the graph’s
incidence matrix is proposed and proved to be strictly equivalent to the
conventional weighted Laplacian.

  * •

A number of properties of the proposed weighted Laplacian matrix are analyzed,
including its eigenvalue, entry values and the existence of Schur complements.
These properties are significant to model and characterize power flow networks
in directed graphs.

  * •

Input and output behaviors of a lossless power flow network are characterized
by the proposed weighted Laplacian. I/O behaviors of the reduced network are
characterized by the reduced Laplacian matrix.

  * •

Implementations of Kron reduction to IEEE-3, IEEE-5, IEEE-9, and IEEE-14 are
successfully delivered. Numerical results of network reduction on IEEE-14 test
feeder and IEEE RTS-96 are presented, showing that the proposed approach can
be applied to power networks with considerable sizes.

###  1.4 Organization

Section 2 gives a summary of the problem formulation of this paper. Section 3
recalls some preliminaries in matrix analysis and algebraic graph theory.
Section 4 presents the formulation of the weighted Laplacian in the context of
a DC power flow network and graph-theoretic analysis of Schur complements.
Section 5 presents the graph-theoretic analysis of the Kron reduction process
on DC power flow networks. Section 6 presents numerical results of the
proposed Kron reduction to an IEEE-14 test feeder and the modified IEEE RTS-96
test system. Finally, Section 7 concludes the paper and suggests future
research directions.

##  2 Problem formulation

We seek answers to these particular questions.

  * •

How to model a lossless DC power flow network using a directed weighted graph?

  * •

What are the properties of the proposed weighted Laplacian matrix?

  * •

How is the proposed weighted Laplacian matrix related to the conventionally
defined Laplacian matrix?

  * •

Does Kron reduction always exist for a directed graph?

  * •

Can Kron reduction always be performed to a lossless power flow network?

  * •

How are input-output behaviors of the original network and the reduced one
related?

These are the major problems that motivate the work. Some were formulated
during the literature review phase, and others arose inevitably during the
model reduction process, which in return complemented problem formulation.

##  3 Preliminaries

###  3.1 Schur complement

Schur complement will be introduced in this section since it is the core of
Kron reduction. Consider a partitioned matrix
$\mathcal{M}=\left(\begin{array}[]{ll}\mathcal{P}&\mathcal{Q}\\\
\mathcal{R}&\mathcal{X}\end{array}\right)$, where
$\mathcal{P},\mathcal{Q},\mathcal{R},\mathcal{X}$ are respectively $p\times
p,p\times q,q\times p,q\times q$ sized matrices and the non-singular matrix
$\mathcal{P}$ is called the leading principal sub-matrix of $\mathcal{M}$
[16]. The term ‘Schur complement’ of $\mathcal{P}$ was introduced by Schur:
$\mathcal{M}/\mathcal{P}\triangleq\mathcal{X}-\mathcal{R}\mathcal{P}^{-1}\mathcal{Q}$.
Note that Schur complement exists with respect to any non-singular sub-matrix
formed with columns and rows from the original matrix. Let $\alpha,\beta$ be
given index sets, which are subsets of $\left\\{1,2,...,p+q\right\\}$. We
denote the cardinality of an index set $\alpha$ by the notation
$\lvert\alpha\rvert$ and its complement by the notation
$\alpha^{c}=\left\\{1,2,...,p+q\right\\}\setminus\alpha$. Let
$\mathcal{M}\left[\alpha,\beta\right]$ denote the sub-matrix of $\mathcal{M}$
formed with rows indexed by $\alpha$ and columns indexed by $\beta$. If
$\mathcal{M}\left[\alpha^{c},\beta^{c}\right]$ is non-singular, we denote the
Schur complement of $\mathcal{M}\left[\alpha^{c},\beta^{c}\right]$ by
$\mathcal{M}/\mathcal{M}\left[\alpha^{c},\beta^{c}\right]\triangleq\mathcal{M}\left[\alpha,\beta\right]-\mathcal{M}\left[\alpha,\beta^{c}\right](\mathcal{M}\left[\alpha^{c},\beta^{c}\right])^{-1}\mathcal{M}\left[\alpha^{c},\beta\right]$.

###  3.2 Kron reduction

Figure 1: Gaussian elimination on resistive circuits

Kron reduction is a general method in graph theory for reducing the size of an
electrical network by removing unimportant vertices and edges. It was first
introduced by Kron as ‘Reduction Formulas’ in [1] which was obtained through a
pure Gaussian elimination procedure.

Consider a linear resistive circuit with $n$ vertices, vertex voltages
$V\in\mathbb{R}^{n\times 1}$, vertex current injections
$I\in\mathbb{R}^{n\times 1}$, branch impedances $z_{ij}\geq 0$ connecting
vertex $i$ and vertex $j$ and the impedance matrix $Z\in\mathbb{R}^{n\times
n}$, which is a Laplacian matrix. By partitioning vertices following
Kirchhoff’s laws into two subsets: border vertices
$\alpha\subset\left\\{1,...,n\right\\},|\alpha|\geq 2$ and inner vertices
$\alpha^{c}=\left\\{1,...,n\right\\}\setminus\alpha$, the current-balance
equations for the network can be partitioned as

$\displaystyle\left[\begin{array}[]{c}V_{\alpha}\\\
V_{\alpha^{c}}\end{array}\right]=\left[\begin{array}[]{cc}Z_{\alpha\alpha}&Z_{\alpha\alpha^{c}}\\\
Z_{\alpha^{c}\alpha}&Z_{\alpha^{c}\alpha^{c}}\end{array}\right]\left[\begin{array}[]{c}I_{\alpha}\\\
I_{\alpha^{c}}\end{array}\right].$ (7)

Gaussian elimination of inner current injections $I_{\alpha^{c}}$ in (7) gives
an electrically-equivalent reduced network with border vertices $\alpha$
obeying the reduced current-balance equations

$\displaystyle V_{\alpha}+Z_{ac}V_{\alpha^{c}}=Z_{red}I_{\alpha}$ (8)

where the reduced impedance matrix $Z_{red}$ is given by the Schur complement
of $Z$ with respect to inner vertices, that is
$Z_{red}=Z_{\alpha\alpha}-Z_{\alpha\alpha^{c}}Z_{\alpha^{c}\alpha^{c}}^{-1}Z_{\alpha^{c}\alpha}$,
and the accompanying matrix
$Z_{ac}=-Z_{\alpha\alpha^{c}}Z_{\alpha^{c}\alpha^{c}}^{-1}$ maps inner
voltages to border voltages in the reduced network.

_Example_ A linear resistive circuit with 6 vertices is presented in Fig. 1.
Vertices $3,4,5,6$ are _inner vertices_ that are only connected to other
vertices within the network. Vertices $1,2$ are _border vertices_ that are
connected to other vertices within the network and voltage/current sources
outside the network. Current-balance equations for this network can be
partitioned in the form of (7). Gaussian elimination of inner vertices gives
an electrically-equivalent reduced network, of which border vertices obey the
reduced current-balance equations given by (8). This example illustrates that
both a linear resistive circuit and the reduced network eliminating all inner
vertices can be described by the matrix-formed current-balance equations.
$\hfill\square$

Similarly, consider a lossless DC power flow network with $n$ vertices, vertex
active powers $P\in\mathbb{R}^{n\times 1}$, vertex angles
$\theta\in\mathbb{R}^{n\times 1}$, branch susceptances $b_{ij}\geq 0$
connecting vertex $i$ and vertex $j$ and the susceptance matrix
$S\in\mathbb{R}^{n\times n}$ which is a Laplacian matrix. By partitioning
vertices into two subsets: border vertices
$\beta\subset\left\\{1,...,n\right\\},|\beta|\geq 2$ and inner vertices
$\beta^{c}=\left\\{1,...,n\right\\}\setminus\beta$, the power-angle equation
for the network can be partitioned as

$\displaystyle\left[\begin{array}[]{c}P_{\beta}\\\
P_{\beta^{c}}\end{array}\right]=\left[\begin{array}[]{cc}S_{\beta\beta}&S_{\beta\beta^{c}}\\\
S_{\beta^{c}\beta}&S_{\beta^{c}\beta^{c}}\end{array}\right]\left[\begin{array}[]{c}\theta_{\beta}\\\
\theta_{\beta^{c}}\end{array}\right].$ (15)

Gaussian elimination of inner angles $\theta_{{\beta}^{c}}$ in (15) gives an
electrically-equivalent reduced network with border vertices $\beta$ obeying
the reduced power-angle equation:

$\displaystyle P_{\beta}+S_{ac}P_{\beta^{c}}=S_{red}\theta_{\beta}$ (16)

where the reduced susceptance matrix $S_{red}$ is given by the Schur
complement of $S$ with respect to inner vertices, that is
$S_{red}=S_{\beta\beta}-S_{\beta\beta^{c}}S_{\beta^{c}\beta^{c}}^{-1}S_{\beta^{c}\beta}$,
and the accompanying matrix
$S_{ac}=-S_{\beta\beta^{c}}S_{\beta^{c}\beta^{c}}^{-1}$ maps inner active
powers to border active powers in the reduced network. Kron reduction will be
performed mainly to lossless DC power networks in this paper.

_Example_ A lossless DC power flow network with 6 buses/vertices is presented
in Fig. 2. Vertices $3,4,5,6$ are _inner vertices_ that are only connected to
other vertices within the network. Vertices $1,2$ are _border vertices_ that
are connected to other vertices within the network and generators/loadings
outside the network. Power-angle equation for this network can be partitioned
in the form of (15). Gaussian elimination of inner vertices gives an
electrically-equivalent reduced network, of which border vertices obey the
reduced power-balance equations given by (16). Similarly, this example
illustrates that both a lossless DC power flow network and the reduced network
eliminating all inner vertices can be described by the matrix-formed power-
angle equation and that the reduction process essentially performs the Schur
complement. $\hfill\square$

Figure 2: Gaussian elimination on lossless DC power flow networks

Before continuing to the next subsection, we would like to distinguish between
_block-by-block Kron reduction_ and _iterative Kron reduction_. First, we
recall the definition of _iterative Kron reduction_.

######  Definition 1 (Iterative Kron reduction, T. Sugiyama and K. Sato [15])

Iterative Kron reduction associated to a weighted Laplacian matrix
$\mathcal{L}\in\mathbb{R}^{n\times n}$ and indices
$\left\\{1,...,|\alpha|\right\\}$, is a sequence of matrices
$\mathcal{L}^{l}\in\mathbb{R}^{(n-l)\times(n-l)}$,
$l\in\left\\{1,...,n-|\alpha|\right\\}$, which is defined as

$\displaystyle\mathcal{L}^{l}=\mathcal{L}^{l-1}/\mathcal{L}^{l-1}[\left\\{k_{l}\right\\},\left\\{k_{l}\right\\}]$
(17)

where $\mathcal{L}^{0}=\mathcal{L}$ and $k_{l}=n+1-l$.

###### Remark 1

_Block-by-block Kron reduction_ eliminates more than one vertex during each
reduction process. We adopt _block-by-block Kron reduction_ as the main
reduction method in this paper, which essentially performs the Schur
complement with block sub-matrices. In contrast, _iterative Kron reduction_
eliminates one vertex during each reduction process. The reduction result of
_block-by-block Kron reduction_ has been proved to be strictly equivalent to
that of _iterative Kron reduction_ when the same vertex subset is eliminated
in [15].

###  3.3 Directed graph, the incidence matrix and its variation

Consider a directed and unweighted graph
$\mathcal{G}_{d}=(\mathcal{V},\varepsilon_{d},\mathcal{H})$, where
$\mathcal{V}$ denotes the finite vertex set, $\varepsilon_{d}$ denotes the
directed edge set and
$\mathcal{H}\in\mathbb{R}^{|\mathcal{V}|,|\mathcal{\varepsilon}_{d}|}$ is the
corresponding unique incidence matrix. $|\mathcal{V}|$ is the number of
vertices, and $|\mathcal{\varepsilon}_{d}|$ is the number of edges. The
$(i,j)$th element $[\mathcal{H}]_{ij}$ of the incidence matrix $\mathcal{H}$
is equal to 1 if vertex $i$ is the head of the edge $j$, is equal to -1 if the
vertex is the tail of edge, and 0 otherwise. The head/tail specification in
the context of $a$ $DC$ $power$ $flow$ $network$ $graph$ is determined by the
positioning of diode-like-functional reactive components on transmission
lines, which will be elaborated in Section 4.1. Thus the incidence matrix
functions as a mapping from $\varepsilon_{d}$ to the set of ordered pairs of
$(v,w)\in\mathcal{V}^{2}$, with no self-loops allowed in the graph under
consideration. For a given graph $\mathcal{G}_{d}$, we identify a subset
$\mathcal{V}_{b}\subset\mathcal{V}$ as _boundary vertices_. Vertices that are
tails of all edges connected to them are _sink_ vertices. Vertices that are
heads of all edges connected to them are _source_ vertices. _Sink_ and
_source_ vertices are _boundary vertices_. _Boundary vertices_ cannot be
eliminated. The subset $\mathcal{V}_{i}=\mathcal{V}\setminus\mathcal{V}_{b}$
contains all the other vertices of the graph, being called _interior
vertices_. _Interior vertices_ can be eliminated. A power flow network usually
includes both _sink_ and _source_. By identifying them as _boundary vertices_
, we ensure the integrity of the reduced graphs.

Consider a directed and weighted graph
$\mathcal{G}_{d}=(\mathcal{V},\varepsilon_{d},\mathcal{A})$. Entries
$[\mathcal{A}]_{ij}$ of the adjacency matrix $\mathcal{A}$ can be expressed
in:

$\displaystyle[\mathcal{A}]_{ij}\triangleq\left\\{\begin{array}[]{c}b_{k},\text{
if }(v_{i},v_{j})=e_{ij}\in\varepsilon_{d},b_{k}\text{ is the weight on edge
}e_{ij}\\\ 0,\text{otherwise.}\end{array}\right.$ (20)

A diagonal degree matrix $\mathcal{D}$ corresponding to the directed and
weighted graph $\mathcal{G}_{d}$ can be derived from the introduced adjacency
matrix $\mathcal{A}$. Diagonal entries $[\mathcal{D}]_{ii}$ of the diagonal
degree matrix $\mathcal{D}$ are defined as:
$[\mathcal{D}]_{ii}\triangleq\sum_{j=1}^{n}[\mathcal{A}]_{ij}$.

Before continuing to the formulation of the weighted Laplacian matrix for a
lossless power flow network, definitions of different classes of directed
graphs and _walk products_ are given below for future reference.

######  Definition 2 (Strongly-connected graph)

A directed graph is said to be _strongly-connected_ if every vertex can be
reached from every other vertex.

######  Definition 3 (Quasi-strongly-connected graph)

A directed graph is said to be _quasi-strongly-connected_ if there exists one
vertex that can reach all the other vertices in the graph. The very vertex is
called _root vertex_.

######  Definition 4 (Walk products $(\mathcal{A}^{k})_{0k}$, [17])

Let $\mathcal{A}$ be the $n\times n$ adjacency matrix for a given weighted
directed graph $\mathcal{G}_{d}$. Let $(\mathcal{A}^{k})_{0k}$ given by
$(v_{0},v_{1})$, $(v_{1},v_{2})$, …, $(v_{k-1},v_{k})$ be a walk in
$\mathcal{G}_{d}$. The walk product for the walk $(\mathcal{A}^{k})_{0k}$ is

$\displaystyle\prod_{j=1}^{k}[\mathcal{A}]_{j-1,j}.$ (21)

###### Remark 2

The product given by the expression in (21) is a generic quadrature of the
$(v_{0},v_{k})$-entry of $\mathcal{A}^{k}$. The walk product
$(\mathcal{A}^{k})_{0k}$ is non-zero only when all quadrated elements
$[\mathcal{A}]_{j-1,j}$, $j=1,2,...,k$ are non-zero. A non-zero walk product
$(\mathcal{A}^{k})_{0k}$ indicates that there exists a directed path in
$\mathcal{G}_{d}$ from $v_{0}$ to $v_{k}$.

Next, we continue to formulate the modelling of a lossless power flow network
via weighted Laplacian. Consider a graph $\mathcal{G}_{d}$. In the context of
a DC power flow network, $\theta$ is the vector of angles _at_ vertices/buses
which can be expressed as
$\theta=\left[\theta_{1},\theta_{2},\ldots,\theta_{n}\right]$ where
$\theta_{i}$ is the angle at the vertex $v_{i}$. The notation $\varphi$
denotes the vector of angle difference _across_ edges (between the head and
the tail of the edge) of which entries $\varphi_{k}$ can be expressed as:

$\displaystyle\varphi_{k}=\theta_{i}-\theta_{j}$ (22)

where $v_{i}$ is the head of $\text{edge}_{k}$ and $v_{j}$ is the tail of
$\text{edge}_{k}$. $P_{edge}$ is the vector of active power flowing _through_
edges of which entries $P_{{edge}_{k}}$ can be expressed as:

$\displaystyle P_{{edge}_{k}}=b_{k}\varphi_{k}$ (23)

where $b_{k}$ is the weight of $\text{edge}_{k}$. $P_{v}$ is the vector of
active power extractions _at_ vertices/buses of which entries $P_{v_{i}}$ can
be expressed as:

$\displaystyle P_{v_{i}}=\sum_{k=1}^{l}P_{\text{edge }_{k}}$ (24)

where the vertex $v_{i}$ is the head of $\text{edge}_{k}$ and the number of
edges out of $v_{i}$ is $l$.

Define a matrix $\mathcal{H}_{o}$ being the variation of the incidence matrix
$\mathcal{H}$ by replacing all $-1$ entries with $0$. In order to have a
symmetric notation, define another matrix $\mathcal{H}_{i}$ being the
variation of the incidence matrix $\mathcal{H}$ by replacing all $1$ entries
with $0$. Since $\mathcal{H}=\mathcal{H}_{o}+\mathcal{H}_{i}$, $\mathcal{H}$
maps $P_{edge}$ to active power summations considering both extractions and
injections _at_ vertices. $\mathcal{H}_{i}$ maps $P_{edge}$ to active power
injections alone _at_ vertices. $\mathcal{H}_{o}$ maps $P_{edge}$ to active
power extractions $P_{v}$ alone _at_ vertices, which will be the focus of this
paper. Kirchhoff’s treatment of circuit graphs is external currents
entering/leaving certain vertices of the graph. The motivation of the
treatment in this paper is analog to Kirchhoff’s treatment of circuit graphs,
which is external active power injecting/extracting to/from certain vertices
of the graph. By considering both power injection and extraction, this hybrid
treatment is indispensable in conventional power flow analysis. Still, it
requires the articulation of $\mathcal{H}$, being the composition of
$\mathcal{H}_{o}$ and $\mathcal{H}_{i}$. This conventional treatment will
inevitably result in operations on undirected graphs, which is against our
intentions: reduction to directed graphs. Hence in this paper we intentionally
distinguish between $\mathcal{H}_{o}$ and $\mathcal{H}_{i}$, and we emphasize
$\mathcal{H}_{o}$. According to the author’s literature review, this treatment
has neither been studied nor proposed.

Hereby we introduce our special treatment on the formulation of _vertex power
balance law_ and _angle difference law_ using the incidence matrix
$\mathcal{H}$ and its variation $\mathcal{H}_{o}$.

_Vertex power balance law_ can be given as:

$\displaystyle\mathcal{H}_{o}P_{edge}=-P_{v}.$ (25)

Correspondingly, _angle difference law_ can be written as:

$\displaystyle\varphi=\mathcal{H}^{T}\theta.$ (26)

The formula (25) describes that _active power extractions_ at one vertex is
the summation of all active powers on the edges that have their heads at the
very vertex. The formula (26) illustrates that the _angle difference_ between
any two vertices can be derived from the product of the transpose of the
incidence matrix and the vector of bus angle $\theta$.

##  4 Modelling of power flow networks and weighted Laplacian properties

###  4.1 Weighted Laplacian matrix

In this subsection, for a given lossless power flow network, we present the
formulation of the corresponding weighting matrix $B$, the formulation of the
corresponding incidence matrix $\mathcal{H}$, and subsequently, the
formulation of the corresponding weighted Laplacian matrix $\mathcal{L}$. In
order to streamline the formulation of problems in the context of directed
graphs, we assume that the reactances of all reactive components in the
network are strictly negative. Whenever there is a line with its reactance
with a non-negative value, then we remove the directed edge corresponding to
this reactance. Thus we may as well define the susceptance $b_{i}$ of each
reactive component as the negative reciprocal of its reactance $x_{i}$, that
is $b_{i}=-\frac{1}{x_{i}}>0$, for every edge $e_{i}$ of the network graph.
Positioning of diode-like-functional reactive components determines the
$orientation$ of each edge (i.e. active power is only allowed to flow through
‘diodes’ forwardly). Define the diagonal matrix $B\triangleq
diag\left\\{b_{1},...,b_{n}\right\\}$. By far we have defined the diagonal
weighting matrix $B$ and the incidence matrix $\mathcal{H}$ for the directed
graph $\mathcal{G}_{d}$ in the context of a DC power flow network.
Furthermore, we will throughout assume that the network graph under
consideration contains at least two vertices. The following example
illustrates the formulations of $\mathcal{H}$, $\mathcal{H}_{o}$, and $B$.

_Example_ Consider a lossless 4-bus power flow network; see Fig.3 (upper). See
Fig. 3 (bottom) for the corresponding graph representation of the 4-bus
lossless network. Edge weights are labeled next to edges accordingly. Assume
all edge susceptancs are 1. The incidence matrix $\mathcal{H}$, its variation
$\mathcal{H}_{o}$, and the weighting diagonal matrix $B$ are:

$\displaystyle\mathcal{H}$
$\displaystyle=\left[\begin{array}[]{ccccc}1&1&0&0&0\\\ 0&0&0&-1&-1\\\
-1&0&-1&1&0\\\ 0&-1&1&0&1\end{array}\right],$ $\displaystyle\mathcal{H}_{o}$
$\displaystyle=\left[\begin{array}[]{lllll}1&1&0&0&0\\\ 0&0&0&0&0\\\
0&0&0&1&0\\\ 0&0&1&0&1\end{array}\right],$ $\displaystyle B$
$\displaystyle=\operatorname{diag}\left\\{1,1,1,1,1\right\\}.$

This example illustrates the specification process of head/tail for every edge
in the context of a DC power flow network. The specification corresponds to
the formulation of the incidence matrix $\mathcal{H}$, and edge susceptances
correspond to the diagonal entries of the diagonal weighting matrix $B$.
$\hfill\square$

Figure 3: A lossless 4-bus power flow network (upper) and its graph
representation (bottom)

To characterize the relation between vertex angles $\theta$ and vertex active
power extractions $P_{v}$ of a lossless network, we consider a distribution of
angles over its vertices, such that the corresponding angles and active power
flow satisfy _vertex power balance_ and _angle difference law_. Hence we again
present the two laws given in (25) and (26) together with the relationship
between active power _through_ edges and the angle differences _across_ the
edge:

$\displaystyle\varphi$ $\displaystyle=\mathcal{H}^{T}\theta,$ (33)
$\displaystyle P_{egde}$ $\displaystyle=-B\varphi,$ (34) $\displaystyle-P_{v}$
$\displaystyle=\mathcal{H}_{o}P_{edge}.$ (35)

Replacing $P_{edge}$ in (35) with its expression (34), and replacing $\varphi$
with its expression in (33), we have:

$\displaystyle P_{v}=\mathcal{H}_{o}B\mathcal{H}^{T}\theta=\mathcal{L}\theta$
(36)

where $\mathcal{L}=\mathcal{H}_{o}B\mathcal{H}^{T}$.

We now formally introduce our definition of the weighted Laplacian matrix.

######  Definition 5 (Weighted Laplacian matrix)

For any directed graph with the incidence matrix $\mathcal{H}$ and the
weighting diagonal matrix $B$, the square matrix
$\mathcal{H}_{o}B\mathcal{H}^{T}$ is defined as the _weighted Laplacian
matrix_ $\mathcal{L}$ of the graph.

The weighted Laplacian matrix features many important properties, which will
be elaborated on in Section 4 and lay the foundation of the characterization
of input-output behavior of $any$ lossless network in Section 5. Every theorem
and lemma introduced in the sequel will be equipped with proof and an example
for readers’ understanding.

###  4.2 Weighted Laplacians of directed graphs

This subsection will present several important properties of the weighted
Laplacian matrix $\mathcal{L}$ of a given directed graph $\mathcal{G}_{d}$.
First, we present a theorem for generalized directed graphs.

###### Theorem 4.1

Consider a directed graph $\mathcal{G}_{d}$ with incidence matrix
$\mathcal{H}$ and its variation $\mathcal{H}_{o}$. Let $B$ be a positive
definite diagonal weighting matrix, of which the dimension is equal to the
number of edges. Then the weighted Laplacian matrix
$\mathcal{L}=\mathcal{H}_{o}B\mathcal{H}^{T}$ has the following properties

  1. 1.

The weighted Laplacian $\mathcal{L}$ is asymmetric, having all eigenvalues
with non-negative real parts, and dependent on the orientation of the graph.

  2. 2.

The weighted Laplacian $\mathcal{L}$ has non-negative diagonal entries, and
non-positive off-diagonal entries.

  3. 3.

The weighted Laplacian $\mathcal{L}$ has zero row sums. The vector $\bm{1}$ is
in the right nullspace of $\mathcal{L}$.

Proof:  For the proof of _Theorem_ 4.1, we aim to prove that our definition of
the weighted Laplacian matrix is strictly equivalent to the conventional
definition: $\mathcal{L}_{conv}\triangleq\mathcal{D}-\mathcal{A}$. Consider a
directed graph $\mathcal{G}_{d}$ with its corresponding incidence matrix
$\mathcal{H}$ and weighting diagonal matrix $B$. Entries $[\mathcal{L}]_{ij}$
of our novel definition of the weighted Laplacian matrix $\mathcal{L}$ can be
expressed in:

$\displaystyle\begin{array}[]{l}i\neq
j:[\mathcal{L}]_{ij}\triangleq\left\\{\begin{array}[]{cl}-b_{k},&\text{ if
}\left(v_{i},v_{j}\right)=e_{ij}\in\varepsilon_{d},\\\ &b_{k}\text{ is the
weight on edge }e_{ij}\\\ 0,&\text{ if
}\left(v_{i},v_{j}\right)=e_{ij}\notin\varepsilon_{d}\end{array}\right.\\\ \\\
i=j:[\mathcal{L}]_{ii}\triangleq-\sum_{p=1,p\neq
i}^{n}[\mathcal{L}]_{ip}.\end{array}$ (43)

Now recall the conventional Laplacian matrix definition for a directed graph:
$\mathcal{L}_{conv}\triangleq\mathcal{D}-\mathcal{A}$, where $\mathcal{A}$ is
the adjacency matrix, entries of which have been declared in Section 3.3, and
$\mathcal{D}$ is the diagonal degree matrix. Hence, entries
$[\mathcal{L}_{conv}]_{ij}$ of the conventional Laplacian matrix
$\mathcal{L}_{conv}$ can be expressed as:

$\displaystyle\begin{array}[]{l}i\neq
j:[\mathcal{L}_{conv}]_{ij}\triangleq\left\\{\begin{array}[]{cl}-b_{k},&\text{
if }\left(v_{i},v_{j}\right)=e_{ij}\in\varepsilon_{d},\\\ &b_{k}\text{ is the
weight on edge }e_{ij}\\\ 0,&\text{ if
}\left(v_{i},v_{j}\right)=e_{ij}\notin\varepsilon_{d}\end{array}\right.\\\ \\\
i=j:[\mathcal{L}_{conv}]_{ii}\triangleq-\sum_{p=1,p\neq
i}^{n}[\mathcal{L}_{conv}]_{ip}.\end{array}$ (50)

Observing (43) and (50) it is evident that for a directed weighted graph
$\mathcal{G}_{d}$, our definition of the weighted Laplacian:
$\mathcal{H}_{o}B\mathcal{H}^{T}$ is strictly equivalent to the conventional
definition: $\mathcal{D}-\mathcal{A}$. Since $\mathcal{L}_{conv}$ is known to
be asymmetric, having all eigenvalues with non-negative real parts, we
conclude the proof of _Theorem_ 4.1.1.

Since $b_{k}$ is always positive as defined in Section 4.1, off-diagonal
entries of $\mathcal{L}$ are always non-positive. Observing the definition for
diagonal entries of $[\mathcal{L}]_{ii}$ in (43), it is evident that
$\mathcal{L}$ has non-negative diagonal entries and zero row sums. Hence the
proofs of _Theorem_ 4.1.2 and _Theorem_ 4.1.3 are concluded. $\blacksquare$

_Example_ For the directed graph in Fig. 3 (bottom), we assign edge weights
$\left\\{b_{1},b_{2},b_{3},b_{4},b_{5}\right\\}$ as
$\left\\{1,2,3,4,5\right\\}$. Then the incidence matrix $\mathcal{H}$, its
variation $\mathcal{H}_{o}$, the diagonal matrix $B$, its weighted Laplacian
$\mathcal{L}$ and its eigenvalues are:

$\displaystyle\begin{array}[]{rlrl}\mathcal{H}&=\left[\begin{array}[]{ccccc}1&1&0&0&0\\\
0&0&0&-1&-1\\\ -1&0&-1&1&0\\\
0&-1&1&0&1\end{array}\right],&\mathcal{H}_{o}=\left[\begin{array}[]{ccccc}1&1&0&0&0\\\
0&0&0&0&0\\\ 0&0&0&1&0\\\ 0&0&1&0&1\end{array}\right],\\\ \\\
B&=\left[\begin{array}[]{ccccc}1&0&0&0&0\\\ 0&2&0&0&0\\\ 0&0&3&0&0\\\
0&0&0&4&0\\\
0&0&0&0&5\end{array}\right],&\mathcal{L}=\left[\begin{array}[]{cccc}3&0&-1&-2\\\
0&0&0&0\\\ 0&-4&4&0\\\ 0&-5&-3&8\end{array}\right],\end{array}$ (71)
$\displaystyle\operatorname{eig}(\mathcal{L})$ $\displaystyle=\\{3,8,4,0\\}.$

Correspondingly the adjacency matrix $\mathcal{A}$, the degree matrix
$\mathcal{D}$, and its conventional Laplacian matrix $\mathcal{L}_{conv}$ are:

$\displaystyle\mathcal{A}$
$\displaystyle=\left[\begin{array}[]{llll}0&0&1&2\\\ 0&0&0&0\\\ 0&4&0&0\\\
0&5&3&0\end{array}\right],\quad\mathcal{D}=\left[\begin{array}[]{llll}3&0&0&0\\\
0&0&0&0\\\ 0&0&4&0\\\ 0&0&0&8\end{array}\right],\quad$ (80)
$\displaystyle\mathcal{L}_{\text{conv }}$
$\displaystyle=\left[\begin{array}[]{cccc}3&0&-1&-2\\\ 0&0&0&0\\\ 0&-4&4&0\\\
0&-5&-3&8\end{array}\right].$ (85)

In this example, it holds that
$\mathcal{D}-\mathcal{A}=\mathcal{H}_{o}B\mathcal{H}^{T}$. This example
presents that for a given directed graph, our definition of the Laplacian
matrix is strictly equivalent to the conventional definition and that the
Laplacian possesses all properties as stated in _Theorem_ 4.1. $\hfill\square$

We then introduce our lemmas on the properties of the weighted Laplacians of
different classes of directed graphs.

Before continuing, we recall the definition for _reachable subset_ and _Lemma_
3.2 in [15] on the existence of Schur complement (with notations changed to
match this paper) for future reference:

######  Definition 6 (Reachable subset, T. Sugiyama and K. Sato [15])

Let $\mathcal{G}_{d}=(\mathcal{V},\varepsilon_{d},\mathcal{H})$ be a directed
and weighted graph with diagonal weighting matrix $B$ and
$\mathcal{V}_{\alpha}\subset\mathcal{V}$ be a proper subset of vertices with
$|\mathcal{V}_{\alpha}|\geq 2$.
$\mathcal{V}_{{\alpha}^{c}}=\mathcal{V}\setminus\mathcal{V}_{\alpha}$. We
refer to $\mathcal{V}_{\alpha}\subset\mathcal{V}$ as a _reachable subset_ of
$\mathcal{G}_{d}$ if for any $v_{i}\in\mathcal{V}_{\alpha^{c}}$, there exist a
vertex $v_{j}\in\mathcal{V}_{\alpha}$ and a path in $\mathcal{G}_{d}$ from
$v_{i}$ to $v_{j}$.

######  Lemma 4.2 (Existence of Schur complement, T. Sugiyama and K. Sato
[15])

Let $\mathcal{G}_{d}=(\mathcal{V},\varepsilon_{d},\mathcal{H})$ be a directed
and weighted graph with diagonal weighting matrix $B$ and
$\mathcal{V}_{\alpha}\subset\mathcal{V}$ be a proper subset of vertices with
$|\mathcal{V}_{\alpha}|\geq 2$.
$\mathcal{V}_{{\alpha}^{c}}=\mathcal{V}\setminus\mathcal{V}_{\alpha}$. Then,
the Schur complement of $\mathcal{L}$ with respect to the sub-matrix
consisting of columns and rows corresponding to vertices
$\mathcal{V}_{\alpha}$ exists if and only if $\mathcal{V}_{\alpha}$ is a
reachable subset of $\mathcal{G}_{d}$.

###### Lemma 4.3

If the graph $\mathcal{G}_{d}$ is strongly-connected, then

  1. 1.

All diagonal entries of $\mathcal{L}$ are positive.

  2. 2.

All Schur complements of $\mathcal{L}$ exist.

Proof:

  1. 1.

For every vertex $v_{i}\in\mathcal{V}$ there exits at least one edge of which
$v_{i}$ is the head, featuring a negative $[\mathcal{L}]_{ij},i\neq j$,
therefore all diagonal entries $[\mathcal{L}]_{ii}$ are positive. Hence the
proof for _Lemma_ 4.3.1 is concluded.

  2. 2.

Schur complements of $\mathcal{L}$ with respect to sub-matrices consisting of
rows and columns corresponding to $\mathcal{V}_{\alpha}$ exist for any vertex
subset $\mathcal{V}_{\alpha}$. In the case of a strong-connected graph, any
vertex subset $\mathcal{V}_{\alpha}$ is always a _reachable subset_ to
$\mathcal{V}_{{\alpha}^{c}}$. Hence by referring to _Lemma_ 4.2 we conclude
the proof for _Lemma_ 4.3.2.

$\blacksquare$

Figure 4: Illustration of Kron reduction to a strongly-connected graph (Left:
original graph. Right: reduced graph with vertices $4,5$ eliminated). Edge
weights are omitted for simplicity.

_Example_ Consider a strongly-connected graph in Fig. 4. Assume all edge
weights are 1 for simplicity. The weighted Laplacian of the original graph is:

$\displaystyle\mathcal{L}=\left[\begin{array}[]{ccccc}2&0&-1&0&-1\\\
0&1&0&-1&0\\\ -1&0&2&-1&0\\\ 0&-1&0&2&-1\\\ 0&0&-1&-1&2\end{array}\right].$
(91)

All diagonal entries of $\mathcal{L}$ are positive, and all Schur complements
of $\mathcal{L}$ with respect to any sub-matrix corresponding to
$\mathcal{V}_{\alpha}$ exist. In Fig. 4, vertices $4,5$ are eliminated during
the reduction. The corresponding Schur complement is $\mathcal{L}_{red}$:

$\displaystyle\mathcal{L}_{\text{red
}}=\left[\begin{array}[]{ccc}2&-0.333&-1.667\\\ 0&0.333&-0.333\\\
-1&-0.667&1.667\end{array}\right].$ (95)

The reduced weighted Laplacian $\mathcal{L}_{red}$ corresponds to the reduced
graph in Fig. 4 (right). This example illustrates that all diagonal entries of
the weighted Laplacian matrix $\mathcal{L}$ corresponding to a strongly-
connected graph $\mathcal{G}_{d}$ are positive. Furthermore, with respect to
the sub-matrix consisting of rows and columns corresponding to any chosen
vertex subset, the Schur complement of the weighted Laplacian exits.
$\hfill\square$

Next we introduce the properties of the weighted Laplacian of a quasi-
strongly-connected graph.

###### Remark 3

For readers’ understanding, we use notations _retained vertices_
$\mathcal{V}_{\alpha}$ and _eliminated vertices_ $\mathcal{V}_{\alpha^{c}}$
which shall be formally introduced in Section 5.1 here in _Lemma_ 4.4. The
Schur complement of $\mathcal{L}$ stated in _Lemma_ 4.4 is with respect to the
sub-matrix consisting of rows and columns corresponding to _retained
vertices_.

###### Lemma 4.4

If the graph $\mathcal{G}_{d}$ is quasi-strongly-connected, and
$\mathcal{G}_{d}$ consists of _sink_ vertices, then the following statements
hold.

  1. 1.

The diagonal entries of $\mathcal{L}$ corresponding to _sink_ vertices are
$0$, and all other diagonal entries are positive.

  2. 2.

Consider the Schur complement of $\mathcal{L}$ with respect to the sub-matrix
consisting of rows and columns corresponding to _retained vertices_
$\mathcal{V}_{\alpha}$. The Schur complement exists if and only if the subset
of _retained vertices_ includes the entire _sink_ vertices.

Proof:

  1. 1.

Since _sink_ vertices are vertices that are tails of all edges connected to
them, every other vertex not being a _sink_ has a positive out-degree. The
diagonal entries of $\mathcal{L}$ indicate out-degrees of corresponding
vertices. Hence the proof for _Lemma_ 4.4.1 is concluded.

  2. 2.

For the proof of _Lemma_ 4.4.2, we first prove that the Schur complement
exists if the subset of _retained vertices_ includes the entire _sink_
vertices. Since the entire _sink_ vertices are included in the subset
$\mathcal{V}_{\alpha}$, there always exists a directed path in
$\mathcal{G}_{d}$ starting at any vertex in $\mathcal{V}_{{\alpha}^{c}}$ and
ending at a _sink_ vertex in $\mathcal{V}_{\alpha}$. Therefore
$\mathcal{V}_{\alpha}$ is always a _reachable subset_ of $\mathcal{G}_{d}$ for
$\mathcal{V}_{{\alpha}^{c}}$. According to _Lemma_ 4.2, the Schur complement
exists if the subset of _retained vertices_ includes the entire _sink_
vertices. Hence we conclude the proof for the first part of _Lemma_ 4.4.2.

We then prove that the Schur complement does not exist if the subset of
_retained vertices_ does not include the entire _sink_ vertices. Since _sink_
vertices are vertices that are tails of all edges connected to them, there
exists no directed path in $\mathcal{G}_{d}$ starting at one vertex of
$\mathcal{V}_{{\alpha}^{c}}$ and ending at any _sink_ vertex of
$\mathcal{V}_{\alpha}$. Therefore, $\mathcal{V}_{\alpha}$ is never a
_reachable subset_ of $\mathcal{G}_{d}$ for $\mathcal{V}_{{\alpha}^{c}}$.
Referring to _Lemma_ 4.2, the Schur complement does not exist if the subset of
_retained vertices_ does not include the entire _sink_ vertices. Hence the
proof for _Lemma_ 4.4.2 is concluded. Hereby we can claim that the Schur
complement of $\mathcal{L}$ with respect to the sub-matrix consisting of rows
and columns corresponding to _retained vertices_ $\mathcal{V}_{\alpha}$ exists
if and only if the subset of _retained vertices_ includes the entire _sink_
vertices.

$\blacksquare$

_Example_ For the quasi-strongly-connected graphs in Fig. 5 (left), assuming
all edge weights are 1 for simplicity, the weighted Laplacian
$\mathcal{L}_{acy}$ of the acyclic graph and the weighted Laplacian
$\mathcal{L}_{cyc}$ of the cyclic graph are:

$\displaystyle\mathcal{L}_{acy}$
$\displaystyle=\left[\begin{array}[]{cccccc}2&0&-1&0&-1&0\\\ 0&0&0&0&0&0\\\
0&0&1&-1&0&0\\\ 0&-1&0&1&0&0\\\ 0&0&-1&0&2&-1\\\
0&-1&0&0&0&1\end{array}\right],\quad$

$\displaystyle\mathcal{L}_{cyc}$
$\displaystyle=\left[\begin{array}[]{ccccc}2&0&-1&0&-1\\\ 0&0&0&0&0\\\
0&0&1&-1&0\\\ 0&-1&0&2&-1\\\ 0&0&-1&0&1\end{array}\right].$ (101)

All diagonal entries of both $\mathcal{L}_{acy}$ and $\mathcal{L}_{cyc}$
except for the _boundary vertex_ $2$ are positive. Except for the Schur
complement of sub-matrix corresponding to the _boundary vertex_ $2$, all the
other Schur complements of $\mathcal{L}$ exist. In Fig. 5, all _interior
vertices_ are eliminated during the reduction ($3,4,5,6$ for the upper graph,
$3,4,5$ for the bottom graph). The corresponding Schur complements are
$\mathcal{L}_{acy\;red}$ and $\mathcal{L}_{cyc\;red}$:

$\displaystyle\mathcal{L}_{acy\;red}=\left[\begin{array}[]{cc}2&-2\\\
0&0\end{array}\right],\quad\mathcal{L}_{cyc\;red}=\left[\begin{array}[]{cc}2&-2\\\
0&0\end{array}\right].$ (106)

This example illustrates that except for the diagonal entries corresponding to
_sink_ vertices, all other diagonal entries of the weighted Laplacian
$\mathcal{L}$ of a quasi-strongly-connected graph $\mathcal{G}_{d}$ are
positive (both for cyclic and acyclic graphs). It also illustrates that the
Schur complement of $\mathcal{L}$ with respect to sub-matrix consisting of
rows and columns corresponding to vertices (of which the subset includes the
entire _sink_ vertices) exists (both for cyclic and acyclic graphs).
$\hfill\square$

###  4.3 Directed graphs corresponding to weighted Laplacian matrices

Figure 5: Illustration of Kron reduction to an acyclic quasi-strongly-
connected graph (upper) and a cyclic quasi-strongly-connected graph (bottom).
Edge weights are omitted for simplicity. _Boundary vertices_ are marked in
red. Figure 6: Example of a directed graph corresponding to the Laplacian
matrix given in _Theorem_ 4.5 (edge weights marked next to edges)

In this section, we will present that there exist directed graphs
corresponding to given weighted Laplacians and reduced weighted Laplacians. We
will also present that certain properties of the corresponding graph are
preserved during the reduction process.

###### Theorem 4.5

Consider an asymmetric matrix $\mathcal{L}$ having all eigenvalues with non-
negative real parts, non-negative diagonal entries, non-positive off-diagonal
entries, and zero row sums. Then

  1. 1.

$\mathcal{L}$ corresponds to the Laplacian matrix of a directed weighted
graph.

  2. 2.

$\mathcal{L}$ can be written as $\mathcal{L}=\mathcal{H}_{o}B\mathcal{H}^{T}$,
with $\mathcal{H}$ the incidence matrix of the corresponding graph,
$\mathcal{H}_{o}$ being the appointed variation of $\mathcal{H}$, and $B$ a
positive definite diagonal matrix of the corresponding graph.

Proof:

  1. 1.

Consider _Theorem_ 4.5 as the reverse statement of _Theorem_ 4.1. Then for
every asymmetric matrix $\mathcal{L}$ with properties stated in _Theorem_ 4.5,
there exists a weighted directed graph corresponding to it.

  2. 2.

The matrix $\mathcal{L}$ can be written as
$\mathcal{L}=\mathcal{D}-\mathcal{A}$, where $\mathcal{D}$ is the graph’s
degree matrix and $\mathcal{A}$ is the graph’s adjacency matrix. Recall that
in the proof for _Theorem_ 4.1, we proved that
$\mathcal{D}-\mathcal{A}=\mathcal{H}_{o}B\mathcal{H}^{T}$. Hence we can
declare that $\mathcal{L}$ can be written as
$\mathcal{L}=\mathcal{H}_{o}B\mathcal{H}^{T}$ with $\mathcal{H}$ the incidence
matrix of the corresponding graph, $\mathcal{H}_{o}$ being the appointed
variation of $\mathcal{H}$, and $B$ a positive definite diagonal matrix of the
corresponding graph.

$\blacksquare$

_Example_ For the following weighted asymmetric Laplacian matrix
$\mathcal{L}$, there exists a directed graph corresponding to it; see Fig. 6.

$\displaystyle\mathcal{L}=\left[\begin{array}[]{cccccccc}3&0&0&0&-1&-2&0&0\\\
0&3&0&0&-3&0&0&0\\\ 0&0&4&0&0&-4&0&0\\\ 0&0&0&0&0&0&0&0\\\
0&0&0&0&11&-5&-6&0\\\ 0&0&0&0&0&7&0&-7\\\ 0&0&0&-8&0&0&8&0\\\
0&0&0&-9&0&0&-10&19\end{array}\right].$

The corresponding incidence matrix $\mathcal{H}$ and the diagonal matrix $B$
are:

$\displaystyle\mathcal{H}$
$\displaystyle=\left[\begin{array}[]{cccccccccc}1&1&0&0&0&0&0&0&0&0\\\
0&0&0&1&0&0&0&0&0&0\\\ 0&0&0&0&1&0&0&0&0&0\\\ 0&0&0&0&0&0&0&0&-1&-1\\\
-1&0&1&-1&0&1&0&0&0&0\\\ 0&-1&-1&0&-1&0&1&0&0&0\\\ 0&0&0&0&0&-1&0&-1&1&0\\\
0&0&0&0&0&0&-1&1&0&1\end{array}\right],$ $\displaystyle B$
$\displaystyle=\operatorname{diag}\left\\{1,2,5,3,4,6,7,10,8,9\right\\}.$

This example illustrates that an asymmetric matrix with the properties stated
in _Theorem_ 4.5 always corresponds to a weighted directed graph and can be
written as $\mathcal{L}=\mathcal{H}_{o}B\mathcal{H}^{T}$ with edge directions
encoded in the incidence matrix $\mathcal{H}$, edge weights encoded in the
weighting diagonal matrix $B$. $\hfill\square$

Figure 7: Strongly-connected graphs corresponding to the weighted Laplacians
before and after reduction (edge weights are omitted for simplicity)

Next we present theorems corresponding to _Theorem_ 4.5 but in the case of
graphs being strongly-connected and quasi-strongly-connected.

###### Theorem 4.6

Suppose the corresponding graph $\mathcal{G}_{d}$ of the Laplacian matrix
$\mathcal{L}=\mathcal{H}_{o}B\mathcal{H}^{T}$ is strongly-connected. Then
every Schur complement (if existing) of $\mathcal{L}$ can be written as
$\bar{\mathcal{H}}_{o}\bar{B}\bar{\mathcal{H}}^{T}$, with $\bar{B}$ a positive
definite diagonal matrix, and $\bar{\mathcal{H}}$ the incidence matrix of a
strongly-connected directed graph $\bar{\mathcal{G}_{d}}$.

Figure 8: Sub-graph consisting of the eliminated vertex $v_{k}$ and all of its
adjacent vertices

Proof:  From _Remark_ 1 we know that _block-by-block Kron reduction_ is
strictly equivalent to _iterative Kron reduction_ regarding reduction results.
For the proof of _Theorem_ 4.6, first, we consider our Kron reduction as a
sequence of _iterative Kron reduction_.

For each iterative step, we focus on the sub-graph consisting of the
eliminated vertex $v_{k}$ and all of its adjacent vertices. For a better
illustration without loss of generality, consider the sub-graph given in Fig.
8 as an example. Adjacent vertices of $v_{k}$ are $v_{i}$, $v_{j}$, and
$v_{m}$. The sub-graph before reduction is associated with the adjacency
matrix $\mathcal{A}_{sub}$ and the corresponding weighted Laplacian
$\mathcal{L}_{red}$:

$\mathcal{A}_{sub}=\left[\begin{array}[]{cccc}0&b_{ik}&0&0\\\ 0&0&b_{kj}&0\\\
0&0&0&0\\\
0&b_{mk}&0&0\end{array}\right],\mathcal{L}_{sub}=\left[\begin{array}[]{cccc}b_{ik}&-b_{ik}&0&0\\\
0&b_{kj}&-b_{kj}&0\\\ 0&0&0&0\\\ 0&-b_{mk}&0&b_{mk}\end{array}\right]$

where non-zero entries in the adjacency matrix $\mathcal{A}_{sub}$ denote the
edge weights on the edges from $v_{i}$ to $v_{j}$.

In the unreduced sub-graph in Fig. 8, there are two nonzero walk products:
$(\mathcal{A}_{sub}^{2})_{ij}$ and $(\mathcal{A}_{sub}^{2})_{mj}$ which are
expressed in:

$\begin{array}[]{l}\left(\mathcal{A}_{sub}^{2}\right)_{ij}=\left[\mathcal{A}_{sub}\right]_{ik}\left[\mathcal{A}_{sub}\right]_{kj}=b_{ik}b_{kj}\neq
0,\\\ \left(\mathcal{A}_{sub}^{2}\right)_{mj}=\left[\mathcal{A}_{\text{sub
}}\right]_{mk}\left[\mathcal{A}_{\text{sub }}\right]_{kj}=b_{mk}b_{kj}\neq
0.\end{array}$

By decomposing the weighted Laplacian $\mathcal{L}_{sub}$ as
$\left[\begin{array}[]{cc}\mathcal{L}_{sub\\{i,j,m\\},\\{i,j,m\\}}&\mathcal{L}_{sub\\{i,j,m\\},\\{k\\}}\\\
\mathcal{L}_{sub\\{k\\},\\{i,j,m\\}}&{\left[\mathcal{L}_{sub}\right]_{kk}}\end{array}\right]$
where
$\mathcal{L}_{sub\\{i,j,m\\},\\{i,j,m\\}}=\left[\begin{array}[]{ccc}b_{ik}&0&0\\\
0&0&0\\\ 0&0&b_{mk}\end{array}\right]$,
$\mathcal{L}_{sub\\{i,j,m\\},\\{k\\}}=\left[\begin{array}[]{c}-b_{ik}\\\ 0\\\
-b_{mk}\end{array}\right]$, $\left[\mathcal{L}_{sub}\right]_{kk}=b_{kj}$, and
$\mathcal{L}_{sub\\{k\\},\\{i,j,m\\}}=\left[\begin{array}[]{lll}0&-b_{kj}&0\end{array}\right]$,
the iterative Kron reduction eliminating vertex $v_{k}$ can be formulated as
the Schur complement of $\mathcal{L}_{sub}$ with respect to
$[\mathcal{L}_{sub}]_{kk}$:

$\displaystyle\mathcal{L}_{sub-red}$
$\displaystyle=\mathcal{L}_{sub\\{i,j,m\\},\\{i,j,m\\}}-\mathcal{L}_{sub\\{i,j,m\\},\\{k\\}}(\left[\mathcal{L}_{sub}\right]_{kk})^{-1}\mathcal{L}_{sub\\{k\\},\\{i,j,m\\}}$
$\displaystyle=\left[\begin{array}[]{ccc}b_{ik}&-b_{ik}&0\\\ 0&0&0\\\
0&-b_{mk}&b_{mk}\end{array}\right]$ (117)

The reduced adjacency matrix $\mathcal{A}_{sub-red}$ corresponding to the
reduced weighted Laplacian is:

$\displaystyle\mathcal{A}_{\text{sub-red
}}=\left[\begin{array}[]{ccc}0&b_{ik}&0\\\ 0&0&0\\\
0&b_{mk}&0\end{array}\right].$ (121)

It is obvious that in the reduced adjacency matrix, there are two nonzero
entries $[\mathcal{A}_{sub-red}]_{ij}$ and $[\mathcal{A}_{sub-red}]_{mj}$
which means that there exists a directed path from $v_{i}$ to $v_{j}$ and a
directed path from $v_{m}$ to $v_{j}$. Non-zero walk products remain non-zero
during each step of the iterative Kron reduction, hence non-zero walk products
remain non-zero after the iterative Kron reduction. Therefore we can claim
that non-zero walk products remain non-zero after the block-by-block Kron
reduction. In other words, there exists a directed path from $v_{i}$ to
$v_{j}$ in the reduced graph if there exists a directed path from $v_{i}$ to
$v_{j}$ in the original graph.

In a strongly-connected graph there exists at least one directed path for
every vertex to reach any other vertex in the graph. Hence there exists at
least one directed path for every vertex to reach any other vertex in the
reduced graph. Therefore, the reduced graph is again a strongly-connected
graph. $\blacksquare$

_Example_ Consider the corresponding graph $\mathcal{G}_{d}$ of the Laplacian
in Fig. 7 (left). The weighted Laplacian $\mathcal{L}$ of the graph is:

$\displaystyle\mathcal{L}=\left[\begin{array}[]{cccc}1&-1&0&0\\\ 0&1&-1&0\\\
0&0&1&-1\\\ -1&0&0&1\end{array}\right].$ (126)

The reduced Laplacian $\mathcal{L}_{red}$ and its corresponding incidence
matrix $\bar{\mathcal{H}}$, variation of the incidence matrix
$\bar{\mathcal{H}_{o}}$ and diagonal weighting matrix $\bar{B}$ are:

$\displaystyle\mathcal{L}_{\text{red }}$
$\displaystyle=\left[\begin{array}[]{ccc}1&-1&0\\\ 0&1&-1\\\
-1&0&1\end{array}\right],\bar{\mathcal{H}}=\left[\begin{array}[]{ccc}1&0&-1\\\
-1&1&0\\\ 0&-1&1\end{array}\right],$ (133)
$\displaystyle\bar{\mathcal{H}}_{o}$
$\displaystyle=\left[\begin{array}[]{lll}1&0&0\\\ 0&1&0\\\
0&0&1\end{array}\right],\quad\quad\bar{B}=\operatorname{diag}\\{1,1,1\\}.$
(137)

The reduced graph in Fig. 7 (right) corresponding to the reduced incidence
matrix $\bar{\mathcal{H}}$ is again a strongly-connected graph. This example
illustrates that every Schur complement of the weighted Laplacian
$\mathcal{L}$ corresponding to a strongly-connected graph $\mathcal{G}_{d}$ is
again a weighted Laplacian matrix $\mathcal{L}_{red}$, which again corresponds
to a strongly-connected graph. $\hfill\square$

###### Theorem 4.7

Suppose the corresponding graph $\mathcal{G}_{d}$ of the Laplacian matrix
$\mathcal{L}=\mathcal{H}_{o}B\mathcal{H}^{T}$ is quasi-strongly-connected.
Then every Schur complement (if existing) of $\mathcal{L}$ can be written as
$\bar{\mathcal{H}}_{o}\bar{B}\bar{\mathcal{H}}^{T}$, with $\bar{B}$ a positive
definite diagonal matrix, and $\bar{\mathcal{H}}$ the incidence matrix of a
quasi-strongly-connected directed graph $\bar{\mathcal{G}_{d}}$.

Proof:  We have proved that for any directed graph $\mathcal{G}_{d}$, there
exists a directed path from $v_{i}$ to $v_{j}$ in the reduced graph if there
exists a directed path from $v_{i}$ to $v_{j}$ in the original graph in the
proof for _Theorem_ 4.6. In a quasi-strongly-connected graph, there exists at
least a _source_ vertex in the unreduced graph. Since _source_ vertices are
_boundary vertices_ which will not be eliminated during Kron reduction, there
exists a directed path for every other vertex (except for _sink_) to start at
_sink_ vertex and end at the very vertex in the reduced graph, hence
concluding the proof for _Theorem_ 4.7. $\blacksquare$

_Example_ Consider the corresponding quasi-strongly-connected graphs in Fig. 9
of two given Laplacians $\mathcal{L}_{1}$ and $\mathcal{L}_{2}$:

$\displaystyle\mathcal{L}_{1}$
$\displaystyle=\left[\begin{array}[]{cccccc}2&0&-1&0&-1&0\\\ 0&0&0&0&0&0\\\
0&0&1&-1&0&0\\\ 0&-1&0&1&0&0\\\ 0&0&-1&0&2&-1\\\
0&-1&0&0&0&1\end{array}\right],\quad$ (144) $\displaystyle\mathcal{L}_{2}$
$\displaystyle=\left[\begin{array}[]{ccccc}2&0&-1&0&-1\\\ 0&0&0&0&0\\\
0&0&1&-1&0\\\ 0&-1&0&2&-1\\\ 0&0&-1&0&1\end{array}\right].$ (150)

The reduced Laplacians $\mathcal{L}_{1\;red}$ and $\mathcal{L}_{2\;red}$, the
corresponding incidence matrices $\bar{\mathcal{H}}_{1}$ and
$\bar{\mathcal{H}}_{2}$, their variations $\bar{\mathcal{H}}_{1o}$ and
$\bar{\mathcal{H}}_{2o}$ and corresponding diagonal weighting matrices
$\bar{B}_{1}$ and $\bar{B}_{2}$ are:

$\displaystyle\begin{array}[]{ccc}\mathcal{L}_{1\text{ red
}}=\left[\begin{array}[]{cccc}2&-0.5&-1.5&0\\\ 0&0&0&0\\\ 0&0&1&-1\\\
0&-1&0&1\end{array}\right],&\mathcal{L}_{2\text{ red
}}=\left[\begin{array}[]{cccc}2&0&-2&0\\\ 0&0&0&0\\\ 0&0&1&-1\\\
0&-1&-1&2\end{array}\right],\\\ \\\
\overline{\mathcal{H}}_{1}=\left[\begin{array}[]{cccc}1&0&0&1\\\ 0&0&-1&-1\\\
-1&1&0&0\\\
0&-1&1&0\end{array}\right],&\overline{\mathcal{H}}_{2}=\left[\begin{array}[]{cccc}1&0&0&0\\\
0&0&0&-1\\\ -1&1&-1&0\\\ 0&-1&1&1\end{array}\right],\\\ \\\
\overline{\mathcal{H}}_{1o}=\left[\begin{array}[]{cccc}1&0&0&1\\\ 0&0&0&0\\\
0&1&0&0\\\
0&0&1&0\end{array}\right],&\overline{\mathcal{H}}_{2o}=\left[\begin{array}[]{cccc}1&0&0&0\\\
0&0&0&0\\\ 0&1&0&0\\\ 0&0&1&1\end{array}\right],\\\ \\\
\bar{B}_{1}=\operatorname{diag}\\{1.5,1,1,0.5\\},&\bar{B}_{2}=\operatorname{diag}\\{2,1,1,1\\}.\end{array}$

The reduced graphs (Fig. 9, right) corresponding to the reduced Laplacians are
still quasi-strongly-connected. This example illustrates that every existing
Schur complement of the weighted Laplacian $\mathcal{L}$ corresponding to a
quasi-strongly-connected graph $\mathcal{G}_{d}$ is again a weighted Laplacian
matrix $\mathcal{L}_{red}$, which again corresponds to a quasi-strongly-
connected graph. $\hfill\square$

Figure 9: Illustration of reduced graphs corresponding to Schur complements of
two given Laplacians (Upper: $\mathcal{G}_{d}$ of $\mathcal{L}_{1}$ and
$\mathcal{G}_{d\;red}$ of $\mathcal{L}_{1\;red}$. Bottom: $\mathcal{G}_{d}$ of
$\mathcal{L}_{2}$ and $\mathcal{G}_{d\;red}$ of $\mathcal{L}_{2\;red}$). Edge
weights are omitted for simplicity.

##  5 Kron reduction to power flow networks

In this section, we present the graph-theoretic analysis of the Kron reduction
process on DC power flow networks.

###  5.1 Vertex classification

Figure 10: Illustration of vertex classification,
$\mathcal{V}_{b}\cap\mathcal{V}_{i}=\mathcal{V}$ (upper),
$\mathcal{V}_{\alpha}\cap\mathcal{V}_{\alpha^{c}}=\mathcal{V},\mathcal{V}_{\alpha^{c}}\subseteq\mathcal{V}_{i}$
(bottom)

In this subsection we will identify a set of vertices that are actually
eliminated and a set of vertices that are actually retained during the Kron
reduction process. First, recall that for a given graph $\mathcal{G}_{d}$, we
identified a subset $\mathcal{V}_{b}\subset\mathcal{V}$ as _boundary vertices_
and a subset $\mathcal{V}_{i}=\mathcal{V}\setminus\mathcal{V}_{b}$ as
_interior vertices_ in Section 4.1. Boundary vertices are vertices that cannot
be eliminated. Interior vertices are vertices that can be eliminated. Although
all _interior vertices_ can be eliminated, there are times during Kron
reduction when some of the interior vertices are to be retained. Hereby we
further identify a subset termed _eliminated vertices_
$\mathcal{V}_{\alpha^{c}}\subseteq\mathcal{V}_{i}$ being the vertices that are
actually eliminated during the Kron reduction process, and the subset termed
_retained vertices_
$\mathcal{V}_{\alpha}=\mathcal{V}\setminus\mathcal{V}_{\alpha^{c}}$ being the
vertices that are actually retained during reduction. See Fig. 10 for a
diagrammatic illustration of vertex classification.

Recall the power-angle equation (36) in Section 4.1. Decompose $P_{v}$ as
$\left[\begin{array}[]{c}P_{v\alpha}\\\ P_{v\alpha^{c}}\end{array}\right]$
with $P_{v\alpha}$ corresponding to active power extractions at retained
vertices and $P_{v\alpha^{c}}$ corresponding to active power extractions at
eliminated vertices. Decompose $\theta$ as
$\left[\begin{array}[]{c}\theta_{\alpha}\\\
\theta_{\alpha^{c}}\end{array}\right]$ with $\theta_{\alpha}$ corresponding to
angles at retained vertices and $\theta_{\alpha^{c}}$ angles at eliminated
vertices. Further decompose $\mathcal{L}$ as
$\left[\begin{array}[]{ll}\mathcal{L}_{\alpha\alpha}&\mathcal{L}_{\alpha\alpha^{c}}\\\
\mathcal{L}_{\alpha^{c}\alpha}&\mathcal{L}_{\alpha^{c}\alpha^{c}}\end{array}\right]$
with subblocks being composed of columns and rows corresponding retained and
eliminated vertices respectively. Then (36) can be partitioned as

$\displaystyle\left[\begin{array}[]{c}P_{v\alpha}\\\
P_{v\alpha^{c}}\end{array}\right]=\left[\begin{array}[]{ll}\mathcal{L}_{\alpha\alpha}&\mathcal{L}_{\alpha\alpha^{c}}\\\
\mathcal{L}_{\alpha^{c}\alpha}&\mathcal{L}_{\alpha^{c}\alpha^{c}}\end{array}\right]\left[\begin{array}[]{c}\theta_{\alpha}\\\
\theta_{\alpha^{c}}\end{array}\right].$ (187)

Gaussian elimination of _eliminated angles_ $\theta_{\alpha^{c}}$ in (187)
gives a reduced network with _retained vertices_ obeying the reduced power
flow equations

$\displaystyle
P_{v\alpha}+\mathcal{L}_{ac}P_{v{\alpha^{c}}}=\mathcal{L}_{red}\theta_{\alpha}$
(188)

where the reduced Laplacian matrix is given by the Schur complement of
$\mathcal{L}$ with respect to _retained vertices_ $\mathcal{V}_{\alpha}$, that
is
$\mathcal{L}_{red}=\mathcal{L}_{\alpha\alpha}-\mathcal{L}_{\alpha\alpha^{c}}\mathcal{L}_{\alpha^{c}\alpha^{c}}^{-1}\mathcal{L}_{\alpha^{c}\alpha}$
and the accompanying matrix
$\mathcal{L}_{ac}=-\mathcal{L}_{\alpha\alpha^{c}}\mathcal{L}_{\alpha^{c}\alpha^{c}}^{-1}$
maps _eliminated active power extractions_ $P_{v{\alpha^{c}}}$ to _retained
active power extractions_
$P_{vred}=P_{v\alpha}+\mathcal{L}_{ac}P_{v{\alpha^{c}}}$ in the reduced
network.

###  5.2 Kron reduction to power flow networks

Following the identification of _retained vertices_ and _eliminated vertices_
in the last section, we formally give the definition of Kron reduction to
power flow networks.

Figure 11: IEEE-3 test feeder and its directed graph representation (boundary
vertices marked in red)

######  Definition 7 (Kron reduction to power flow networks)

Consider a power flow network corresponding to the graph representation
$\mathcal{G}_{d}=(\mathcal{V},\varepsilon_{d},\mathcal{H},B)$. Let
$\mathcal{L}\in\mathbb{R}^{|\mathcal{V}|\times|\mathcal{V}|}$ denote the
weighted Laplacian matrix: $\mathcal{H}_{o}B\mathcal{H}^{T}$ of the graph. Let
$\mathcal{V}_{\alpha}\subset\mathcal{V}$, the _retained vertices_ be a proper
subset of vertices with $|\mathcal{V}_{\alpha}|\geq 2$. (‘Proper’ means that
_boundary vertices_ are always included in $\mathcal{V}_{\alpha}$ following
the classification in Section 5.1.) Then the
$|\mathcal{V}_{\alpha}|\times|\mathcal{V}_{\alpha}|$ dimensional Kron reduced
matrix $\mathcal{L}_{red}$ is defined by the Schur complement of $\mathcal{L}$
with respect to the sub-matrix consisting of rows and columns corresponding to
_retained vertices_ :

$\displaystyle\mathcal{L}_{red}=\mathcal{L}_{\alpha\alpha}-\mathcal{L}_{\alpha\alpha^{c}}\mathcal{L}_{\alpha^{c}\alpha^{c}}^{-1}\mathcal{L}_{\alpha^{c}\alpha},$
(189)

which gives the reduced power flow network with the reduced graph
representation i.e.,
$\bar{\mathcal{G}}_{d}=(\mathcal{V_{\alpha}},\bar{\varepsilon}_{d},\bar{\mathcal{H}},\bar{\mathcal{B}})$,
with
$\mathcal{L}_{red}=\mathcal{L}_{\alpha\alpha}-\mathcal{L}_{\alpha\alpha^{c}}\mathcal{L}_{\alpha^{c}\alpha^{c}}^{-1}\mathcal{L}_{\alpha^{c}\alpha}$.

###### Remark 4

In most cases (most IEEE test feeders) power flow networks are neither
strongly-connected nor quasi-strongly-connected. However, there are several
cases when power flow networks are relatively simple and are quasi-strongly-
connected. See the example of an IEEE-3 test feeder, in Fig. 11. Vertex $1$ is
the _root vertex_ of this quasi-strongly-connected graph.

Next, we discuss sufficient conditions for the existence of Kron reduction to
power flow networks.

######  Lemma 5.1 (Existence of Kron reduction to power flow networks with
quasi-strongly-connected graph representations)

Consider a power flow network corresponding to the quasi-strongly-connected
graph representation
$\mathcal{G}_{d}=(\mathcal{V},\varepsilon_{d},\mathcal{H},B)$ with the
weighted Laplacian $\mathcal{L}=\mathcal{H}_{o}B\mathcal{H}^{T}$. Let
$\mathcal{V}_{\alpha}\subset\mathcal{V}$, the _retained vertices_ be a proper
subset of vertices with $|\mathcal{V}_{\alpha}|\geq 2$. Then Kron reduction
always exists for this network.

Proof:  For a given power flow network corresponding to the quasi-strongly-
connected graph $\mathcal{G}_{d}$ with the weighted Laplacian $\mathcal{L}$,
since $\mathcal{V}_{sink}\in\mathcal{V}_{b}\subset\mathcal{V}_{\alpha}$, Schur
complements of $\mathcal{L}$ with respect to sub-matrices consisting of rows
and columns corresponding to $\mathcal{V}_{\alpha}$ always exist by referring
to _Lemma_ 4.4.3. Therefore, Kron reduction always exists for this network.
Laplacian matrix of the reduced network is given by (189). $\blacksquare$

Figure 12: IEEE-5 test feeder, its directed graph representation (boundary
vertices marked in red), the reduced graph representation, and the restored
reduced network

_Example_ For the quasi-strongly-connected corresponding graph representation
of an IEEE-5 test feeder in Fig. 12, vertex $1$ and vertex $5$ are boundary
vertices, which are included in $\mathcal{V}_{\alpha}$. Kron reduction of this
network eliminates vertex $2$; see Fig. 12. Assume all edge susceptances are
1. The graph of the reduced network is quasi-strongly-connected, which
conforms to _Theorem_ 4.7. The weighted Laplacian $\mathcal{L}$ for the
original network and the weighted Laplacian $\mathcal{L}_{red}$ for the
reduced network are:

$\displaystyle\mathcal{L}=\left[\begin{array}[]{ccccc}2&-1&-1&0&0\\\
0&3&-1&-1&-1\\\ 0&0&1&-1&0\\\ 0&0&0&1&-1\\\
0&0&0&0&0\end{array}\right],\quad\mathcal{L}_{\text{red
}}=\left[\begin{array}[]{ccc}2&-1&-1\\\ 0&3&-3\\\ 0&0&0\end{array}\right].$
(198)

This example illustrates that Kron reduction exists for a lossless DC power
flow network that corresponds to a quasi-strongly-connected graph.
$\hfill\square$

######  Lemma 5.2 (Existence of Kron reduction to generalized power flow
networks)

Consider a generalized power flow network with the graph representation
$\mathcal{G}_{d}=(\mathcal{V},\varepsilon_{d},\mathcal{H},B)$ that consists of
_sink_ vertices and _source_ vertices. Let
$\mathcal{V}_{\alpha}\subset\mathcal{V}$, the _retained vertices_ be a proper
subset of vertices with $|\mathcal{V}_{\alpha}|\geq 2$. Then Kron reduction
always exists for this network.

Proof:  For a given power flow network of which the graph is not quasi-
strongly-connected but still consists of _sink_ vertices and _source_
vertices, since
$\mathcal{V}_{sink}\in\mathcal{V}_{b}\subset\mathcal{V}_{\alpha}$, there
exists a directed path in $\mathcal{G}_{d}$ starting at any vertex in
$\mathcal{V}_{{\alpha}^{c}}$ and ending at a _sink_ vertex in
$\mathcal{V}_{\alpha}$. Therefore $\mathcal{V}_{\alpha}$ is always a
_reachable subset_ of $\mathcal{G}_{d}$ for $\mathcal{V}_{{\alpha}^{c}}$. By
referring to _Lemma_ 4.2, we can declare Schur complements of $\mathcal{L}$
with respect to sub-matrices consisting of rows and columns corresponding to
$\mathcal{V}_{\alpha}$ always exist. The proof for _Lemma_ 5.2 is concluded.
$\blacksquare$

_Example_ For the corresponding graph representation of an IEEE-9 test feeder
in Fig. 13, vertices $1,2,3,5,6,8$ are boundary vertices, which are included
in $\mathcal{V}_{\alpha}$. The graph representation of this network is not
quasi-strongly-connected. Kron reduction of this network eliminates vertex
$4,7$; see Fig. 13. Assume all edge susceptances are 1. The weighted Laplacian
$\mathcal{L}$ for the original network and the weighted Laplacian
$\mathcal{L}_{red}$ for the reduced network are:

$\displaystyle\begin{array}[]{c}\mathcal{L}=\left[\begin{array}[]{ccccccccc}1&0&0&-1&0&0&0&0&0\\\
0&1&0&0&0&0&-1&0&0\\\ 0&0&1&0&0&0&0&0&-1\\\ 0&0&0&2&-1&-1&0&0&0\\\
0&0&0&0&0&0&0&0&0\\\ 0&0&0&0&0&0&0&0&0\\\ 0&0&0&0&-1&0&2&-1&0\\\
0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&-1&0&-1&2\end{array}\right],\quad\mathcal{L}_{\text{red
}}=\left[\begin{array}[]{ccccccc}1&0&0&-0.5&-0.5&0&0\\\ 0&1&0&-0.5&0&-0.5&0\\\
0&0&1&0&0&0&-1\\\ 0&0&0&0&0&0&0\\\ 0&0&0&0&0&0&0\\\ 0&0&0&0&0&0&0\\\
0&0&0&0&-1&-1&2\end{array}\right].\end{array}$ (216)

This example illustrates that Kron reduction exists for a lossless DC power
flow network that corresponds to a weighted directed graph consisting of
_sink_ and _source_ vertices. $\hfill\square$

Figure 13: IEEE-9 test feeder, its directed graph representation (boundary
vertices marked in red), the reduced graph representation, and the restored
reduced network

###  5.3 Input-output behaviors of lossless DC power flow networks

In this subsection, we present how the weighted Laplacian matrix $\mathcal{L}$
and its Kron-reduced form $\mathcal{L}_{red}$ function as I/O mappings for a
lossless power flow system.

###### Theorem 5.3

Consider a lossless DC power flow network with the graph representation
$\mathcal{G}_{d}=(\mathcal{V},\varepsilon_{d},\mathcal{H},B)$ of which
_boundary vertices_ consist of both _sink_ and _source vertices_. The
corresponding weighted Laplacian is
$\mathcal{L}=\mathcal{H}_{o}B\mathcal{H}^{T}$. Then

  1. 1.

The Laplacian $\mathcal{L}$ maps vertex angle vector $\theta$ (input) to
vertex power extraction vector $P_{v}$ (output).

  2. 2.

For any retained vertex angle vector $\theta_{\alpha}$, there exists a unique
$\mathcal{L}_{red}$ such that (188) is satisfied.

  3. 3.

To any weighted directed Laplacian matrix $\mathcal{L}_{red}$ there
corresponds a lossless DC power flow network of which the input-output
behavior is given by the linear map:

$\displaystyle P_{vred}=\mathcal{L}_{red}\theta_{\alpha}.$ (217)

Proof:

  1. 1.

For the proof of _Theorem_ 5.3.1, we aim to show that $\mathcal{L}$ indeed
functions as a mapping from $\theta$ to $P_{v}$. Recall the expression (36),
the statement in _Theorem_ 5.3.1 is evident.

  2. 2.

For the proof of _Theorem_ 5.3.2, we first aim to prove that for any retained
vertex subset, the Schur complement of the reduction always exists. Consider
the directed graph representation $\mathcal{G}_{d}$ corresponding to the given
lossless DC power flow network. Since both _sink_ and _source_ vertices are
boundary vertices, they are not eliminated. Therefore for any vertex
$v_{i}\in\mathcal{V}_{{\alpha}^{c}}$, there exists a directed path in
$\mathcal{G}_{d}$ starting at the very vertex and ending at the _sink_ vertex.
Hence $\mathcal{V}_{{\alpha}}$ is a reachable subset for
$\mathcal{V}_{{\alpha}^{c}}$. By recalling _Lemma_ 4.2, we can declare that
for any retained vertex subset, the Schur complement of the reduction always
exists, which also means that $\mathcal{L}_{\alpha^{c}\alpha^{c}}$ is non-
singular and
$\mathcal{L}_{red}=\mathcal{L}_{\alpha\alpha}-\mathcal{L}_{\alpha\alpha^{c}}\mathcal{L}_{\alpha^{c}\alpha^{c}}^{-1}\mathcal{L}_{\alpha^{c}\alpha}$
exists for (188). Hence we conclude the proof for _Theorem_ 5.3.2.

  3. 3.

Following the proof for _Theorem_ 5.3.2, the left hand side of (188) is
precisely the expression for $P_{red}$. Hence we have
$P_{red}=\mathcal{L}_{red}\theta_{\alpha}$. According to our proof for
_Theorem_ 4.5, the reduced Laplacian $\mathcal{L}_{red}$ corresponds to a
weighted directed graph, from which the reduced lossless DC power flow network
can be restored.

$\blacksquare$

###### Remark 5

An example illustrating _Theorem_ 5.3 will be given in Section 6. In Section 4
we presented several important properties of the weighted Laplacians of
different types of directed graphs. In Section 5 we presented the methodology
of using directed graphs to model lossless power flow networks and the
physical interpretation of the weighted Laplacian. This work can be viewed as
an extension of the work in [6] by A. van der Schaft.

##  6 Numerical results

Figure 14: Graph representation of IEEE-14 test feeder, boundary vertices
marked in red squares

In this section, the IEEE-14 test feeder will be used as a detailed example
for numerical testing; see the weighted graph representation of the IEEE-14
power flow network in Fig. 14. A two-stage reduction process will be adopted.
During the first stage, boundary vertices and vertices that are connected to
boundary vertices via an edge are retained. During Stage II where the
reduction is performed on the reduced result of Stage I, all interior vertices
are to be eliminated. Testing on a modified IEEE RTS-96 test system will also
be presented in order to show the scalability of the proposed reduction
method.

###  6.1 IEEE-14 test feeder

####  6.1.1 Reduction process

The reduction process is detailed as follows:

  1. 1.

Vertex classification: Each bus of the IEEE-14 network corresponds to a vertex
of the graph. Buses that are connected to generators (outside the IEEE-14
network) correspond to _source vertices_. Relatively, buses that are connected
to loadings (outside the IEEE-14 network) correspond to _sink vertices_. Buses
that are connected to both generators and loadings (outside the IEEE-14
network) correspond to _source vertices_ , while we assume the dominant power
flow pattern is active power flowing out of the very buses for simulation
simplicity. All the other buses correspond to _interior vertices_. Sink and
source vertices are marked in red squares, and interior vertices are marked in
black circles. So far we have applied our vertex classification method
proposed in Section 5.1 to the IEEE-14 test feeder.

  2. 2.

Edge direction specification: Each transmission line between two buses
corresponds to a directed edge. Edge directions are indicated by arrows, and
edge weights are marked next to edges. Edge directions are determined by the
‘diodes’ positioning on the transmission lines, which are dictated by the
attributes of the buses on two ends of the transmission line, i.e.,

    1. (a)

In the case of connecting one sink vertex and one interior vertex, the diode
faces toward the sink vertex.

    2. (b)

In the case of connecting one source vertex and one interior vertex, the diode
faces toward the interior vertex.

    3. (c)

In the case of connecting two interior vertices, the diode faces toward the
interior vertex that is connected to the sink vertex.

So far we have defined the incidence matrix $\mathcal{H}$ for the
corresponding weighted directed graph using the proposed specification in
Section 4.1, the numerical results of which are omitted due to page limit.

  3. 3.

Derivation of the weighted Laplacian: For the simplicity of the weighting
diagonal matrix $B$, we assume all edge weights are $1$. So far we can derive
the weighted Laplacian matrix $\mathcal{L}=\mathcal{H}_{o}B\mathcal{H}^{T}$
based on _Definition_ 5 for the corresponding graph.

  4. 4.

Input profile: Since active power flows from buses with high voltage angles to
buses with low voltage angles, we choose the angle profile conforming to the
incidence matrix. We deliberately set each vertex angle to be a small shift
from the reference angle $\alpha$. Phase shifts are in $[-0.6,0.6]$. The
motivation of this treatment is that DC power flow essentially is a
linearization of AC power flow, which takes the small angle difference as one
of its several prerequisites. By limiting phase shifts in $[-0.6,0.6]$, we
manage to keep angle differences smaller than 1.2. See the angle profile
$\theta$ for the unreduced graph in the $3^{rd}$ column of Table 1.

  5. 5.

Output profile: we derive the vertex active power $P_{v}$ based on the
expression given in (36). See the vertex power $P_{v}$ in the $2^{nd}$ column
of Table 1.

  6. 6.

Reduction Stage I: we calculate the reduced weighted Laplacian matrix of the
reduced graph preserving boundary vertices and vertices that are connected to
boundary vertices via an edge using the expression given in (189). We then
calculate the reduced power profile based on the expression given in (217).
See the reduced power $P_{v}^{{}^{\prime}}$ in the $4^{th}$ column of Table 1.
The numerical results conform to _Theorem_ 5.3. See the reduced graph
corresponding to the reduced weighted Laplacian matrix of Stage I in Fig. 15.
The successful delivery of the reduced directed graph conforms to _Lemma_ 5.2.

  7. 7.

Reduction Stage II: we calculate the reduced weighted Laplacian matrix of the
reduced graph eliminating all interior vertices based on the expression given
in (189). We then calculate the reduced power profile based on the expression
given in (217). See the reduced power $P_{v}^{{}^{\prime\prime}}$ in the
$6^{th}$ column of Table 1, and the reduced graph corresponding to the reduced
weighted Laplacian matrix of Stage II in Fig. 16. The reduction results
conform to _Lemma_ 5.2 and _Theorem_ 5.3.

Table 1: Vertex parameters of IEEE-14 test feeder before reduction (column 2,3), after stage I reduction (vertices $3,4,9,10,11$ eliminated) (column 4,5), and after stage II reduction (all interior vertices eliminated) (column 6,7) $\begin{array}[]{ | c | c | c | c | c | c | c | }\hline\cr\text{ Vertex }_{i}&P_{\text{vi }}(p.u.)&\theta_{i}\left({}^{\circ}\right)&P_{\text{vi }}^{{}^{\prime}}(p.u.)&\theta_{i}^{{}^{\prime}}\left({}^{\circ}\right)&P_{\text{vi }}^{{}^{\prime\prime}}(p.u.)&\theta_{i}^{{}^{\prime\prime}}\left({}^{\circ}\right)\\\ \hline\cr 1&0.58&\alpha+0.5271&0.58&\alpha+0.5271&1.98&\alpha+0.5271\\\ \hline\cr 2&1.1&\alpha+0.3371&1.6&\alpha+0.3371&\times&\times\\\ \hline\cr 3&0.1&\alpha-0.0629&\times&\times&\times&\times\\\ \hline\cr 4&0.1&\alpha-0.1629&\times&\times&\times&\times\\\ \hline\cr 5&0.4&\alpha+0.1371&0.6&\alpha+0.1371&\times&\times\\\ \hline\cr 6&0.8&\alpha+0.0371&1.1&\alpha+0.0371&\times&\times\\\ \hline\cr 7&0.7&\alpha+0.1371&1&\alpha+0.1371&\times&\times\\\ \hline\cr 8&0.39&\alpha+0.5271&0.39&\alpha+0.5271&0.99&\alpha+0.5271\\\ \hline\cr 9&0.1&\alpha-0.2629&\times&\times&\times&\times\\\ \hline\cr 10&0.1&\alpha-0.1629&\times&\times&\times&\times\\\ \hline\cr 11&0.1&\alpha-0.0629&\times&\times&\times&\times\\\ \hline\cr 12&0.3&\alpha-0.1629&0.3&\alpha-0.1629&\times&\times\\\ \hline\cr 13&0&\alpha-0.4629&0&\alpha-0.4629&0&\alpha-0.4629\\\ \hline\cr 14&0.1&\alpha-0.3629&0.1&\alpha-0.3629&\times&\times\\\ \hline\cr\end{array}$

####  6.1.2 Results

Figure 15: Reduced IEEE-14 test feeder with vertices 3,4,9,10,11 eliminated
Figure 16: Reduced IEEE-14 test feeder with all interior vertices eliminated

  1. 1.

The lossless power flow network model of the IEEE-14 test feeder in a directed
graph is successfully delivered.

  2. 2.

The proposed weighted Laplacian matrix has been successfully derived from the
directed graph, conforming to _Definition_ 5.

  3. 3.

The vertex angle input profile is suitably chosen to meet the linearization
requirement.

  4. 4.

The active power output profile is derived, showing that the proposed weighted
Laplacian matrix functions as a mapping of system input to output.

  5. 5.

Kron reduction is performed on the built lossless power flow network, of which
the reduced results conform to _Theorem_ 5.3.

  6. 6.

Notice that during stage I, $P_{v}^{{}^{\prime}}$ of boundary vertices also
remain unchanged after the transformation:
$P_{v}^{{}^{\prime}}=P_{v\alpha}+\mathcal{L}_{ac}P_{v{\alpha^{c}}}$. It will
be interesting for future work to look into this matter.

###  6.2 Modified IEEE RTS-96 test system

####  6.2.1 Reduction process

In this example, we take Area $4$ of the modified IEEE RTS-96 test system from
[18] in Fig. 17 as the reduction object. Buses connected to generators,
loadings, and buses in Area 3 are boundary vertices. The remaining vertices
are interior vertices. The corresponding weighted Laplacian matrices of the
original and the reduced graph are omitted due to the page limit. Bus angles
and active power extractions are omitted as well. All interior vertices are
eliminated during the reduction process in Fig. 18.

####  6.2.2 Results

  1. 1.

The directed graph corresponding to Area $4$ of the IEEE RTS-96 test system is
successfully derived.

  2. 2.

The proposed weighted Laplacian matrix is derived based on the directed graph
and is strictly equivalent to the conventionally defined Laplacian matrix,
conforming to _Definition_ 5 and _Theorem_ 4.1.

  3. 3.

Kron reduced network is successfully derived by computing the Schur complement
of the weighted Laplacian matrix.

  4. 4.

The successful delivery of the Kron reduced network validates the scalability
of the proposed reduction method.

Figure 17: Wiring diagram of the modified IEEE RTS-96 test system [18] Figure
18: Kron reduction on Area 4 of the modified IEEE RTS-96 test system

##  7 Conclusions and recommendations

We have studied Kron reduction on directed graphs and on directed power flow
networks. Our work was motivated by the gap in the existing research work
between Kron reduction and its application to directed graphs, and the gap
between Kron reduction and its application to electrical networks. We have
proposed a novel formulation of the weighted Laplacian matrix for a directed
graph in a way that the novel definition is strictly equivalent to the
conventional definition of the weighted Laplacian. We presented a
comprehensive graph-theoretic analysis of Kron reduction to directed graphs.
This analysis led to new physical insights regarding the application of power
flow networks.

Our analysis demands answers to further questions, such as effective
resistance and sensitivity analysis of Kron reduction to directed DC power
flow networks, and Kron reduction to other characteristic electrical networks.
Undirected/directed graphs with complex-valued weights as well for modelling
power networks would be another interesting topic for future research.

## Acknowledgment

The first author would like to thanks EIT InnoEnergy and SENSE, for gaining
the access to Europe’s largest innovation community, including top partners in
business, research, and higher education. The paper presents research outcomes
from the first author’s MSc graduation project. The first author would like to
thank the supervisor team (Dr. Zhiyong Sun and Prof. Siep Weiland) for
stimulating conversations on this topic and for the guidance and effort in
this project.

## References

  * [1] Gabriel Kron.  Tensor Analysis of Networks, volume 146.  John Wiley & Sons, 1939.
  * [2] Austin Armbruster, Mike Gosnell, Bruce McMillin, and Mariesa L Crow.  Power transmission control using distributed max-flow.  In Proceedings of the 29th Annual International Computer Software and Applications Conference (COMPSAC’05), volume 1, pages 256–263. IEEE, 2005.
  * [3] Juraj Kardoš, Drosos Kourounis, and Olaf Schenk.  Two-level parallel augmented Schur complement interior-point algorithms for the solution of security constrained optimal power flow problems.  IEEE Transactions on Power Systems, 35(2):1340–1350, 2019.
  * [4] Ian Dobson.  Voltages across an area of a network.  IEEE Transactions on Power Systems, 27(2):993–1002, 2011.
  * [5] Jan C Willems and Erik I Verriest.  The behavior of resistive circuits.  In Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference, pages 8124–8129. IEEE, 2009.
  * [6] Arjan van der Schaft.  Characterization and partial synthesis of the behavior of resistive circuits at their terminals.  Systems & Control Letters, 59(7):423–428, 2010.
  * [7] Florian Dörfler and Francesco Bullo.  Spectral analysis of synchronization in a lossless structure-preserving power network model.  In Proceedings of the 2010 First IEEE International Conference on Smart Grid Communications, pages 179–184. IEEE, 2010.
  * [8] Florian Dörfler and Francesco Bullo.  Kron reduction of graphs with applications to electrical networks.  IEEE Transactions on Circuits and Systems I: Regular Papers, 60(1):150–163, 2012.
  * [9] Florian Dörfler and Francesco Bullo.  Synchronization and transient stability in power networks and nonuniform Kuramoto oscillators.  SIAM Journal on Control and Optimization, 50(3):1616–1642, 2012\.
  * [10] Florian Dörfler and Francesco Bullo.  Synchronization in complex networks of phase oscillators: A survey.  Automatica, 50(6):1539–1564, 2014.
  * [11] Florian Dörfler, John W Simpson-Porco, and Francesco Bullo.  Electrical networks and algebraic graph theory: Models, properties, and applications.  Proceedings of the IEEE, 106(5):977–1005, 2018.
  * [12] Sina Yamac Caliskan and Paulo Tabuada.  Towards Kron reduction of generalized electrical networks.  Automatica, 50(10):2586–2590, 2014.
  * [13] Manish K Singh, Sairaj Dhople, Florian Dörfler, and Georgios B Giannakis.  Time-domain generalization of Kron reduction.  IEEE Control Systems Letters, 7:259–264, 2022.
  * [14] George Forrest Young, Luca Scardovi, and Naomi Ehrich Leonard.  A new notion of effective resistance for directed graphs—part i: Definition and properties.  IEEE Transactions on Automatic Control, 61(7):1727–1736, 2015.
  * [15] Tomohiro Sugiyama and Kazuhiro Sato.  Kron reduction and effective resistance of directed graphs.  arXiv preprint arXiv:2202.12560, 2022.
  * [16] Fuzhen Zhang.  The Schur complement and its applications, volume 4.  Springer Science & Business Media, 2006.
  * [17] Jeffrey L Stuart.  Digraphs and matrices.  In Handbook of Linear Algebra, pages 29–1. Chapman and Hall/CRC, 2006.
  * [18] Andrea Tosatto, Tilman Weckesser, and Spyros Chatzivasileiadis.  A modified version of the IEEE 3-area RTS’96 Test Case for time series analysis.  arXiv preprint arXiv:1906.00055, 2019.