第1页 / 共220页
第2页 / 共220页
第3页 / 共220页
第4页 / 共220页
第5页 / 共220页
第6页 / 共220页
第7页 / 共220页
第8页 / 共220页
Combinatorial-Matrix-Theory.pdf
Foreword
Contents
Some Combinatorially Defined Matrix Classes
Permutations & Permutation Matrices
Alternating Sign Matrices
Tournaments & Tournament Matrices
Biblio
Sign Pattern Matrices
Intro to Sign Pattern Matrices
Potential Stability of Sign Patterns
Spectrally Arbitrary Sign Patterns
Refined Inertia of Sign Patterns
Inertially Arbitrary Sign Patterns
Biblio
Spectral Radius of Graphs
Graph-Theoretical Definitions
Adjacency Matrix & its Spectral Properties
Big Gun Approach
Eigenvector Approach
Characteristic Polynomial Approach
Walk Counting
Biblio
Group Inverse of Laplacian Matrix of Graph
Intro
Laplacian Matrix
Group Inverse
L# & Bottleneck Matrix
L# for Weighted Trees
Algebraic Connectivity
Joins
Resistance Distance
Computational Considerations
Closing Remarks
Biblio
Boundary Value Problems on Finite Networks
Intro
M-Matrix Inverse Problem
Difference Operators on Networks
Glossary
Networks with Boundaries
Self-Adjoint Boundary Value Problems
Monotonicity & Minimum Principle
Green & Poisson Kernels
Dirichlet-to-Robin Map
Characterization of Symmetric M-Matrices as Resistive Inverses
Distance-Regular Graphs with M-Property
Biblio
Richard A. Brualdi • Ángeles Carmona
P. van den Driessche • Stephen Kirkland
Dragan Stevanović
Combinatorial Matrix Theory
Editors for this volume:
Andrés M. Encinas, Universitat Politècnica de Catalunya
Margarida Mitjana, Universitat Politècnica de Catalunya
Richard A. Brualdi
Mathematics Department
University of Wisconsin
Madison, WI, USA
P. van den Driessche
Department of Mathematics and Statistics
University of Victoria
Victoria, BC, Canada
Dragan Stevanović
Mathematical Institute
Serbian Academy of Sciences and Arts
Belgrade, Serbia
Ángeles Carmona
Departament de Matemàtiques
Universitat Politècnica de Catalunya
Barcelona, Spain
Stephen Kirkland
Department of Mathematics
University of Manitoba
Winnipeg, MB, Canada
ISSN 2297-0312 (electronic)
(eBook)
ISSN 2297-0304
Advanced Courses in Mathematics - CRM Barcelona
ISBN 978-3-319-70952-9
https://doi.org/10.1007/978-3-319-70953-6
Library of Congress Control Number: 2018935110
© Springer International Publishing AG, part of Springer Nature 2018
ISBN 978-3-319-70953-6
Foreword
This book contains the notes of lectures delivered by Richard A. Brualdi, Angeles
Carmona, Stephen Kirkland, Dragan Stevanovic and Pauline van den Driessche
at the Centre de Recerca Matematica (CRM) in Bellaterra, Barcelona from June
29th to July 3rd, 2015. The Advanced Course on Combinatorial Matrix Theory
was mainly addressed to PhD students and post-docs in related areas, and also to
more established researchers who wanted to get involved in these subjects.
Combinatorial matrix theory is a rich branch of matrix theory; it is both an
active eld of research and a widespread toolbox for many scientists. Combina-
torial properties of matrices are studied on the basis of qualitative rather than
quantitative information, so that the ideas developed can provide consistent infor-
mation about a model even when the data is incomplete or inaccurate. The theory
behind qualitative methods can also contribute to the development of eective
quantitative matrix methods.
The topics covered in the Advanced Course included permutation matrices,
alternating sign matrices, tournaments, sign pattern matrices, minimum rank and
its distribution, boundary value problems on nite networks, the group inverse for
the Laplacian matrix of a graph, and bounds on the spectral radius of the Laplacian
matrix. The activity consisted of ve series of four lectures each. Accordingly, the
material is divided into ve chapters in the book. There were also two short sessions
devoted to informal presentations of the current work of most of the participants.
The rst chapter corresponds to the lectures delivered by Richard A. Brualdi
on some combinatorially dened matrix classes, specically on three families,
namely permutation, alternating sign, and tournament matrices. Permutation ma-
trices are the matrices associated with permutations, and it is shown that the
Bruhat order on this symmetric group is related to Gaussian elimination and
leads to the Bruhat decomposition of a nonsingular matrix. Alternating sign ma-
trices are generalizations of permutation matrices, and the extension of Bruhat
order is a lattice, specically its McNielle completion. A tournament matrix is
the adjacency matrix corresponding to a tournament; that is, an orientation of
the complete graph. The generation problem is presented and analyzed on loopy,
Hankel, and skew-Hankel tournaments.
The second chapter is devoted to the series of lectures given by Pauline
van den Driessche on sign pattern matrices. It discusses the study of spectral
properties of matrices with a given sign pattern. Several classes of sign patterns
are reviewed, including sign patterns that allow all possible spectra; those allowing
all possible inertias; those allowing stability; and those that may give rise to Hopf
bifurcation in associated dynamical systems. Some classes of these matrices are
explored in more detail using techniques from matrix theory, graph theory, and
analysis. Moreover, some open problems are suggested to encourage further work.
Dragan Stevanovic delivered lectures on the spectral radius of graphs, col-
lected in Chapter 3. The spectral radius of a graph is a tool to provide bounds of
parameters related to the properties of a graph. More precisely, eigenvalues and
eigenvectors of graph matrices have become standard mathematical tools nowa-
days due to their wide applicability in network analysis and computer science,
with the most prominent graph matrices being the adjacency and the Laplacian
matrix. In this chapter, lower and upper limits of the spectral radius of adjacency
and Laplacian matrices are addressed, with special attention to testing techniques
and common properties of shapes of the boundaries. In addition, approximate
formulas for the spectral radius of the adjacency matrix are also discussed.
The fourth chapter contains the lectures delivered by Stephen Kirkland on
the group inverse for the Laplacian matrix of a graph. In recent times, Laplacian
matrices for undirected graphs have received a good deal of attention, in part
because the spectral properties of the Laplacian matrix are related to a number of
features of interest of the underlying graph. It turns out that a certain generalized
inverse, the group inverse, of a Laplacian matrix also carries information about
the graph in question. This chapter explores the group inverse of the Laplacian
matrix and its relationship to graph structure. Connections with the algebraic
connectivity and the resistance distance are made, and the computation of the
group inverse of a Laplacian matrix is also considered from a numerical viewpoint.
The last chapter, authored by Angeles Carmona, is devoted to the study of
boundary value problems on nite networks. The starting point is the description
of the basic dierence operators: the derivative, gradient, divergence, curl and
Laplacian, or more generally, Schrodinger operators. The next step is to dene
the discrete analogue of a manifold with a boundary, which includes the concept
of outer normal eld and proves the Green identities. At that point, the focus
is on some aspects of discrete potential theory. The discrete analog of the Green
and Poisson kernels are dened and their relationship with the so-called Dirichlet-
to-Neuman map established. Finally, some applications to matrix theory and to
organic chemistry, such as the M-inverse problem and the Kirchho index compu-
tation, are considered.
We would like to express our gratitude to the director, Prof. Joaquim Bruna,
and sta of the Centre de Recerca Matematica not only for their excellent job in
organizing this course but also for their kindness and support during the event.
We are also in debt to Elsevier, the Societat Catalana de Matematiques, and the
Real Sociedad Matematica Espa~nola for their nancial support.
Finally, we thank all the participants for their active involvement and spe-
cially to the ve lecturers for their accurate preparation of these notes. We hope
that their publication will contribute to increasing knowledge of combinatorial
matrix theory.
Andres M. Encinas and Margarida Mitjana
Contents
Foreword
1 Some Combinatorially Dened Matrix Classes
By Richard A. Brualdi
1.1 Permutations and Permutation Matrices . . . . . . . . . . . . . . .
1.1.1 Basic Properties
. . . . . . . . . . . . . . . . . . . . . . . .
1.1.2 Generation . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.3 Bruhat Order . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.4 Matrix Bruhat Decomposition . . . . . . . . . . . . . . . .
1.1.5 Flags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.6
. . . . . . . .
1.2 Alternating Sign Matrices . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
1.2.1 Basic Properties
1.2.2 Other Views of ASMs
. . . . . . . . . . . . . . . . . . . . .
1.2.3 The -determinant . . . . . . . . . . . . . . . . . . . . . . .
1.2.4 Maximal ASMs . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.5 Generation . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.6 MacNeille Completion and the Bruhat Order . . . . . . . .
1.2.7 Bruhat Order Revisited . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
1.2.8
. . . . . . . . . . . . . . .
1.3.1 The Inverse Problem . . . . . . . . . . . . . . . . . . . . . .
1.3.2 Generation . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.3 Loopy Tournaments and Their Generation . . . . . . . . . .
1.3.4 Hankel Tournaments and Their Generation . . . . . . . . .
1.3.5 Combinatorially Skew-Hankel Tournaments and Their
1.3 Tournaments and Tournament Matrices
Involutions and Symmetric Integral Matrices
Spectral Radius of ASMs
Generation . . . . . . . . . . . . . . . . . . . . . . . . . . .
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
v
1
1
1
3
3
5
8
11
15
15
16
19
20
21
22
25
31
32
33
34
36
38
40
45
2 Sign Pattern Matrices
By P. van den Driessche
2.1
Introduction to Sign Pattern Matrices . . . . . . . . . . . . . . . .
2.1.1 Notation and Denitions . . . . . . . . . . . . . . . . . . . .
2.2 Potential Stability of Sign Patterns . . . . . . . . . . . . . . . . . .
Stability Denitions
. . . . . . . . . . . . . . . . . . . . . .
2.2.1
Stability of a Dynamical System . . . . . . . . . . . . . . .
2.2.2
2.2.3 Characterization of Sign Stability . . . . . . . . . . . . . . .
2.2.4 Basic Facts for Potential Stability . . . . . . . . . . . . . .
2.2.5 Known Results on Potential Stability for Small Orders . . .
2.2.6
Sucient Condition for Potential Stability . . . . . . . . . .
2.2.7 Construction of Higher-Order Potentially Stable Sign
Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.8 Number of Nonzero Entries . . . . . . . . . . . . . . . . . .
2.2.9 Open Problems Related to Potential Stability . . . . . . . .
2.3 Spectrally Arbitrary Sign Patterns . . . . . . . . . . . . . . . . . .
2.3.1
Some Denitions Relating to Spectra of Sign Patterns . . .
2.3.2 A Family of Spectrally Arbitrary Sign Patterns . . . . . . .
2.3.3 Minimal Spectrally Arbitrary Patterns and Number of
Nonzero Entries
2.5
. . . . . . . . . . . . . . . . . . . . . . . .
2.3.4 Reducible Spectrally Arbitrary Sign Patterns . . . . . . . .
Some Results on Potentially Nilpotent Sign Patterns . . . .
2.3.5
2.3.6
Some Open Problems Concerning SAPs . . . . . . . . . . .
2.4 Rened Inertia of Sign Patterns . . . . . . . . . . . . . . . . . . . .
2.4.1 Denition and Maximum Number of Rened Inertias . . . .
2.4.2 The Set of Rened Inertias Hn . . . . . . . . . . . . . . . .
Sign Patterns of Order 3 and H3 . . . . . . . . . . . . . . .
2.4.3
Sign Patterns of Order 4 and H4 . . . . . . . . . . . . . . .
2.4.4
2.4.5
Sign Patterns with All Diagonal Entries Negative . . . . . .
2.4.6 Detecting Periodic Solutions in Dynamical Systems . . . . .
2.4.7
. . . . . . . . . . . .
Inertially Arbitrary Sign Patterns . . . . . . . . . . . . . . . . . . .
2.5.1 Denition and Relation to Other Properties . . . . . . . . .
2.5.2 Generalization of the Nilpotent-Jacobian Method . . . . . .
2.5.3 Reducible IAPs . . . . . . . . . . . . . . . . . . . . . . . . .
2.5.4 A Glimpse at Zero-Nonzero Patterns . . . . . . . . . . . . .
2.5.5 A Taste of More General Patterns
. . . . . . . . . . . . . .
. . . . . . . . . . .
2.5.6
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Some Open Problems Concerning Hn
Some Open Problems Concerning IAPs
47
47
47
48
48
49
50
51
52
52
54
56
57
57
57
59
61
62
63
64
64
64
65
66
66
67
68
72
73
73
74
76
76
77
78
79
3 Spectral Radius of Graphs
By Dragan Stevanovic
83
83
3.1 Graph-Theoretical Denitions . . . . . . . . . . . . . . . . . . . . .
85
3.2 The Adjacency Matrix and Its Spectral Properties
. . . . . . . . .
89
3.3 The Big Gun Approach . . . . . . . . . . . . . . . . . . . . . . . .
3.4 The Eigenvector Approach . . . . . . . . . . . . . . . . . . . . . . .
95
3.5 The Characteristic Polynomial Approach . . . . . . . . . . . . . . . 105
3.6 Walk Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
4 The Group Inverse of the Laplacian Matrix of a Graph
131
By Stephen Kirkland
4.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
4.2 The Laplacian Matrix . . . . . . . . . . . . . . . . . . . . . . . . . 132
4.3 The Group Inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
4.4 L# and the Bottleneck Matrix . . . . . . . . . . . . . . . . . . . . 141
4.5 L# for Weighted Trees . . . . . . . . . . . . . . . . . . . . . . . . . 144
4.6 Algebraic Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . 148
4.7 Joins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
4.8 Resistance Distance
. . . . . . . . . . . . . . . . . . . . . . . . . . 154
4.9 Computational Considerations
. . . . . . . . . . . . . . . . . . . . 160
4.10 Closing Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
5 Boundary Value Problems on Finite Networks
By Angeles Carmona
173
5.3.1
5.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
5.2 The M -Matrix Inverse Problem . . . . . . . . . . . . . . . . . . . . 174
5.3 Dierence Operators on Networks . . . . . . . . . . . . . . . . . . . 176
Schrodinger Operators . . . . . . . . . . . . . . . . . . . . . 181
5.4 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
5.5 Networks with Boundaries . . . . . . . . . . . . . . . . . . . . . . . 185
5.6 Self-Adjoint Boundary Value Problems . . . . . . . . . . . . . . . . 188
5.7 Monotonicity and the Minimum Principle . . . . . . . . . . . . . . 193
5.8 Green and Poisson Kernels
. . . . . . . . . . . . . . . . . . . . . . 195
5.9 The Dirichlet-to-Robin Map . . . . . . . . . . . . . . . . . . . . . . 199
5.10 Characterization of Symmetric M -Matrices as Resistive Inverses
. 201
5.10.1 The Kirchho Index and Eective Resistances
. . . . . . . 202
5.10.2 Characterization . . . . . . . . . . . . . . . . . . . . . . . . 204
5.11 Distance-regular Graphs with the M -Property . . . . . . . . . . . . 207
5.11.1 Strongly Regular Graphs
. . . . . . . . . . . . . . . . . . . 209
5.11.2 Distance-regular Graphs with Diameter 3 . . . . . . . . . . 210
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
