Thomas R. Cameron

In this article, we extend the notion of the Laplacian spread to simple directed graphs (digraphs) using the restricted numerical range. First, we provide Laplacian spread values for several families of digraphs. Then, we prove sharp upper bounds on the Laplacian spread for all polygonal and balanced digraphs. In particular, we show that the validity of the Laplacian spread bound for balanced digraphs is equivalent to the Laplacian spread conjecture for simple undirected graphs, which was conjectured in 2011 and proven in 2021. Moreover, we prove an equivalent statement for weighted balanced digraphs with weights between 0 and 1. Finally, we state several open conjectures that are motivated by empirical data.

• Publication
• Pre-Print

In 2020, Cameron et al. introduced the restricted numerical range of a digraph (directed graph) as a tool for characterizing digraphs and studying their algebraic connectivity. Notably, digraphs with a degenerate polygon (that is, a point or a line segment) as a restricted numerical range were completely described. In this article, we extend those results to include digraphs whose restricted numerical range is a non-degenerate convex polygon. In general, we refer to digraphs whose restricted numerical range is a degenerate or non-degenerate convex polygon as polygonal. We provide computational methods for identifying these polygonal digraphs and show that they can be broken into three disjoint classes: normal, restricted-normal, and pseudo-normal digraphs. Sufficient conditions for normal digraphs are provided, and we show that the directed join of two normal digraphs results in a restricted-normal digraph. Moreover, we prove that directed joins are the only restricted-normal digraphs when the order is square-free or twice a square-free number. Finally, we provide methods to construct restricted-normal digraphs that are not directed joins for all orders that are neither square-free nor twice a square-free number.

• Publication
• Pre-Print

Several researchers have recently explored various graph parameters that can or cannot be characterized by the spectrum of a matrix associated with a graph. In this paper, we show that several NP-hard zero forcing numbers are not characterized by the spectra of several types of associated matrices with a graph. In particular, we consider standard zero forcing, positive semidefinite zero forcing, and skew zero forcing and provide constructions of infinite families of pairs of cospectral graphs, which have different values for these numbers. We explore several methods for obtaining these cospectral graphs including using graph products, graph joins, and graph switching. Among these, we provide a construction involving regular adjacency cospectral graphs; the regularity of this construction also implies cospectrality with respect to several other matrices including the Laplacian, signless Laplacian, and normalized Laplacian. We also provide a construction where pairs of cospectral graphs can have an arbitrarily large difference between their zero forcing numbers.

• Publication
• Pre-Print

In this article, we use the complex compensated Horner method to derive a compensated Ehrlich-Aberth method for the accurate computation of all roots, real or complex, of a polynomial. In particular, under suitable conditions, we prove that the limiting accuracy for the compensated Ehrlich-Aberth iterations is as accurate as if computed in twice the working precision and then rounded to the working precision. Moreover, we derive a running error bound for the complex compensated Horner method and use it to form robust stopping criteria for the compensated Ehrlich-Aberth iterations. Finally, extensive numerical experiments illustrate that the backward and forward errors of the root approximations computed via the compensated Ehrlich-Aberth method are similar to those obtained with a quadruple precision implementation of the Ehrlich-Aberth method with a significant speed-up in terms of computation time.

• Publication
• Pre-Print

In 2019, Anderson et al. proposed the concept of rankability, which refers to a dataset's inherent ability to be meaningfully ranked. In this article, we give an expository review of the linear ordering problem (LOP) and then use it to analyze the rankability of data. Specifically, the degree of linearity is used to quantify what percentage of the data aligns with an optimal ranking. In a sports context, this is analogous to the number of games that a ranking can correctly predict in hindsight. In fact, under the appropriate objective function, we show that the optimal rankings computed via the LOP maximize the hindsight accuracy of a ranking. Moreover, we develop a binary program to compute the maximal Kendall tau ranking distance between two optimal rankings, which can be used to measure the diversity among optimal rankings without having to enumerate all optima. Finally, we provide several examples from the world of sports and college rankings to illustrate these concepts and demonstrate our results.

• Publication
• Pre-Print

In this article, we present the restricted numerical for the Laplacian matrix of a directed graph (digraph). We motivate our interest in the restricted numerical range by its close connection to the algebraic connectivity of a digraph. Moreover, we show that the restricted numerical range can be used to characterize digraphs, some of which are not determined by their Laplacian spectrum. Finally, we identify a new class of digraphs that are characterized by having a real restricted numerical range.

• Publication
• Pre-Print

Recently, Anderson et al. (2019) proposed the concept of rankability, which refers to a dataset's inherent ability to produce a meaningful ranking of its items. In the same paper, they proposed a rankability measure that is based on an integer program for computing the minimum number of edge changes made to a directed graph in order to obtain a complete dominance graph, i.e., an acyclic tournament graph. In this article, we prove a spectral-degree characterization of complete dominance graphs and apply this characterization to produce a new measure of rankability that is cost-effective and more widely applicable. We support the details of our algorithm with several results regarding the conditioning of the Laplacian spectrum of complete dominance graphs and the Hausdorff distance between their Laplacian spectrum and that of an arbitrary directed graph with weights between zero and one. Finally, we analyze the rankability of datasets from the world of chess and college football.

• Publication
• Pre-Print

We present a generalization of Householder sets for matrix polynomials. After defining these sets, we analyze their topological and algebraic properties, which include containing all of the eigenvalues of a given matrix polynomial. Then, we use instances of these sets to derive the Geršgorin set, weighted Geršgorin set, and weighted pseudospectra of a matrix polynomial. Finally, we show that Householder sets are intimately connected to the Bauer-Fike theorem by using these sets to derive Bauer-Fike-type bounds for matrix polynomials.

• Publication
• Pre-Print

We present a generalized Descartes’ rule of signs for self-adjoint matrix polynomials whose coefficients are either positive or negative definite, or null. In particular, we conjecture that the number of real positive (negative) eigenvalues of a matrix polynomial is bounded above by the product of the size of the matrix coefficients and the number of definite sign alternations (permanences) between consecutive coefficients. Our main result shows that this generalization holds under the additional assumption that the matrix polynomial is hyperbolic. In addition, we prove individual cases where the matrix polynomial is diagonalizable by congruence, or of degree three or less. The full proof of our conjecture is an open problem; we discuss analytic and algebraic approaches for solving this problem and ultimately, what makes this open problem non-trivial. Finally, we prove generalizations of two famous extensions of Descartes’ rule: If all eigenvalues are real then the bounds in Descartes’ rule are sharp and the number of real positive and negative eigenvalues have the same parity as the associated bounds in Descartes’ rule.

• Publication
• Pre-Print

Expository article on floating-point arithmetic, the floating-point error in basic calculations, and the use compensated arithmetic to remove these errors.

• Publication

We present a novel perspective on developing the determinant through the lens of signed volume. Starting with a unique and rigorous development of both the volume and orientation of a parallelepiped, we are able to give an unambiguous, basis-free definition for the determinant of a linear transformation. We then build intuition for the determinant by proving many of its properties in a succinct and basis-free fashion. We conclude our journey by using these properties to derive a well-known method for computing the determinant and motivating the Laplace expansion.

• Publication

Two common strategies for computing all roots of a polynomial with Laguerre’s method are explicit deflation and Maehly’s procedure. The former is only a semi-stable process and is not suitable for solving large degree polynomial equations. In contrast, the latter implicitly deflates the polynomial using previously accepted roots and is, therefore, a more practical strategy for solving large degree polynomial equations. However, since the roots of a polynomial are computed sequentially, this method cannot take advantage of parallel systems. In this article, we present an implementation of a modified Laguerre method for the simultaneous approximation of all roots of a polynomial. We provide a derivation of this method along with a detailed analysis of our algorithm’s initial estimates, stopping criterion, and stability. Finally, the results of several numerical experiments are provided to verify our analysis and the effectiveness of our algorithm.

• Publication
• Pre-Print

It is well known that every real or complex square matrix is unitarily similar to an upper Hessenberg matrix. The purpose of this paper is to provide a constructive proof of the result that every square matrix polynomial can be reduced to an upper Hessenberg matrix, whose entries are rational functions and in special cases polynomials. It will be shown that the determinant is preserved under this transformation, and both the finite and infinite eigenvalues of the original matrix polynomial can be obtained from the upper Hessenberg matrix.

• Publication

It is well known that the eigenvalues of any unitary matrix lie on the unit circle. The purpose of this paper is to prove that the eigenvalues of any matrix polynomial, with unitary coefficients, lie inside the annulus centered at the origin with inner radius 1/2 and outer raidus 2. The foundations of this result rely on an operator version of Roucheâs theorem and the intermediate value theorem.

• Publication