Lecturer Series

Richard A. Brualdi: Topics in Combinatorial Matrix Theory

Topics to be taken from: Alternating sign matrices, Combinatorial Matrix Classes ((0,1)-matrices, doubly stochastic matrices and generalizations, ...), A Berlekamp switching game, Principal minors of symmetric matrices, ... .

Peter Brooksbank: Linear methods in computational algebra

In this series of lectures I aim to provide an overview of some fundamental problems in computational algebra, focusing particularly on problems that admit the use of techniques from linear algebra. Not surprisingly, the selection of problems to some extent reflects my own interests, but each of them is an active area of current research in the field. I assume only a basic knowledge of algebra: groups, rings, fields, and of course linear algebra.

Lecture 1.

In this lecture I will give a (somewhat biased) overview of computational algebra, putting a special emphasis on problems concerning linear groups and algebras. I will discuss broad goals, some history, algorithms, and complexity. I will also introduce fundamental tools needed for the subsequent talks.

Lecture 2.

The basis for this lecture is a large scale project to compute the structure of any given group of matrices defined over a finite field. I will mention two approaches to this problem and identify a certain problem of "constructive recognition" as being crucial to both. I will then discuss algorithms to solve the latter problem, once again emphasizing the power of techniques from linear algebra.

Lecture 3.

The motivation for this lecture is the fundamental "isomorphism problem" for finite groups, which seeks an efficient algorithm to decide whether or not two given finite groups are isomorphic. I will show how, in key cases, the problem involves the construction of groups that preserve a certain linear object (a bi-additive map) associated to the input groups. The main idea is to then "linearize" a seemingly non-linear problem; I will report on recent progress in this regard.

---

Iain Duff: Sparse Matrices

This series of lectures will introduce and illustrate the ubiquity of sparse matrices and will discuss in some detail the solution of large sparse linear systems. We will mainly consider direct methods of solution based on a matrix factorization but also discuss iterative and hybrid methods. The only assumption made of the audience is that they are familiar with linear equations and matrices.

Good background reading might include the books:

• Direct Methods for Sparse Linear Systems. Timothy A. Davis. SIAM Press 2006.
(Access full text from NUI Galway though the library portal).
• Direct Methods for Sparse Matrices. Iain S. Duff, Albert M. Erisman, and John K. Reid. Oxford University Press. 1986.
• Computer Solution of Large Sparse Positive Definite Systems. A. George and J. W. H. Liu. Prentice-Hall. 1981.

Lecture 1.

Introduction to sparse matrices and sparse linear equation solution and introduction to sparse direct methods. This will include relationship to graphs and matrix reorderings.

Lecture 2.

Direct methods for solving sparse linear systems to include discussion of elimination trees, supernodal and multifrontal methods and comments on parallelism.

Lecture 3.

A short introduction to iterative and hybrid methods with a discussion of current research in this area.

---

Carlos Martins da Fonseca: Recent trends on spectral graph theory

Spectral graph theory is a prosperous and powerful common branch of graph theory and linear algebra that relates various graph properties with the spectra of certain matrices associated to the graph. This vibrant field of interest has been extensively studied in the last decades with applications in various disciplines.

The aim of these lectures is to recall some crucial results on spectral graph theory and understand some recent developments in the area.

In the first session we will review basic results on the spectra of acyclic Hermitian matrices and its relations with the underlying graph, reminding some well and less-known results.

The next two sessions will be devoted to the P-vertices of acyclic symmetric matrix matrices. We will characterise the trees where the maximum number of P-vertices is attained. Moreover, we will establish an algorithm to construct a graph and a corresponding matrix where the number of P-vertices is given. One session will be dedicated to the non-singular matrices and the other to the remaining matrices.

In the last lecture, we will analyse the multiplicities of the eigenvalues of the so-called Φ-binary tree. We carry this discussion forward extending some recent results to a larger family of trees, namely, the wide double path, i.e., a tree consisting of two paths that are joined by another path. Several research problems will be proposed.

---

Charles Johnson: Totally Positive Matrices

General goal: The audience should be exposed a fairly complete description of all the basic theory, and have an idea of some recent work and interesting research problems in the subject.

• Lecture 1: Definitions, history, common tools, and the most basic theory
• Lecture 2: The Elementary Bidiagonal Factorization, applications, recognition results and spectral theory.
• Lecture 3: Advanced Topics: determinantal inequalities, shadows, Hadamard powers, etc
• Lecture 4: Modern Research: completion problems, geometric connections, etc.

Reference: Totally Nonnegative Matrices, by S. Fallat and C. Johnson, Princeton University Press, 2011.. (Note: Chapter 1 is freely available from the publisher's website)