Skip to main content

About this book

This book contains the notes of the lectures delivered at an Advanced Course on Combinatorial Matrix Theory held at Centre de Recerca Matemàtica (CRM) in Barcelona. These notes correspond to five series of lectures. The first series is dedicated to the study of several matrix classes defined combinatorially, and was delivered by Richard A. Brualdi. The second one, given by Pauline van den Driessche, is concerned with the study of spectral properties of matrices with a given sign pattern. Dragan Stevanović delivered the third one, devoted to describing the spectral radius of a graph as a tool to provide bounds of parameters related with properties of a graph. The fourth lecture was delivered by Stephen Kirkland and is dedicated to the applications of the Group Inverse of the Laplacian matrix. The last one, given by Ángeles Carmona, focuses on boundary value problems on finite networks with special in-depth on the M-matrix inverse problem.

Table of Contents


Chapter 1. Some Combinatorially Defined Matrix Classes

In this section we consider the symmetric group of permutations of a finite set and their partial order known as the Bruhat order. Regarding a permutation as a permutation matrix, this partial order is related to Gaussian elimination and leads to the matrix Bruhat decomposition of a nonsingular matrix, and then to a characterization of ags in a vector space. We also describe a correspondence between permutations that are involutions (symmetric permutation matrices) and a certain class of nonnegative integral matrices.
Richard A. Brualdi

Chapter 2. Sign Pattern Matrices

The study of sign pattern matrices is an important part of combinatorial matrix theory. It has a rich theory in its own right and, in addition, some results are useful in applications to dynamical systems where sign patterns arise naturally, for example in predator-prey populations, economics, chemistry, and sociology. The aim of this chapter is to describe some spectral properties of matrices with a given sign pattern from the perspective of combinatorial matrix theory, showing some results, techniques, applications, and open problems. Topics are chosen from the literature on sign patterns; some of these and other related topics can be found in the book Brualdi–Shader [7], and in the chapter Hall–Li [34] from the Handbook of Linear Algebra edited by L. Hogben, and references therein. Readers are encouraged to consult these other references for topics beyond those in this chapter, which is a somewhat personal overview of some results on sign pattern matrices.
P. van den Driessche

Chapter 3. Spectral Radius of Graphs

Graphs are naturally associated with matrices, as matrices provide a simple way of representing graphs in computer memory. The basic one of these is the adjacency matrix, which encodes existence of edges joining vertices of a graph. Knowledge of spectral properties of the adjacency matrix is often useful to describe graph properties which are related to the density of the graph’s edges, on either a global or a local level. For example, entries of the principal eigenvector of adjacency matrices have been used in the study of complex networks, introduced under the name eigenvector centrality by the renowned mathematical sociologist Phillip Bonacich back in 1972; see [5, 6].
Dragan Stevanović

Chapter 4. The Group Inverse of the Laplacian Matrix of a Graph

What follows is a short, selective tour of some of the connections between weighted graphs and the group inverses of their associated Laplacian matrices. The presentation below draws heavily from Kirkland–Neumann [11, Ch. 7], and the interested reader can find further results on the topic in that book. We note that Molitierno [13] also covers some of the material presented in this chapter, and so serves as another source for readers interested in pursuing this subject further.
Stephen Kirkland

Chapter 5. Boundary Value Problems on Finite Networks

This chapter is motivated by a well-known matrix problem; specifically, the M- matrix inverse problem, as we will see in the next section. Our approach differs from others because the tools we use come from discrete potential theory, in which we have been working for a long period, trying to emulate as much as possible the continuous case. This chapter introduces this way of approximating a problem typical of matrix theory and offers an overview of the potential power of introducing new approaches in this field.
Ángeles Carmona


Additional information

Premium Partner

    Image Credits