Réunion d'hiver SMC 2023

Montréal, 1 - 4 decembre 2023


Advancements in Matrix Theory with Applications
Org: Avleen Kaur (University of British Columbia), Karen Meagher (University of Regina) et Hermie Monterde (University of Manitoba)

LUDOVICK BOUTHAT, Université Laval
The Geometry of the Birkhoff Polytope  [PDF]

The geometry of the Birkhoff polytope, i.e., the compact convex set of all $n \times n$ doubly stochastic matrices, has been an active subject of research. While its faces, edges and facets as well as its volume have been intensely studied, other geometric characteristics such as the center and radius were left off, despite their natural uses in some areas of mathematics. In this talk, we present recent results on the Chebyshev center and the Chebyshev radius of the Birkhoff polytope associated with the metrics induced by the operator norms from $\ell^p_n$ to $\ell^p_n$ and by the Schatten $p$-norms, both for the range $1 \leq p \leq \infty$. While studying these properties, an intrinsic connection to the minimal trace, which naturally appears in the assignment problem, is also established.

JANE BREEN, Ontario Tech University
A structured condition number for Kemeny's constant  [PDF]

Kemeny's constant is an interesting and useful quantifier describing the global average behaviour of a Markov chain. In this talk, we will examine the sensitivity of Kemeny's constant to perturbations in the transition probabilities of the Markov chain. That is, we consider the problem of generating a condition number for Kemeny's constant, to give an indication of the size of the change in its value relative to the size of the perturbation. We will motivate this investigation with some interesting applications of Kemeny's constant.

MINERVA CATRAL, Xavier University
Spectral properties of a structured matrix related to a system of second order ODEs  [PDF]

We consider real matrices of the form $C = \left[\begin{array}{cc} A & B \\ I & O\end{array}\right]$ where $A, B$ are square matrices and $I, O$ are the identity matrix and zero matrix, respectively. Such matrices arise from dynamical systems of second-order ordinary differential equations $\ddot{\mathbf{x}} = A\dot{\mathbf{x}} + B \mathbf{x}$ where $A$ and $B$ are real matrices of order $n$. Eigenvalue properties are studied for the sign pattern $\mathcal{C} = \left[\begin{array}{cc} \mathcal{A} & \mathcal{B} \\ \mathcal{D} & O\end{array}\right]$ of order $2n$, where $\mathcal{A}, \mathcal{B}$ are the sign patterns of $A, B$ respectively, and $\mathcal{D}$ is a positive diagonal sign pattern. This talk gives an overview of results from joint works with Adam Berliner, D.D. Olesky and P. van den Driessche.

JOCELYN CHI, Rice University
Revisiting Symmetric Tensor Decompositions  [PDF]

In this work we present a simple method for computing a symmetric CP decomposition based on a Gauss-Newton linearization. The algorithm requires solving a sequence of linear least squares problems. With modest modification our approach can be extended to compute symmetric decompositions under additional constraints such as nonnegativity and sparsity. We present empirical results highlighting the effectiveness of the approach. This is joint work with Eric Chi.

CHRISTINA CHRISTARA, University of Toronto, Depart. of Computer Science
Properties of matrices arising from Black-Scholes equations  [PDF]

The Black-Scholes equation and various versions of it are used for modelling many financial problems. While the Black-Scholes equation is a parabolic Partial Differential Equation (PDE) and it is often discretized by typical centered finite differences in space and Crank-Nicolson timestepping, it is not as ``typical'' parabolic PDE, as many would think. In this talk, we discuss some of the peculiarities these parabolic PDE problems exhibit, including positive and negative interest rates, unusual boundary conditions, special nonuniform grids, vanishing coefficients, etc, and the effect these have on the arising matrices. We also discuss the performance of certain solvers and preconditioners for the arising discrete equations.

MALENA ESPANOL, Arizona State University
Variable Projection Methods for Separable Nonlinear Inverse Problems  [PDF]

Variable projection methods are among the classical and efficient methods to solve separable nonlinear least squares problems. In this talk, I will introduce the variable projection method to solve large-scale blind deconvolution problems.

ERIC EVERT, Northwestern University
Free extreme points of free spectrahedrops and generalized free spectrahedra  [PDF]

Matrix convexity generalizes convexity to the dimension free setting and has connections to many mathematical and applied pursuits including operator theory, quantum information, noncommutative optimization, and linear control systems. In the setting of classical convex sets, extreme points are central objects. For example, the well-known Minkowski theorem shows that any element of a closed bounded convex set can be expressed as a convex combination of extreme points. Extreme points are also of great interest in the dimension free setting of matrix convex sets; however, here the situation requires more nuance, as there are many types of extreme points for matrix convex sets. Of particular interest are free extreme points, a highly restricted type of extreme point that is connected to the dilation theoretic Arveson boundary.

Building on a recent work of J. W. Helton and the speaker which shows that free spectrahedra, i.e., dimension free solution sets to linear matrix inequalities, are spanned by their free extreme points, this talk establishes two additional classes of matrix convex sets that are spanned by their free extreme points. Namely, we show that closed bounded free spectrahedrops, i.e, closed bounded projections of free spectrahedra, are the span of their free extreme points. Furthermore, we show that if one considers linear operator inequalities that have compact operator defining tuples, then the resulting ``generalized" free spectrahedra are spanned by their free extreme points.

AVLEEN KAUR, The University of British Columbia
Unravelling the Friedrichs Angle: A Key to Lower Bounds on the Minimum Singular Value  [PDF]

Estimating the eigenvalues of a sum of two symmetric matrices, say $P+Q$, in terms of the eigenvalues of $P$ and $Q$, has a long tradition. To our knowledge, no study has yielded a positive lower bound on the minimum eigenvalue, $\lambda_{\min}(P+Q)$, when $P+Q$ is symmetric positive definite with $P$ and $Q$ singular positive semi-definite. We derive two new lower bounds on $\lambda_{\min}(P+Q)$ in terms of the minimum positive eigenvalues of $P$ and $Q$. The bounds take into account geometric information by utilizing the Friedrichs angles between certain subspaces. The basic result is when $P$ and $Q$ are two non-zero singular positive semi-definite matrices such that $P+Q$ is non-singular, then $\lambda_{\min}(P+Q)\geq (1-\cos\theta_F)\min\{\lambda_{\min}(P),\lambda_{\min}(Q)\}$, where $\lambda_{\min}$ represents the minimum positive eigenvalue of the matrix, and $\theta_F$ is the Friedrichs angle between the range spaces of $P$ and $Q$. We will discuss the interaction between the range spaces for some pair of small matrices to elucidate the geometric aspect of these bounds. Such estimates lead to new lower bounds on the minimum singular value of full rank $1\times 2$, $2\times 1$, and $2\times 2$ block matrices in terms of the minimum positive singular value of these blocks. Some examples provided in this talk further highlight the simplicity of applying the results in comparison to some existing lower bounds. This is joint work with S. H. Lui (University of Manitoba).

BROCK KLIPPENSTEIN, University of Manitoba
Numerical Solution of Non-Normal Coefficient Sylvester Equations for Partial Differential Equations  [PDF]

A method for solving certain partial differential equations, such as the heat or wave equation, numerically consists of discretizing the equation to obtain a matrix equation known as a Sylvester equation. It is well-known that Sylvester equations equations can be solved quickly if among other conditions, certain matrices are normal. In this talk, we will discuss to solve Sylvester equations while trading in the normality condition for a norm condition. The main tool used here is dilation theory, where we can view an operator as the top left entry of a bigger operator with nice properties, such as being normal. Additionally, we will look at an example of solving a partial integro-differential equation numerically which results in a Sylvester equation with a non normal coefficient.

This is joint work with Dr. Mikael Slevinsky and Dr. Raphael Clouatre.

ERIN MEGER, Queen's University
The Spectral Gap of Iterative Complex Networks  [PDF]

Complex Networks appear in applications all around us, from the internet to social networks. These networks exhibit a range of similar properties including large scale, power-law degree distribution, and small-world properties. Studying the spectral gap of complex networks reveals an understanding of the underlying community structures. We will explore the spectral gap of iterated models for complex networks. In these models, each subsequent graph is created through a deterministic generation algorithm, where nodes are cloned and preserve either in-group or out-group relationships. Furthermore, we will define the generalized model of the Iterative Independent Model, specifically exploring the spectral gap of graphs in this model.

HERMIE MONTERDE, University of Manitoba
Hadamard diagonalizability and generalizations  [PDF]

An $n$-by-$n$ matrix $H$ is a Hadamard matrix if $HH^T=nI$. We say that a matrix $M$ is Hadamard diagonalizable if $M=\frac{1}{n}HDH^T$ for some diagonal matrix $D$. In the context of graphs, we say that a graph $X$ is Hadamard diagonalizable if its Laplacian matrix $L$ is Hadamard diagonalizable. In this talk, we give an overview of results about the properties of Hadamard diagonalizable matrices and graphs, and discuss some generalizations. This talk is based on the work of Barik et al. (2011), Johnston et al. (2017), Chan et al. (2020), Breen et al. (2022), and McLaren et al. (2023).

The diameter of the Birkhoff polytope  [PDF]

The geometry of the compact convex set of all $n \times n$ doubly stochastic matrices, a structure frequently referred to as the Birkhoff polytope, has been an active subject of research as of late. While its faces, edges and facets as well as its volume have been intensely studied over the years, other geometric characteristics with respect to usual matrix norms have only recently been studied in depth. In this talk, we shall explore the question of determining the diameter of the Birkhoff polytope with respect to the metrics induced by the operator norms from $\ell_n^p$ to $\ell_n^p$ and the Schatten p-norms, both for the range $1 \leq p \leq \infty$.

PAUL SKOUFRANIS, York University
Matrix Majorization in Non-Commutative Contexts  [PDF]

The notion of majorization of one self-adjoint $n\times n$ matrix by another is a very useful concept in matrix theory. For example, a classical theorem of Schur and Horn states that a diagonal matrix $D$ is majorized by a self-adjoint matrix $B$ if and only if a unitary conjugate of $B$ has the same diagonal as $D$. Some equivalent characterizations of $A$ being majorized by $B$ include there existing a doubly stochastic matrix that maps the vector or eigenvalues of $B$ to the the vector or eigenvalues of $A$, tracial inequalities involving convex functions of $A$ and $B$, and there exists a mixed unitary quantum channel that maps $B$ to $A$.

In this talk, we will examine the notion of majorization in other non-commutative contexts. In particular, we will discuss a generalization of matrix majorization that works in any C$^*$-algebra, and a new non-commutative notion of majorization that characterizes the potential outputs under all unital quantum channels of any non-commutative tuple of matrices.

This talk is based on joint works with Ng and Robert, and with Kennedy and Marcoux.

HEATHER SWITZER, The College of William & Mary
Exploring the Advantages of Using Sketched Krylov Methods in PRIMME  [PDF]

In recent years, sketching methods have increased in popularity for large scale least-squares problems. This is due to the scalability and reliability of randomized subspace embeddings which turn a large problem into something more managable with minimal loss of accuracy in the solutions. It had been observed that Rayleigh-Ritz approaches in Krylov iterative methods can be written as a least-squares problem, and therefore may benefit from the use of sketching to extract approximate solutions from the eigenspace.

One known pitfall of Krylov methods is that as the Krylov basis is being built, the condition number can grow exponentially due to numerical error and repeated directions occurring. Theoretically, we can reorthogonalize the basis using techniques such as Gram-Schmidt or the QR decomposition. However, in practice, these methods are expensive to execute and result in a computational bottleneck, particularly when looking for a large number of eigenpairs.

One benefit of using sketching in conjunction with Krylov methods is that we can avoid having to reorthogonalize our basis frequently. In theory, as long as the condition number of the basis remains below $\epsilon_{\tt mach}$, sketched Rayleigh-Ritz should produce accurate Ritz vectors. Using the eigensolver software package PRIMME, we explore the benefits and disadvantages of using sketching with two popular Krylov methods, Lanczos and Davidson.

MICHAEL TAIT, Villanova University
Counting subgraphs using graph eigenvalues  [PDF]

We discuss how to use graph eigenvalues to count subgraphs of various graphs. We discuss the general framework of this problem and how it captures several problems in extremal graph theory, and then we show how to use graph eigenvalues to answer the problem in specific cases. Some applications include to combinatorial number theory, to geometric questions in graph theory, and to VC dimension.

IAN THOMPSON, University of Manitoba
Peaking phenomena in finite-dimensions  [PDF]

Complex function theory is a powerful tool for studying operators. Indeed, this is at the heart of numerous applications of the spectral theorem (functional calculi, von Neumann’s inequality), as well as countless modern developments. We focus on one connection to function theory that has garnered significant interest in recent years: non-commutative peak points. Their interest is, in part, justified by their ability to detect intrinsic components of a subspace of operators. In this talk, we will discuss a few formulations of peaking, with a particular focus on spaces of matrices. This includes joint work with Raphaël Clouâtre.

AMY YIELDING, Eastern Oregon University
An Investigation of Coefficient Sign Arbitrary Patterns  [PDF]

A square zero-nonzero pattern, $\mathcal{A}$, is a square matrix with entries in $\{0, \ast\}$. Such a pattern is said to be coefficient support arbitrary if for every $S\subseteq\{1,2,\ldots,n\}$ there is a matrix $A$ with zero-nonzero pattern $\mathcal{A}$ such that $\alpha_i\neq0$ if and only if $i\in S$, where $x^n+\alpha_1x^{n-1}+\alpha_2x^{n-2}+\ldots+\alpha_{n-1}x+\alpha_n$ is the characteristic polynomial of $A$. In this talk, we naturally extend this definition to coefficient sign arbitrary patterns and explore some initial results.

HARMONY ZHAN, Worcester Polytechnic Institute
Spectra of line digraphs and their applications  [PDF]

The line digraph of a graph $X$ has all arcs of $X$ as its vertices, and an arc $(a,b)$ is adjacent to an arc $(c,d)$ if $b=c$. In this talk, we will explore the spectra of some matrix representations of line digraphs, and see a few applications where $X$ is highly regular.

XIAOHONG ZHANG, Université de Montréal
Laplacian cospectral graphs  [PDF]

In this talk, we present a way of constructing Laplacian cospectral graphs by deleting edges of smaller Laplacian cospectral graphs from certain graphs. This has applications in subgraph transfer of continuous time quantum walks.

© Société mathématique du Canada : http://www.smc.math.ca/