Réunion d'été SMC 2011 Université de l'Alberta, Edmonton, 3 - 5 juin 2011 www.smc.math.ca//Reunions/ete11

Théorie combinatoire des matrices
Org: Shaun Fallat (Regina) et Kevin N. Vander Meulen (Redeemer College)
[PDF]

WAYNE BARRETT, Brigham Young University
The Combinatorial Inverse Eigenvalue Problem  [PDF]

Let $G=(V,E)$ be an undirected graph on $n$ vertices, and let $S(G)$ be the set of all real symmetric $n \times n$ matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of $G$, i.e., for $i \ne j$, $a_{ij}\ne 0 \iff \{i,j\} \in E$. The combinatorial inverse eigenvalue problem asks:

Given a graph $G$ on $n$ vertices and real numbers $\lambda_1,\lambda_2,\ldots,\lambda_n$, is there a matrix in $S(G)$ with eigenvalues equal to $\lambda_1,\lambda_2,\ldots,\lambda_n$?

Previous results focus on solving the problem for trees. Another fairly large class of graphs for which it is possible to obtain general results is the class of minimum rank 2 graphs; for these all possible pairs of nonzero eigenvalues which are attainable for a rank 2 matrix in $S(G)$ are characterized. Time permitting, we will discuss properties of minimum rank matrices and the associated inverse inertia problem.

MICHAEL CAVERS, University of Calgary
Allow Problems Concerning Spectral Properties of Patterns  [PDF]

Let $S\subseteq\{0,+,-,+_0,-_0,*,\#\}$ be a set of symbols, where $+$ (resp. $-$, $+_0$ and $-_0$) denotes a positive (resp. negative, nonnegative and nonpositive) real number, and $*$ (resp. $\#$) denotes a nonzero (resp. ambiguous) real number. An $S$-pattern is a matrix with entries in $S$. In particular, a $\{0,+,-\}$-pattern is a sign pattern and $\{0,*\}$-pattern is a zero-nonzero pattern. In this talk, we will discuss various allow problems concerning spectral properties of $S$-patterns.

LOUIS DEAETT, University of Victoria
The principal rank characteristic sequence of a real symmetric matrix  [PDF]

Given an $n\times n$ real symmetric matrix $A$ we associate to $A$ a sequence $r_0r_1\cdots r_n \in \{0,1\}^{n+1}$ defined by$r_k=\begin{cases} 1 & \mbox{ if A has a principal submatrix of rank k, and}\0&\mbox{ otherwise,} \end{cases}$ or, equivalently, $$\label{alt_char} r_k=\begin{cases} 1 & \mbox{ if A has a nonzero principal minor of order k, and }\0&\mbox{ otherwise} \end{cases}$$ for $1\le k \le n$, with $r_0=1$ if and only if $A$ has a zero entry on its main diagonal. Denote this sequence by $\text{pr}(A)$.

Now, given an arbitrary sequence of $0$s and $1$s, is it $\text{pr}(A)$ for any real symmetric matrix $A$? If so, call the sequence $attainable$. The problem, then, is to characterize the attainable sequences.

We will discuss how this problem relates to graph eigenvalues and to both some quite old and some quite recent results concerning algebraic relationships between the principal minors of a symmetric matrix.

Joint work with Richard Brualdi, Dale Olesky and Pauline van den Driessche.

RANDY ELZINGA, Royal Military College of Canada
Graphs with Rational Normalized Adjacency Eigenvalues  [PDF]

If $A$ is the adjacency matrix of a graph $G$ and $D$ is the diagonal matrix of vertex degrees, then the {\em Laplacian matrix} of $G$ is $L=D-A$. Longstanding problems include determining which graphs have only integral adjacency eigenvalues and which have only integral Laplacian eigenvalues. The {\em normalized adjacency matrix} of $G$ is $N=D^{-1/2}AD^{-1/2}$. I will show that the graphs with only integral normalized adjacency eigenvalues are graphs whose components are complete bipartite graphs, show that the analogous problem is to determine which graphs have only rational normalized adjacency eigenvalues, and present some results on trees with only normalized rational eigenvalues.

SHAUN FALLAT, University of Regina
On Two Colin de Verdiere Parameters of Chordal Graphs  [PDF]

Two important graph parameters, developed by Colin de Verdiere, are connected with the maximum nullity of certain real symmetric matrices associated with a given graph. In this talk, these parameters, called $\mu$ and $\nu$, are calculated for chordal graphs.

YI ZHENG FAN, University of Regina

The eigenvalues of a graph are defined as the eigenvalues of a certain matrix associated with that graph. Maximizing or minimizing an extreme eigenvalue in some class of graphs is a topic in spectral graph theory, from which we can understand the structure of graphs. The quadratic forms on graphs are combinatorial viewpoint or method on this topic, as it contains information on the graph structure and it has more meaning than the quadratic form of matrices. In this talk I will introduce the quadratic forms on graphs and illustrate it with some examples.

CHRIS GODSIL, University of Waterloo
Graph Spectra and Quantum Computing  [PDF]

If $A$ is the adjacency matrix of a graph $X$, we define a transition matrix $H_X(t)$ by $$H_X(t) := \exp(itA).$$ This is a symmetric unitary matrix, underlying a so-called continuous quantum walk. Work in quantum computing leads to a number of questions which can be attacked using ideas from the theory of graph spectra. I will present examples, along with a number of open questions.

IN-JAE KIM, Minnesota State University
Unordered multiplicity lists of $\Phi$-binary trees  [PDF]

The unordered multiplicity lists of eigenvalues of a graph were introduced in the study of Inverse Eigenvalue Problem for graphs (IEP-G). In this talk we study the unordered multiplicity lists of $\Phi$-binary trees, and discuss some other results related to the lists.

ZHONGSHAN LI, Georgia State University
Irreducible 4 by 4 sign patterns that require 4 distinct eigenvalues  [PDF]

A sign pattern (matrix) is a matrix whose entries are from the set $\{+, -, 0\}$. Some necessary or sufficient conditions for a square sign pattern to require all distinct eigenvalues are presented. In particular, it is known that such sign patterns require a fixed number of real eigenvalues. The $3 \times 3$ irreducible sign patterns that require 3 distinct eigenvalues have been identified previously. The $4 \times 4$ irreducible sign patterns that require four distinct real eigenvalues and those that require four distinct nonreal eigenvalues are characterized. The $4 \times 4$ irreducible sign patterns that require two distinct real eigenvalues and two distinct nonreal eigenvalues are investigated.

JUDI MCDONALD, Washington State University
Spectrally Arbitrary Matrix Patterns that Depend on Field Structure  [PDF]

An nxn pattern P of zeros and stars (nonzeros) is said to be spectrally arbitrary over a field F provided any n-th degree monic polynomial in F[x] can be realized as the characteristic polynomial of a matrix formed from replacing the stars in P by nonzero elements from F. A pattern may be spectrally arbitrary over some fields, but not others. In this talk we will look at some specific patterns for which the algebraic properties of a given field play a critical role in whether or not the pattern is spectrally arbitrary for that field.

KAREN MEAGHER, University of Regina
The Erd\H{o}s-Ko-Rado Theorem: an algebraic perspective  [PDF]

The Erd\H{o}s-Ko-Rado (EKR) Theorem is a major result in extremal set theory. It gives the exact size and structure of the largest system of sets that has the property that any two sets in the system have non-trivial intersection. There are many extensions of this theorem to combinatorial objects other than set systems, such as vectors subspaces over a finite field, integer sequences, partitions, and recently, there have been several results that extend the EKR theorem to permutations.

I will describe an algebraic method that can be used to prove the EKR theorem for several of these combinatorial objects. Using the eigenvalues of the adjacency matrix of an appropriately defined graph we can often bound the size of the largest intersecting set of objects. Further, by considering the structure of the eigenspace we can also determine the structure of these sets. I will present several examples where this works and show some open problems.

Extremal norms of graphs and matrices  [PDF]

The energy of a graph, a parameter introduced by Gutman and much studied recently, turns out to be just the nuclear norm of the adjacency matrix. Similar matrix norms seem to be interesting as well. Thus, this talk presents some extremal results about the Schatten and Ky Fan norms of the adjacency matrices of graphs and of matrices in general.

DALE OLESKY, University of Victoria
Sign Patterns with a Nest of Positive Principal Minors  [PDF]

A matrix $A\in\ M_n\,(\mathbb{R})$ has a nest of positive principal minors if $PAP^T$ has positive leading principal minors for some permutation matrix $P$. A sign pattern is a matrix with entries $\in\, \{+,\; -,\; 0\}$. A sign pattern ${\cal A}$ requires a nest of positive principal minors if every real matrix $B$ with that sign pattern has a nest of positive principal minors, and ${\cal A}$ allows a nest of positive principal minors if there exists such a matrix $B$ that has a nest of positive principal minors. Motivated by the fact that a matrix $A$ with a nest of positive principal minors can be positively scaled so all its eigenvalues lie in the open right-half-plane, conditions are investigated so that a square sign pattern either requires or allows a nest of positive principal minors. This is joint work with Michael Tsatsomeros and Pauline van den Driessche.

PAULINE VAN DEN DRIESSCHE, University of Victoria
Refined Inertia of Pattern Matrices  [PDF]

The refined inertia of a real matrix $A$ of order $n$ is an ordered quadruple $(n_+, n_-, n_z, 2n_p)$ of nonnegative integers that sum to $n$, where $n_+, n_-$ is the number of eigenvalues of $A$ with real part positive, negative, respectively, $n_z$ is the number of zero eigenvalues, and $2n_p$ is the number of nonzero pure imaginary eigenvalues. This concept has application in detecting the possibility of Hopf bifurcation in dynamical systems. Some results on refined inertias of zero-nonzero pattern matrices (matrices with entries $0$ or $*$) and of sign pattern matrices (matrices with entries $+, -$ or $0$) are given and open problems are stated.

KEVIN VANDER MEULEN, Redeemer University College
Index of Nilpotent Matrices and the Nilpotent-Jacobian Method  [PDF]

A nonzero pattern is a matrix with entries in $\{0, \ast\}$. A pattern is potentially nilpotent if there is some nilpotent real matrix with nonzero entries in precisely the entries indicated by the pattern. We construct some potentially nilpotent balanced tree patterns, and explore their index. Using the Nilpotent-Jacobian method, we observe that some balanced tree patterns are spectrally arbitrary. Inspired by an argument of Pereira, we uncover a feature of the Nilpotent-Jacobian method. In particular, we show that if $N$ is the nilpotent matrix employed by this method to show that a pattern is a spectrally arbitrary pattern, then $N$ must have full index. [Joint work with Hannah Bergsma and Adam van Tuyl]