2019 CMS Summer Meeting
Regina, June 7 - 10, 2019
- ROBERT BAILEY, Grenfell Campus, Memorial University
Orthogonal matrices with zero diagonal [PDF]
-
Motivated by work of the Discrete Mathematics Research Group at the University of Regina on the question of determining the minimum number of distinct eigenvalues of graphs, we consider real orthogonal $n\times n$ matrices where the diagonal entries are all zero and the off-diagonal entries are all non-zero. We show that such matrices exist if and only if $n\not\in\{1,3\}$, and that symmetric examples exist if and only if $n$ is even and $n\neq 4$. We also give a complete solution to the existence of orthogonal matrices with partially-zero diagonal.
This is joint work with Robert Craigen (University of Manitoba).
- EUGENE BILOKOPYTOV, University of Manitoba
From Principal Minor Assignment problem for matrices to characterization of the isometries on Hilbert Spaces [PDF]
-
We generalize a theorem by Engel and Schneider on matrices diagonally similar to a symmetric matrix to the case of infinite matrices. Geometric interpretation of this result allows us to
obtain a new characterization of isometries of Hilbert spaces using volumes of parallelepipeds.
- MURRAY R. BREMNER, University of Saskatchewan
Computing a short basis for the nullspace of a modular matrix [PDF]
-
Given a vector $X$ over the field with $p$ elements, define its length to be the sum of the squares of the symmetric representatives of its components. Define the length of a finite set of vectors to be the base 10 logarithm of the product of the lengths of the vectors. I will present an evolutionary algorithm which attempts to determine the shortest basis of the nullspace of a modular matrix $A$. To begin, compute $M$, the matrix in RREF whose $k$ rows form a basis for the null space of $A$. One generation consists of six steps. Step 1 (mutation): Randomly permute the columns of $A$ to obtain $B$. Step 2: Compute $C$, the matrix in RREF whose $k$ rows form a basis for the null space of $B$. Step 3: Unpermute the columns of $C$ to obtain $N$. Step 4 (recombination): Stack $M$ and $N$ and sort the $2k$ rows by increasing length to obtain $D$. Step 5 (selection): Determine the lexicographically minimal subset of the rows of $D$ which forms a basis of the nullspace of $A$. Step 6 (reproduction): Replace $M$ by the matrix consisting of these $k$ rows of $D$. I will present experimental results showing the behavior of this algorithm over thousands of generations.
- SAMUEL COLE, University of Manitoba
Spectral recovery of stochastic block models on graphs and hypergraphs [PDF]
-
The stochastic block model is a random graph model in which $n$ fixed vertices are partitioned into $k$ clusters, and edges are added independently between each pair of verices with probability $p$ if they are in the same cluster and $q$ if they are in different clusters, where $0 \leq q < p \leq 1$. Given only a random graph from this distribution, can one recover the partition of the vertices w.h.p? We will discuss a simple algorithm that accomplishes this using spectral properties of the random graph's adjacency matrix, and a generalization to a hypergraph setting. While there have been many results for the sparse case, in which $p, q = o(1)$ and the number of clusters $k$ is fixed, we will focus on the dense case, in which $p, q$ are fixed and $k$ grows with $n$.
- ROBERT CRAIGEN, University of Manitoba
- COLIN GARNETT, Black Hills State University
Non-sparse Companion Matrices [PDF]
- COLIN GARNETT, Black Hills State University
-
Given a polynomial $p(z)$, a companion matrix can be thought of as a simple template for placing the coefficients of $p(z)$ in a matrix such that the characteristic polynomial of this matrix is $p(z)$. The Frobenius companion matrix and the more recently discovered Fiedler companion matrices are examples. Both the Frobenius and Fiedler companion matrices have the maximum possible number of zero entries, and in that sense are sparse. In this presentation we will discuss the Frobenius and Fiedler companion matrices and explore the question of finding non-sparse companion matrices with more nonzero entries. We will also give some bounds on the minimum number of zeros that must appear in a companion matrix.
- CHUN-HUA GUO, University of Regina
Explicit convergence region of Newton's method for the matrix $p$th root [PDF]
-
For a square matrix with all eigenvalues in a suitable region in the complex plane,
its principal $p$th root exists and can be approximated by the quadratically convergent sequence generated by Newton's method (starting from the identity matrix). Such a region is called a convergence region for Newton's method.
In this talk, we present an explicit convergence region that drastically expands all existing ones.
- NATHAN KRISLOCK, Northern Illinois University
- LON MITCHELL, University of South Florida St. Petersburg
Optimal Colin de Verdière Matrices for Complete Multipartite Graphs [PDF]
- LON MITCHELL, University of South Florida St. Petersburg
-
We find matrices that are optimal for the Colin de Verdière invariant $\mu$ in the case of complete multipartite graphs and show how, for any graph $G$, $\mu(G)$ can be bounded using $\mu$ of a related complete multipartite graph.
- KEIVAN MONFARED, University of Victoria
An Analog of Matrix Tree Theorem for Signless Laplacians [PDF]
-
The number of spanning trees in a graph $G$ is given by Matrix Tree Theorem in terms of principal minors of Laplacian matrix of $G$. We show a similar combinatorial interpretation for principal minors of signless Laplacian $Q$. We also prove that $\frac{\det(Q)}{4}$ is greater than or equal to the number of odd cycles in $G$, where the equality holds if and only if $G$ is a bipartite graph or an odd-unicyclic graph.
- SIVARAM K. NARAYAN, Central Michigan University
Graph Complement Conjecture for Classes of Shadow Graphs [PDF]
-
The real minimum semidefinite rank of a graph $G$, denoted $mr_+^{\mathbb{R}}(G)$, is the minimum rank among all real symmetric positive semidefinite matrices whose zero/nonzero pattern corresponds to the graph $G$. The graph complement conjecture, denoted $GCC_+$, is the inequality $mr_+^{\mathbb{R}}(G) + mr_+^{\mathbb{R}}(\overline{G}) \leq |G| + 2$. Given a graph $G$, the shadow graph $S(G)$ is obtained from $G$ by adding for each vertex $u$ of $G$, a new vertex $v$, called the shadow vertex of $u$, and joining $v$ to the neighbors of $u$ in $G$. Also, a variant of $S(G)$, denoted Shad$(G)$, will be given. It is shown that $S(G)$ and Shad$(G)$ satisfies $GCC_+$ when $G$ is a tree or a unicyclic graph or a complete graph.
- PIETRO PAPARELLA, University of Washington Bothell
Matricial Proofs of Some Classical Results about Critical Point Location [PDF]
-
The Gauss–Lucas and Bôcher–Grace–Marden theorems are classical results in the geometry of polynomials. Proofs of the these results are available in the literature, but the approaches are seemingly different. In this work, we show that these theorems can be proven in a unified theoretical framework utilizing matrix analysis (in particular, using the field of values and the differentiator of a matrix). In addition, we provide a useful variant of a well-known result due to Siebeck.
- RAJESH PEREIRA, University of Guelph
The real joint numerical range and the real higher rank numerical range [PDF]
-
We study properties of the real analogs of the joint numerical range and the higher rank numerical ranges and discuss both similarities and differences with the usual complex case. Applications to cross sections of ellipsoids and open questions will also be discussed. This is joint work with Matthew Kazakov and David Kribs.
- MAHSA NASROLLAHI SHIRAZI, University of Regina
Erdős-Ko-Rado theorem for t-intersecting families of perfect matchings [PDF]
-
An interesting way to answer some questions arising in design theory is to use both graph theory and matrix theory, which is the approach I employ to find extensions of the famous Erdős-Ko-Rado theorem to t-intersecting families of objects. Such a result would give the size and structure of the largest set of the t-intersecting objects. In this approach we define a graph so that finding the largest set of t-intersecting perfect matchings is equivalent to finding the largest coclique of this graph. Bounds on the size of max cocliques can be found if we can determine the least eigenvalue of the adjacency matrix of our graph.
In this talk I will present the progress I have made in determining these eigenvalues.
- GURMAIL SINGH, University of Regina
Encoding the vertices of a hyper cube [PDF]
-
A concept class $\mathcal{C}$ over a finite domain $\mathcal{X}$ is a subset of the powerset of $\mathcal{X}$. The elements of $\mathcal{C}$ are called concepts. A concept class $\mathcal{C}$ over a domain $\mathcal{X}$ is said to shatter a set $A\subseteq \mathcal{X}$ if $\forall ~ a \subseteq A, \exists~ c \in \mathcal{C} \mbox{ such that } a= A\cap c$. The VC-dimension of $\mathcal{C}$, denoted as $VCD(\mathcal{C})$, is defined as the cardinality of the largest subset of $\mathcal{X}$ that $\mathcal{C}$ shatters. A concept class $\mathcal{C}$ over a domain $\mathcal{X}$ with $VCD(\mathcal{C})=d$ is called a maximum concept class if it attains equality in the well-known upper bound $|\mathcal{C}|\leq \sum^d_{i=0} {|\mathcal{X}| \choose i}$ due to Sauer, Shelah, and Perles. The subset teaching dimension of a concept class $\mathcal{C}$ measures the difficulty to encode the concepts of $\mathcal{C}$ in terms of their elements in a certain way. In this talk, we prove that every maximum concept class $\mathcal{C}$ with $VCD(\mathcal{C})=2$ has subset teaching dimension equal to $2$. This result is extended to higher VC-dimension for a particular kind of maximum concept class known as Simple Linear Arrangement. This is joint work with Sandra Zilles.
- KERRY TARRANT, University of Iowa
The Good, The Bad, and The Ugly: Minimally Cop Win and Maximally Robber Win Graphs [PDF]
-
Cops and robbers is a two-player pursuit and evade game played on discrete graphs. This presentation will investigate the addition and removal of any one edge to change the outcome of the game. In one instance, the removal of any edge will change a cop win game into a robber win game (called minimally cop win). In another instance, the addition of any edge will turn a robber win game into a cop win game (called maximally robber win). Characterizing the former is quite simple. However, characterizing maximally robber win graphs presents many challenges. Our efforts were greatly aided by studying such graphs in the complement, with unexpected results.
- HARMONY ZHAN, Centre de Recherches Mathématiques, Universite de Montreal
Quantum state transfer in the algebra of the Johnson scheme [PDF]
-
A real matrix $A$ in the adjacency algebra of a distance regular graph represents a spin network with non-nearest neighbour couplings. We are interested in a quantum phenomenon called perfect state transfer, that is, $|\exp(itA)_{u,v}|=1$ for some vertices $u$, $v$ and time $t$. It is known that the only generalized Johnson graphs that admit perfect state transfer are disjoint unions of edges. In this talk, we characterize all real matrices in the algebra of the Johnson scheme that admit perfect state transfer. This is joint work with Luc Vinet.
- XIAOHONG ZHANG, University of Manitoba
Perfect state transfer on weighted paths [PDF]
-
Let $X$ be a weighted graph, and denote its Laplacian matrix by $L(X)$. Let $U(t) = e^{itL(X)}$. Then $U(t)$ is a complex symmetric unitary matrix.
We say that $X$ admits Laplacian perfect state transfer (Laplacian PST) between vertices $j$ and $k$ at time $t=t_0$ if $|(U(t_0))_{j,k}|^2$, the fidelity of state transfer between vertices $j$ and $k$ at time $t_0$, is 1.
It is known that the unweighted path on $n$ vertices admits Laplacian PST only for $n=2$.
In this talk I will show that no weighted path on $n\geq 3$ vertices admits Laplacian PST between its end vertices.