Department of Mathematics & Statistics

Permanent URI for this communityhttps://hdl.handle.net/10294/339

Mathematics and Statistics are concerned with quantitative and geometric structure and form, and making inferences from limited information. Knowledge of mathematics and statistics has become indispensable in subjects as diverse as the traditional sciences, economics, administration, computer science, medicine and public policy. The Department has expertise and offers courses in the areas of algebra, analysis, geometry, graph theory, linear algebra, number theory, probability, statistics and topology.

To learn more about the department and its programs, visit the web site at: www.math.uregina.ca/

Browse

Now showing 1 - 20 of 38

Open Access
C.V.
(2014-01-21) Meagher, Karen
Open Access
Colin de Verdiere parameters of chordal graphs
(International Linear Algebra Society, 2013-01) Mitchell, Lon; Fallat, Shaun
The Colin de Verdi`ere parameters mu and nu are defined to be the maximum nullity of certain real symmetric matrices associated with a given graph. In this work, both of these parameters are calculated for all chordal graphs. For nu the calculation is based solely on maximal cliques, while for μ the calculation depends on split subgraphs. For the case of μ our work extends some recent work on computing μ for split graphs.
Open Access
Complex symmetric stabilizing solution of the matrix equation $X+A^{T}X^{-1}A=Q$
(Elsevier, 2011) Guo, Chun-Hua; Kuo, Yueh-Cheng; Lin, Wen-Wei
We study the matrix equation $X+A^{T}X^{-1}A=Q$, where $A$ is a complex square matrix and $Q$ is complex symmetric. Special cases of this equation appear in Green's function calculation in nano research and also in the vibration analysis of fast trains. In those applications, the existence of a unique complex symmetric stabilizing solution has been proved using advanced results on linear operators. The stabilizing solution is the solution of practical interest. In this paper we provide an elementary proof of the existence for the general matrix equation, under an assumption that is satisfied for the two special applications. Moreover, our new approach here reveals that the unique complex symmetric stabilizing solution has a positive definite imaginary part. The unique stabilizing solution can be computed efficiently by the doubling algorithm.
Open Access
Convergence Analysis of the Doubling Algorithm for Several Nonlinear Matrix Equations in the Critical Case
(SIAM, 2009) Chiang, Chun-Yueh; Chu, Eric King-Wah; Guo, Chun-Hua; Huang, Tsung-Ming; Lin, Wen-Wei; Xu, Shu-Fang
In this paper, we review two types of doubling algorithm and some techniques for analyzing them. We then use the techniques to study the doubling algorithm for three different nonlinear matrix equations in the critical case. We show that the convergence of the doubling algorithm is at least linear with rate 1/2. As compared to earlier work on this topic, the results we present here are more general, and the analysis here is much simpler.
Open Access
Convergence rates of some iterative methods for nonsymmetric algebraic Riccati equations arising in transport theory
(Elsevier, 2010) Guo, Chun-Hua; Lin, Wen-Wei
We determine and compare the convergence rates of various fixed-point iterations for finding the minimal positive solution of a class of nonsymmetric algebraic Riccati equations arising in transport theory.
Open Access
A convergence result for matrix Riccati differential equations associated with M-matrices
(2014-04-22) Guo, Chun-Hua; Yu, Bo
The initial value problem for a matrix Riccati differential equation associated with an $M$-matrix is known to have a global solution $X(t)$ on $[0, \infty)$ when $X(0)$ takes values from a suitable set of nonnegative matrices. It is also known, except for the critical case, that as $t$ goes to infinity $X(t)$ converges to the minimal nonnegative solution of the corresponding algebraic Riccati equation. In this paper we present a new approach for proving the convergence, which is based on the doubling procedure and is also valid for the critical case. The approach also provides a way for solving the initial value problem and a new doubling algorithm for computing the minimal nonnegative solution of the algebraic Riccati equation.
Open Access
Corrigendum to “The recognition problem for table algebras and reality-based algebras” [J. Algebra 479 (2017) 173–191]
(2019) Herman, Allen; Muzychuk, Mikhail; Xu, Bangteng
This note reports and corrects an error in the above article.
Open Access
Department of Mathematics and Statistics Annual Report 2004
(Department of Mathematics and Statistics, University of Regina, 2004) University of Regina. Dept. of Mathematics & Statistics.
Open Access
Detecting and solving hyperbolic quadratic eigenvalue problems
(SIAM, 2009) Guo, Chun-Hua; Higham, Nicholas J.; Tisseur, Francoise
Hyperbolic quadratic matrix polynomials $Q(\lambda) = \lambda^2 A + \lambda B + C$ are an important class of Hermitian matrix polynomials with real eigenvalues, among which the overdamped quadratics are those with nonpositive eigenvalues. Neither the definition of overdamped nor any of the standard characterizations provides an efficient way to test if a given $Q$ has this property. We show that a quadratically convergent matrix iteration based on cyclic reduction, previously studied by Guo and Lancaster, provides necessary and sufficient conditions for $Q$ to be overdamped. For weakly overdamped $Q$ the iteration is shown to be generically linearly convergent with constant at worst 1/2, which implies that the convergence of the iteration is reasonably fast in almost all cases of practical interest. We show that the matrix iteration can be implemented in such a way that when overdamping is detected a scalar $\mu < 0$ is provided that lies in the gap between the $n$ largest and $n$ smallest eigenvalues of the $n \times n$ quadratic eigenvalue problem (QEP) $Q(\lambda)x = 0$. Once such a $\mu$ is known, the QEP can be solved by linearizing to a definite pencil that can be reduced, using already available Cholesky factorizations, to a standard Hermitian eigenproblem. By incorporating an initial preprocessing stage that shifts a hyperbolic $Q$ so that it is overdamped, we obtain an efficient algorithm that identifies and solves a hyperbolic or overdamped QEP maintaining symmetry throughout and guaranteeing real computed eigenvalues.
Open Access
The enhanced principal rank characteristic sequence
(Elsevier, 2015) Butler, Steve; Catral, Minnie; Fallat, Shaun; Hall, Tracy; Hogben, Leslie; van den Driessche, Pauline; Young, michael
The enhanced principal rank characteristic sequence (epr-sequence) of a symmetric n ×n matrix is a sequence from A,S, or N according as all, some, or none of its principal minors of order k are nonzero. Such sequences give more information than the (0,1) pr-sequences previously studied (where basically the kth entry is 0 or 1 according as none or at least one of its principal minors of order k is nonzero). Various techniques including the Schur complement are introduced to establish that certain subsequences such as NAN are forbidden in epr-sequences over fields of characteristic not two. Using probabilistic methods over fields of characteristic zero, it is shown that any sequence ofAs andSs ending inAis attainable, and any sequence ofAs andSs followed by one or moreNs is attainable; additional families of attainable epr-sequences are constructed explicitly by other methods. For real symmetric matrices of orders 2, 3, 4, and 5, all attainable epr-sequences are listed with justifications.
Open Access
The enhanced principal rank characteristic sequence for skew-symmetric matrices
(Elsevier, 2015-08-15) Fallat, Shaun; Olesky, Dale; van den Driessche, Pauline
The enhanced principal rank characteristic sequence (epr-sequence) was originally defined for an n ×n real symmetric matrix or an n ×n Hermitian matrix. Such a sequence is defined to be l1l2···ln where lk is A,S, or N depending on whether all, some, or none of the matrix principal minors of order k are nonzero. Here we give a complete characterization of the attainable epr-sequences for real skew-symmetric matrices. With the constraint that lk=0 if k is odd, we show that nearly all epr-sequences are attainable by skew-symmetric matrices, which is in contrast to the case of real symmetric or Hermitian matrices for which many epr-sequences are forbidden. ©2015
Open Access
An Erdős-Ko-Rado theorem for finite \(2\)-transitive groups
(European Journal of Combinatorics, 2016) Meagher, Karen; Spiga, Pablo; Tiep, Pham Huu
We prove an analogue of the classical Erdős-Ko-Rado theorem for intersecting sets of permutations in finite \(2\)-transitive groups. Given a finite group \(G\) acting faithfully and \(2\)-transitively on the set \(\Omega\), we show that an intersecting set of maximal size in \(G\) has cardinality \(|G|/|\Omega|\). This generalises and gives a unifying proof of some similar recent results in the literature.
Open Access
An Erdős-Ko-Rado theorem for the derangement graph of \(PGL_3(q)\) acting on the projective plane
(SIAM J. Discrete Math. 28, 2014) Meagher, Karen; Spiga, Pablo
In this paper we prove an Erdős-Ko-Rado-type theorem for intersecting sets of permutations. We show that an intersecting set of maximal size in the projective general linear group \(PGL_3(q)\), in its natural action on the points of the projective line, is either a coset of the stabilizer of a point or a coset of the stabilizer of a line. This gives the first evidence to the veracity of Conjecture~\(2\) from K.~Meagher, P.~Spiga, An Erdős-Ko-Rado theorem for the derangement graph of \(\mathrm{PGL}(2,q)\) acting on the projective line, \( \textit{J. Comb. Theory Series A} \textbf{118} \) (2011), 532--544.
Open Access
An Erdos-Ko-Rado theorem for the derangement graph of PGL(2,q) acting on the projective plane
(SIAM Journal on Discrete Mathematics, 2014) Meagher, Karen; Spiga, Pablo
Let G = PGL(2, q) be the projective general linear group acting on the projec- tive line P_q. A subset S of G is intersecting if for any pair of permutations \pi and \sigma in S, there is a projective point p in P_q such that \pi(p)= \sigma(p). We prove that if S is intersecting, then |S| <= q(q-1). Also, we prove that the only sets S that meet this bound are the cosets of the stabilizer of a point of P_q. Keywords: derangement graph, independent sets, Erdos-Ko-Rado
Open Access
An Improved Arc Algorithm for Detecting Definite Hermitian Pairs
(SIAM, 2009) Guo, Chun-Hua; Higham, Nicholas J.; Tisseur, Francoise
A 25-year old and somewhat neglected algorithm of Crawford and Moon attempts to determine whether a given Hermitian matrix pair $(A,B)$ is definite by exploring the range of the function $f(x) = x^*(A + iB)x/|x^*(A + iB)x|$, which is a subset of the unit circle. We revisit the algorithm and show that with suitable modifications and careful attention to implementation details it provides a reliable and efficient means of testing definiteness. A clearer derivation of the basic algorithm is given that emphasizes an arc expansion viewpoint and makes no assumptions about the definiteness of the pair. Convergence of the algorithm is proved for all $(A,B)$, definite or not. It is shown that proper handling of three details of the algorithm is crucial to the efficiency and reliability: how the midpoint of an arc is computed, whether shrinkage of an arc is permitted, and how directions of negative curvature are computed. For the latter, several variants of Cholesky factorization with complete pivoting are explored and the benefits of pivoting demonstrated. The overall cost of our improved algorithm is typically just a few Cholesky factorizations. Applications of the algorithm are described to testing the hyperbolicity of a Hermitian quadratic matrix polynomial, constructing conjugate gradient methods for sparse linear systems in saddle point form, and computing the Crawford number of the pair $(A,B)$ via a quasiconvex univariate minimization problem.
Open Access
Intersecting generalized permutations
(2014-01-21) Borg, Peter; Meagher, Karen
Open Access
Iterative methods for a linearly perturbed algebraic matrix Riccati equation arising in stochastic control
(Taylor & Francis, 2013) Guo, Chun-Hua
We start with a discussion of coupled algebraic Riccati equations arising in the study of linear-quadratic optimal control problem for Markov jump linear systems. Under suitable assumptions, this system of equations has a unique positive semidefinite solution, which is the solution of practical interest. The coupled equations can be rewritten as a single linearly perturbed matrix Riccati equation with special structures. We study the linearly perturbed Riccati equation in a more general setting and obtain a class of iterative methods from different splittings of a positive operator involved in the Riccati equation. We prove some special properties of the sequences generated by these methods, and determine and compare the convergence rates of these methods. Our results are then applied to the coupled Riccati equations of jump linear systems. We obtain linear convergence of the Lyapunov iteration and the modified Lyapunov iteration, and confirm that the modified Lyapunov iteration indeed has faster convergence than the original Lyapunov iteration.
Open Access
The matrix equation $X+A^TX^{-1}A=Q$ and its application in nano research
(SIAM, 2010) Guo, Chun-Hua; Lin, Wen-Wei
The matrix equation $X+A^TX^{-1}A=Q$ has been studied extensively when $A$ and $Q$ are real square matrices and $Q$ is symmetric positive definite. The equation has positive definite solutions under suitable conditions, and in that case the solution of interest is the maximal positive definite solution. The same matrix equation plays an important role in Green's function calculations in nano research, but the matrix $Q$ there is usually indefinite (so the matrix equation has no positive definite solutions) and one is interested in the case where the matrix equation has no positive definite solutions even when $Q$ is positive definite. The solution of interest in this nano application is a special weakly stabilizing complex symmetric solution. In this paper we show how a doubling algorithm can be used to find good approximations to the desired solution efficiently and reliably.
Open Access
The maximum nullity of a complete edge subdivision graph is equal to it zero forcing number
(International Linear Algebra Society, 2014-06) Barrett, Wayne; Butler, Steve; Catral, Minnie; Hall, Tracy; Fallat, Shaun; Hogben, Leslie; Young, Michael
Barrett et al. asked in [W. Barrett et al. Minimum rank of edge subdivisions of graphs. Electronic Journal of Linear Algebra, 18:530–563, 2009.], whether the maximum nullity is equal to the zero forcing number for all complete subdivision graphs. We prove that this equality holds. Furthermore, we compute the value of M(F, °G) = Z(°G) by introducing the bridge tree of a connected graph. Since this equality is valid for all fields, °G has field independent minimum rank, and we also show that °G has a universally optimal matrix.
Open Access
MIKL´ OS-MANICKAM-SINGHI CONJECTURES ON PARTIAL GEOMETRIES
(2016-06) Meagher, Karen; Ihringer, Ferdinand
In this paper we give a proof of the Mikl´os-Manickam-Singhi (MMS) conjecture for some partial geometries. Specifically, we give a condition on partial geometries which implies that the MMS conjecture holds. Further, several specific partial geometries that are counterexamples to the conjecture are described.