Navigate Up
Sign In
  • CRM
  • CRM
  • CRM
CRM > English > Activities > Curs 2014-2015 > Combinatorial Matrix Theory
Combinatorial Matrix Theory
advanced course on Combinatorial matrix theory
 

General information 

​From June 29 to July 3, 2015 at the CRM (location)

Timetable​

List of participants​

Grants available

Download the poster here​


Goals 

Combinatorial matrix theory is a rich branch of matrix theory concerned with the interplay of combinatorics/graph theory and matrix theory/linear algebra. It's a two way street, with linear algebra providing a means to prove combinatorial theorems, and combinatorics providing more detailed and refined information in linear algebra. Moreover, combinatorial properties of matrices are studied based on qualitative rather than quantitative information, so that the ideas developed can provide consistent information about a model even when the data is incomplete or inaccurate. The theory behind qualitative methods can also contribute to the development of effective quantitative matrix methods.

 

Particular topics lectured in this summer school will include sign pattern matrices, minimum rank and its distribution, boundary value problems on finite networks, the group inverse for the Laplacian matrix of a graph and bounds on the spectral radius of the Laplacian matrix. 

Scientific Committee 


Andrés M. Encinas, Universitat Politècnica de Catalunya
Carlos Da Fonseca, Kuwait University
Margarida Mitjana, Universitat Politècnica de Catalunya

​Lecturers


Each lecturer will give 5 hours course:

 

Richard A. Brualdi, University of Wisconsin-Madison

Angeles Carmona Mejías, Universitat Politècnica de Catalunya-BarcelonaTech

Stephen J. Kirkland, University of Manitoba

Dragan Stevanovic, Serbian Academy of Sciences and Arts (SANU)

Pauline van den Driessche, University of Victoria 

 

LECTURE ABSTRACTS


Richard A. Brualdi

Combinatorial Matrix Theory

Combinatorial Matrix Theory (CMT) is concerned with the interplay of combinatorics/graph theory and matrix theory/linear algebra. It's a two way street, with linear algebra providing a means to prove combinatorial theorems, and combinatorics providing more detailed and refined information in linear algebra. In addition, in CMT classes of matrices (adjacency matrices of bipartite graphs, or in the symmetric case, graphs) are investigated with the goal of understanding such classes and investigation of combinatorial or linear algebraic invariants over the class. In these lectures I plan to discuss many aspects of CMT.

 

Angeles Carmona

Boundary value problems on Finite Networks

The aim of these lectures is to analyze self–adjoint boundary value problems on finite networks. We start with the description of the basic difference operators: the derivative, gradient, divergence, curl and laplacian, or more generally, Schrodinger operators. Moreover, we prove that the above operators satisfy analogue properties to those exhibited by their continuous counterpart. The next step is to define the discrete analogue of a manifold with boundary, which includes the concept of outer normal field. Then, we prove the Green Identities in order to establish the variational formulation of boundary value problems. Then, we focus on some aspects of discrete Potential Theory by proving the discrete version of the Dirichlet, the maximum and the condenser principles. In this framework, another useful tool is the concept of Resolvent Kernel associated with a boundary value problem. So, we define the discrete analogous of the Green and Poisson Kernels and we establish its main properties and relations. Then, we also deal with the Dirichlet to Neumann map and study its relation with the Poisson and Green kernels. Finally, we consider some applications to Matrix Theory and to Organic Chemistry, as the M–inverse problem and the Kirchhoff Index computation, respectively.

 

 

Stephen Kirkland

The Group Inverse for the Laplacian Matrix of a Graph

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 generalised inverse - the group inverse - of a Laplacian matrix also carries information about the graph in question. This series of lectures will explore the group inverse of the Laplacian matrix and its relationship with graph structure. Connections with algebraic connectivity and resistance distance will be made, and the computation of the group inverse of a Laplacian matrix will also be considered from a numerical viewpoint.

 

Dragan Stevanovic

Spectral radius of graphs

Eigenvalues and eigenvectors of graph matrices have become standard mathematical tools nowadays 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 these lectures I will survey lower and upper bounds on the spectral radius of adjacency and Laplacian matrices, with focus on the proof techniques and on common properties of the forms of the bounds. Some interesting approximate formulas for the spectral radius of adjacency matrix will be discussed as well.


Pauline van den Driessche

Sign Pattern Matrices

An n x n sign pattern (matrix) A* = [αij] has entries from {+, -, 0} with an associated sign pattern class of real n x n matrices {A = [aij] : sign(aij ) = αij for all i, j}. These lectures will survey some important classes of sign patterns, including sign patterns that allow all possible spectra, those that allow all possible inertias, those that allow stability, and those that may give rise to Hopf bifurcation in associated dynamical systems. Then some classes will be explored in more detail using techniques from matrix theory, graph theory and analysis, and open problems will be suggested.  ​

Registration 
 
 REGISTRATION FEE

Junior: 150€

Senior: 300€

Registration includes: Documentation package, lunch (during the days of the advanced course, from Monday to Friday), social dinner, and coffee breaks.

Deadline for registration: June 21, 2015

The number of participants is limited. See the grants available below.

Please, access the on-line registration process by clicking one of the REGISTER buttons 
​Grants


A limited number of grants (lodging and/or reduced registration) are available for PhD students and recent PhD holders (who received their PhDs no more than two years ago).  

Check the details here

Lodging

For lodging in the area please click here​

For off-campus and family accommodation click here​​ ​​


Acknowledgments


Partial support for students attending this advanced course has been received from Elsevier, publisher of the journal "LinearAlgebra and its Applications​".

This advanced course has also received support from the Societat Catalana de Matemàtiques 

Contact

​For further information contact the programme coordinator Neus Portet (nportet@crm.cat​) ​




​​​​​​​​​​​​​​​​​​​​​