Réunion d'été SMC 2024
Saskatchewan, 2 mai - 3 juin 2024
Problèmes inverses des valeurs propres et théorie des matrices
Org: Shaun Fallat et Himanshu Gupta (University of Regina)
[PDF]
Org: Shaun Fallat et Himanshu Gupta (University of Regina)
[PDF]
- SHAUN FALLAT
Bordering Matrices and the Inverse Eigenvalue Problem for Graphs [PDF]
-
An important parameter tied to the inverse eigenvalue problem for graphs is the fewest number of distinct eigenvalues that can be realized by a given graph. To this end we concentrate on bordering a symmetric matrix associated with a given graph and endeavor to control the variation in the number of distinct eigenvalues under this operation. We examine numerous results on the study of the minimum number of distinct eigenvalues as vertices are joined to certain classes of graphs.
- CHUN-HUA GUO, University of Regina
On absolute value equations associated with M-matrices [PDF]
-
We consider the absolute value equation (AVE) $Ax-|x|=b$, where $A$ is an $n\times n$ matrix such that
$A-I$ is a nonsingular $M$-matrix or an irreducible singular $M$-matrix. We show that the generalized Newton method (GNM) terminates with the exact unique solution
in at most $n+2$ iterations when $A-I$ is a nonsingular $M$-matrix and in at most $n+1$ iterations when $A-I$ is an irreducible singular $M$-matrix and the AVE has a unique solution. When $A-I$ is an irreducible singular $M$-matrix, the AVE may have infinitely many solutions. In this case, we show that GNM always terminates (in at most $n+1$ iterations) with a uniquely identifiable solution, as long as the initial guess has at least one nonpositive component. The GNM requires $O(n^3)$ operations each iteration. Linear convergence of a generalized Gauss-Seidel iteration (GGS), which requires $O(n^2)$ operations each iteration, is known when $A-I$ is a nonsingular $M$-matrix.
We show that GGS is still linearly convergent when $A-I$ is an irreducible singular $M$-matrix and the AVE has a unique solution.
- HIMANSHU GUPTA, University of Regina
Matrix positivity preservers over finite fields [PDF]
-
We resolve an algebraic version of Schoenberg's celebrated theorem characterizing the functions $f$ with the property that the matrix $(f(a_{ij}))$ is positive definite for any positive definite matrix $(a_{ij})$. Compared to the classical real and complex settings, we consider matrices with entries in a finite field. Here, we say that such a matrix is positive definite if all its leading principal minors are non-zero quadratic residues. We obtain a complete characterization of entrywise positivity preservers in that setting for matrices of a fixed dimension. When the dimension of the matrices is at least 3, we prove that, surprisingly, the positivity preservers are precisely the positive multiples of the field's automorphisms. We also provide a new connection between entrywise positivity preservers and automorphisms of Paley graphs. This is joint work with Dominique Guillot (University of Delaware) and Prateek Kumar Vishwakarma (Indian Institute of Science). The talk is based on the paper: https://arxiv.org/abs/2404.00222.
- NATHAN JOHNSTON, Mount Allison University
The Inverse Eigenvalue Problem for Entanglement Witnesses [PDF]
-
In quantum information theory, a linear operator that can detect entanglement in a quantum system is called an entanglement witnesses. We consider the inverse eigenvalue problem for entanglement witnesses, which asks for a characterization of their possible spectra. Equivalently, we consider the problem of classifying the spectra that can result from applying a positive linear map to a single tensor factor of a positive semidefinite matrix. We completely solve this problem in some low dimensions and we derive a large family of new necessary conditions on the spectra in arbitrary dimensions.
- AVLEEN KAUR, The University of British Columbia
Estimating the minimum positive eigenvalue of PSD matrices [PDF]
-
An extensive body of literature addresses the estimation of eigenvalues of the sum of two symmetric matrices, $P + Q$, in relation to the eigenvalues of $P$ and $Q$. Recently, we introduced two novel lower bounds on the minimum eigenvalue, $\lambda_{\min}(P+Q)$, under the conditions that matrices $P$ and $Q$ are symmetric positive semi-definite (PSD) and their sum $P+Q$ is non-singular. These bounds rely on the Friedrichs angle between the range spaces of matrices $P$ and $Q$, which are denoted by $\mathcal{R}(P)$ and $\mathcal{R}(Q)$, respectively. In addition, both results led to the derivation of several new lower bounds on the minimum singular value of full-rank matrices. We extend these insights to estimate the minimum positive eigenvalue of $P+Q$, $\lambda_{\min}(P+Q)$, even if $P+Q$ is singular, in terms of the minimum positive eigenvalues of $P$ and $Q$, namely $\lambda_{\min}(P)$ and $\lambda_{\min}(Q)$. Our approach leverages angles between specific subspaces of $\mathcal{R}(P)$ and $\mathcal{R}(Q)$, meticulously chosen to yield a positive lower bound. Additionally, we illustrate these concepts through relevant examples.
- STEVE KIRKLAND, University of Manitoba
Stochastic matrices and the boundary of the Karpelevich region [PDF]
-
A square nonnegative matrix with all row sums equal to 1 is known as a stochastic matrix, and the eigenvalues of such matrices are central to the study of Markov chains. Given a natural number $n$, the corresponding Karpelevich region is the subset of the complex plane consisting of all eigenvalues of arising from stochastic matrices of order $n$. In this talk we report on some recent progress on the problem of characterizing the stochastic matrices having a complex eigenvalue on the boundary of the corresponding Karpelevich region. Joint work with Helena Smigoc and Priyanka Joshi.
- AHMAD MOJALLAL, University of Regina
Nonregular Graphs with Three Eigenvalues [PDF]
-
In this talk, we study nonregular graphs with three eigenvalues. We look at the well-known results in this area, focusing particularly on addressing a question posed by Muzychuk and Klin in their paper [M. Muzychuk, M. Klin, On graphs with three eigenvalues, Discrete Mathematics 189 (1998) 191-207] "Is there an upper bound for the number of distinct degrees in a graph? If so, then find it".
- RAJESH PEREIRA, University of Guelph
Correlation Matrices: The Inverse Eigenvalue and Other Problems. [PDF]
-
We examine some problems relating to the convex hull of the rank one correlation matrices. One key problem we look at is the problem of determining the set of all possible spectra of matrices in the convex hull of the real rank one correlation matrices. We show relations between this problem and other areas of mathematics such as the geometry of polynomials and the existence of Hadamard matrices.
We also examine the relationship between the convex hull of $n \times n$ rank one correlation matrices and the set of all $n \times n$ correlation matrices. Relations between this problem and other areas of mathematics such as the theory of positive definite functions on groups and Grothendieck's inequality are explored.
- SARAH PLOSKER, Brandon University
Spectral Inequalities for Factor Width of a Matrix [PDF]
-
A Hermitian matrix $X $ is called $k$-locally positve semidefinite if every $k \times k$ principal submatrix of $X$ is positive semidefinite. We develop some bounds on the possible spectra of $k$-locally PSD matrices, and present a method for numerically constructing a $k$-locally PSD matrix with a given spectrum. We explore the connection to the concept of $k$-incoherent states from quantum information theory. This is joint work with Nathaniel Johnston, Shirin Moein, and Rajesh Pereira.
- CHRISTOPHER RAMSEY, MacEwan University
The numerical diameter of linear maps [PDF]
-
The numerical range and the numerical radius are much loved and much studied objects as they extend the eigenvalue information of a matrix into the non-normal setting. In this joint work with Niel de Beaudrap (Sussex) we study the diameter of the numerical range and the induced seminorm on linear maps between operator systems. In particular, the completely bounded numerical diameter is a norm comparable to but distinct from the completely bounded norm.
- BRENDAN ROONEY, Rochester Institute of Technology
Sparse Graphs with $q(G)=2$ [PDF]
-
Given a graph $G$ on $n$ vertices, $\mathcal{S}(G)$ is the set of symmetric $n\times n$ matrices with the same off-diagonal zero pattern as the adjacency matrix of $G$. We say that a connected graph $G$ has $q(G)=2$ if there is a matrix $M\in \mathcal{S}(G)$ with exactly $2$ distinct eigenvalues.
Recently, Barrett et al. (Barrett et al. Sparsity of graphs that allow two distinct eigenvalues. Linear Algebra Appl. 674(2023), 377–395) proved that graphs on $n$ vertices with $q(G)=2$ must have $|E(G)| \geq 2n-4$. They also showed that the odd-order graphs with $q(G)=2$ have $|E(G)|\geq 2n-3$, and characterized the odd-order graphs that meet this bound. We complete the characterization of graphs with $|E(G)|=2n-3$ and $q(G)=2$ by treating the even-order case. As part of our characterization, we resolve an open question of Barrett et al. by determining for each double-ended candle $H$, the sets of non-edges $S$ for which $q(H+S)=2$.
- HRISTO SENDOV, The University of Western Ontario
On the Hadamard-Fischer Inequality, the Inclusion-Exclusion Formula, and Bipartite Graphs [PDF]
-
The classical Hadamard-Fischer-Koteljanskii inequality is an inequality between principal minors of positive definite matrices. In this work, we present an extension of the Hadamard-Fischer-Koteljanskii inequality, that is inspired by the inclusion-exclusion formula for sets. We formulate necessary and sufficient conditions for the inequality to hold. We describe general structures of the collection of index sets involved. In analyzing these structures, a graph-theoretical property that applies to bipartite graphs is found. We establish that if the vertices of a bipartite graph satisfy simple conditions, then the bipartite graph contains a vertex subgraph which is a cycle or a complete subgraph missing a matching. This result is reminiscent of the Hall's marriage theorem for bipartite graphs.
- MAHSA SHIRAZI, University of Manitoba
Weakly Hadamard Diagonalizable Graphs [PDF]
-
An interesting question in the spectral graph theory is about the structure of the eigenvectors of matrices associated with graphs. A graph is weakly Hadamard diagonalizable (WHD) if its Laplacian matrix $L$ can be diagonalized with a weakly Hadamard matrix. In other words, if $L = PDP^{-1}$, where $D$ is a diagonal matrix and P has the property that all entries in $P$ are from $\{ 0,-1,1 \}$ and that $P^{t}P$ is a tridiagonal matrix. In this talk, I will present some necessary and sufficient conditions for a graph to be WHD. Also some families of graphs which are WHD, will be presented.
This work is part of a research project done with the discrete math research group (DMRG) at the University of Regina
- JACIK SZMIGIELSKI, Department of Mathematics and Statistics, University of Saskatchewan
Peakon inspired spectral and inverse spectral problems [PDF]
-
Peakon equations form a class of non-linear PDEs with weak (distributional) solutions akin to solitons but non-smooth. They can be studied using isospectral (spectrum preserving) deformations of boundary value problems, which generally are non-selfadjoint. Yet, these boundary value problems are multifold covers of spectral problems involving oscillatory kernels of the Gantmacher-Krein type. The inverse spectral problems for those lead to mixed Hermite-Pad\'{e} approximations. In this talk, I will illustrate some of these ideas with two examples of peakon-bearing equations: the Novikov equation and a two-component Novikov equation. This talk is in part based on joint work with X. Chang.
- HEIN VAN DER HOLST, Georgia State University
Digraphs with maximum stable nullity at most 1 [PDF]
-
For a digraph $D$ with vertex-set $V=\{1,\ldots,n\}$ and arc-set $A$, let $Q(D)$ be the set of all real $n\times n$ matrices $A=[a_{i,j}]$ with $a_{i,j}\not=0$ if $ij\in A$, $a_{i,i}\not=0$ for $i\in V$, and $a_{i,j}=0$ if $i\not=j$ and $ij\not\in A$. We say that a matrix $A\in Q(D)$ satisfies the ASAP if for all $A\circ X = 0$, $A X^T = 0$ and $X^T A = 0$ implies $X=0$. The stable maximum nullity $Ms(D)$ of a digraph $D$ is the maximum nullity of any $A\in Q(D)$ satisfying the ASAP. A digraph $D$ has $M_s(D)=0$ if and only if $D$ has no directed cycles.
If $D$ is a digraph, we denote by $\overleftarrow{D}$ the digraph obtained from $D$ by reversing each arrow.
In this talk, we show that the digraphs $D$ with $M_s(D)\leq 1$ are exactly the digraphs $D$ such that $D$ and $\overleftarrow{D}$ have Kelly-width $\leq 1$ .
- PETER ZIZLER, Mount Royal University
On loading matrices with non negative entries [PDF]
-
Loading matrices arising in principal component analysis are not unique. For a given factor loading problem it is desirable to determine
whether factor loadings that are all non negative do exist. We give sufficient conditions for the existence of a non negative loading matrix and discuss some of its consequences.