Search

The longstanding nonnegative inverse eigenvalue problem (NIEP) is to determine which multisets of complex numbers occur as the spectrum of an entry-wise nonnegative matrix. Although there are some well-known necessary conditions, a solution to the NIEP is far from known. An invertible matrix is called a Perron similarity if it diagonalizes an irreducible, nonnegative matrix. Johnson and Paparella developed the theory of real Perron similarities. Here, we fully develop the theory of complex Perron similarities. Each Perron similarity gives a nontrivial polyhedral cone and polytope of realizable spectra (thought of as vectors in complex Euclidean space). The extremals of these convex sets are finite in number, and their determination for each Perron similarity would solve the diagonalizable NIEP, a major portion of the entire problem. By considering Perron similarities of certain realizing matrices of Type I Karpelevich arcs, large portions of realizable spectra are generated for a given positive integer. This is demonstrated by producing a nearly complete geometrical representation of the spectra of $4 \times 4$ stochastic matrices. Similar to the Karpelevich region, it is shown that the subset of complex Euclidean space comprising the spectra of stochastic matrices is compact and star-shaped. Extremal elements of the set are defined and shown to be on the boundary. It is shown that the polyhedral cone and convex polytope of the discrete Fourier transform (DFT) matrix corresponds to the conical hull and convex hull of its rows, respectively. Similar results are established for multifold Kronecker products of DFT matrices and multifold Kronecker products of DFT matrices and Walsh matrices. These polytopes are of great significance with respect to the NIEP because they are extremal in the region comprising the spectra of stochastic matrices., Comment: Submitted to Trans. Amer. Math. Soc

In decision making a weight vector is often obtained from a reciprocal matrix A that gives pairwise comparisons among n alternatives. The weight vector should be chosen from among efficient vectors for A. Since the reciprocal matrix is usually not consistent, there is no unique way of obtaining such a vector. It is known that all weighted geometric means of the columns of A are efficient for A. In particular, any column and the standard geometric mean of the columns are efficient, the latter being an often used weight vector. Here we focus on the study of the efficiency of the vectors in the (algebraic) convex hull of the columns of A. This set contains the (right) Perron eigenvector of A, a classical proposal for the weight vector, and the Perron eigenvector of AA^{T} (the right singular vector of A), recently proposed as an alternative. We consider reciprocal matrices A obtained from a consistent matrix C by modifying at most three pairs of reciprocal entries contained in a 4-by-4 principal submatrix of C. For such matrices, we give necessary and sufficient conditions for all vectors in the convex hull of the columns to be efficient. In particular, this generalizes the known sufficient conditions for the efficiency of the Perron vector. Numerical examples comparing the performance of efficient convex combinations of the columns and weighted geometric means of the columns are provided.

A $n$-by-$n$ matrix is called totally positive ($TP$) if all its minors are positive and $TP_k$ if all of its $k$-by-$k$ submatrices are $TP$. For an arbitrary totally positive matrix or $TP_k$ matrix, we investigate if the $r$th compound ($1

In prioritization schemes, based on pairwise comparisons, such as the Analytical Hierarchy Process, it is necessary to extract a cardinal ranking vector from a reciprocal matrix that is unlikely to be consistent. It is natural to choose such a vector only from efficient ones. One of the most used ranking methods employs the (right) Perron eigenvector of the reciprocal matrix as the vector of weights. It is known that the Perron vector may not be efficient. Here, we focus on extending arbitrary reciprocal matrices and show, constructively, that two different extensions of any fixed size always exist for which the Perron vector is inefficient and for which it is efficient, with the following exception. If B is consistent, any reciprocal matrix obtained from B by adding one row and one column has efficient Perron vector. As a consequence of our results, we obtain families of reciprocal matrices for which the Perron vector is inefficient. These include known classes of such matrices and many more. We also characterize the 4-by-4 reciprocal matrices with inefficient Perron vector. Some prior results are generalized or completed.

We focus upon the relationship between Hamiltonian cycle products and efficient vectors for a reciprocal matrix $A$, to more deeply understand the latter. This facilitates a new description of the set of efficient vectors (as a union of convex subsets), greater understanding of convexity within this set and of order reversals in efficient vectors. A straightforward description of all efficient vectors for an $n$-by-$n$, column perturbed consistent matrix is given; it is the union of at most $(n-1)$ choose $2$ convex sets.

Historically, the rotorcraft community has experienced a higher fatal accident rate than other aviation segments, including commercial and general aviation. Recent advancements in artificial intelligence (AI) and the application of these technologies in different areas of our lives are both intriguing and encouraging. When developed appropriately for the aviation domain, AI techniques provide an opportunity to help design systems that can address rotorcraft safety challenges. Our recent work demonstrated that AI algorithms could use video data from onboard cameras and correctly identify different flight parameters from cockpit gauges, e.g., indicated airspeed. These AI-based techniques provide a potentially cost-effective solution, especially for small helicopter operators, to record the flight state information and perform post-flight analyses. We also showed that carefully designed and trained AI systems could accurately predict rotorcraft attitude (i.e., pitch and yaw) from outside scenes (images or video data). Ordinary off-the-shelf video cameras were installed inside the rotorcraft cockpit to record the outside scene, including the horizon. The AI algorithm could correctly identify rotorcraft attitude at an accuracy in the range of 80\%. In this work, we combined five different onboard camera viewpoints to improve attitude prediction accuracy to 94\%. In this paper, five onboard camera views included the pilot windshield, co-pilot windshield, pilot Electronic Flight Instrument System (EFIS) display, co-pilot EFIS display, and the attitude indicator gauge. Using video data from each camera view, we trained various convolutional neural networks (CNNs), which achieved prediction accuracy in the range of 79\% % to 90\% %. We subsequently ensembled the learned knowledge from all CNNs and achieved an ensembled accuracy of 93.3\%.

In prioritization schemes, based on pairwise comparisons, such as the Analytical Hierarchy Process, it is important to extract a cardinal ranking vector from a reciprocal matrix that is unlikely to be consistent. It is natural to choose such a vector only from efficient ones. Recently a method to generate inductively all efficient vectors for any reciprocal matrix has been discovered. Here we focus upon the study of efficient vectors for a reciprocal matrix that is a block perturbation of a consistent matrix in the sense that it is obtained from a consistent matrix by modifying entries only in a proper principal submatrix. We determine an explicit class of efficient vectors for such matrices. Based upon this, we give a description of all the efficient vectors in the 3-by-3 block perturbed case. In addition, we give sufficient conditions for the right Perron eigenvector of such matrices to be efficient and provide examples in which efficiency does not occur. Also, we consider a certain type of constant block perturbed consistent matrices, for which we may construct a class of efficient vectors, and demonstrate the efficiency of the Perron eigenvector. Appropriate examples are provided throughout., Comment: arXiv admin note: text overlap with arXiv:2305.05307

Efficient vectors are the natural set from which to choose a cardinal ranking vector for a pairwise comparison matrix. Such vectors are the key to certain business project selection models. Many ways to construct specific efficient vectors have been proposed. Yet, no previous method to produce all efficient vectors was known. Here, using some graph theoretic ideas, as well as a numerical extension technique, we show how to generate inductively all efficient vectors for any given pairwise comparison matrix. We apply this method to give a matricial proof of the fact that the set of efficient vectors and other related sets are piecewise linearly connected. In addition, we determine explicitly all efficient vectors for a 4-by-4 pairwise comparison matrix. Several examples are provided.

The Analytic Hierarchy Process (AHP) is a much discussed method in ranking business alternatives based on empirical and judgemental information. We focus here upon the key component of deducing efficient vectors for a reciprocal matrix of pair-wise comparisons. It is not yet known how to produce all efficient vectors. It has been shown that the entry-wise geometric mean of all columns is efficient for any reciprocal matrix. Here, by combining some new basic observations with some known theory, we 1) give a method for inductively generating large collections of efficient vectors, and 2) show that the entry-wise geometric mean of any collection of distinct columns of a reciprocal matrix is efficient. We study numerically, using different measures, the performance of these geometric means in approximating the reciprocal matrix by a consistent matrix., Comment: 27 pages, 4 figures, 4 tables

A list $\Lambda =\{\lambda _{1},\ldots ,\lambda _{n}\}$ of complex numbers (repeats allowed) is said to be \textit{realizable} if it is the spectrum of an entrywise nonnegative matrix $A$. $\Lambda $ is \textit{diagonalizably realizable} if the realizing matrix $A$ is diagonalizable. $\Lambda $ is said to be \textit{universally realizable} if it is \textit{\ realizable} for each possible Jordan canonical form allowed by $\Lambda .$ Here, we study the connection between diagonalizable realizability and universal realizability of spectra. In particular, we establish \textit{\ indices of realizability} for diagonalizable and universal realizability. We also define the merge of two spectra and we prove a result that allow us to easily decide, in many cases, about the universal realizability of spectra., Comment: 1. Theorem 2.4: we say that we are going to prove that there is a minimum called diagonalizable realizability index, but we do not. 2. Corollary 2.1: We say that we may define a universal realizablity index, but we do not show that such index exists. Corollary 2.1 only show lower and upper bounds for that index

This work builds on the models and concepts presented in part 1 to learn approximate dictionary representations of Koopman operators from data. Part I of this paper presented a methodology for arguing the subspace invariance of a Koopman dictionary. This methodology was demonstrated on the state-inclusive logistic lifting (SILL) basis. This is an affine basis augmented with conjunctive logistic functions. The SILL dictionary's nonlinear functions are homogeneous, a norm in data-driven dictionary learning of Koopman operators. In this paper, we discover that structured mixing of heterogeneous dictionary functions drawn from different classes of nonlinear functions achieve the same accuracy and dimensional scaling as the deep-learning-based deepDMD algorithm. We specifically show this by building a heterogeneous dictionary comprised of SILL functions and conjunctive radial basis functions (RBFs). This mixed dictionary achieves the same accuracy and dimensional scaling as deepDMD with an order of magnitude reduction in parameters, while maintaining geometric interpretability. These results strengthen the viability of dictionary-based Koopman models to solving high-dimensional nonlinear learning problems., Comment: 16 pages, 6 figures. arXiv admin note: substantial text overlap with arXiv:2206.13585

Koopman operators model nonlinear dynamics as a linear dynamic system acting on a nonlinear function as the state. This nonstandard state is often called a Koopman observable and is usually approximated numerically by a superposition of functions drawn from a dictionary. In a widely used algorithm, Extended Dynamic Mode Decomposition, the dictionary functions are drawn from a fixed class of functions. Recently, deep learning combined with EDMD has been used to learn novel dictionary functions in an algorithm called deep dynamic mode decomposition (deepDMD). The learned representation both (1) accurately models and (2) scales well with the dimension of the original nonlinear system. In this paper we analyze the learned dictionaries from deepDMD and explore the theoretical basis for their strong performance. We explore State-Inclusive Logistic Lifting (SILL) dictionary functions to approximate Koopman observables. Error analysis of these dictionary functions show they satisfy a property of subspace approximation, which we define as uniform finite approximate closure. Our results provide a hypothesis to explain the success of deep neural networks in learning numerical approximations to Koopman operators. Part 2 of this paper will extend this explanation by demonstrating the subspace invariant of heterogeneous dictionaries and presenting a head-to-head numerical comparison of deepDMD and low-parameter heterogeneous dictionary learning., Comment: 13 pages, 2 figures. arXiv admin note: substantial text overlap with arXiv:2206.13585

Among those real symmetric matrices whose graph is a given tree $T$, the maximum multiplicity $M(T)$ that can be attained by an eigenvalue is known to be the path cover number of $T$. We say that a tree is $k$-NIM if, whenever an eigenvalue attains a multiplicity of $k-1$ less than the maximum multiplicity, all other multiplicities are $1$. $1$-NIM trees are known as NIM trees, and a characterization for NIM trees is already known. Here we provide a graph-theoretic characterization for $k$-NIM trees for each $k\geq 1$, as well as count them. It follows from the characterization that $k$-NIM trees exist on $n$ vertices only when $k=1,2,3$. In case $k=3$, the only $3$-NIM trees are simple stars., Comment: 20 pages, 5 figures

Koopman operators model nonlinear dynamics as a linear dynamic system acting on a nonlinear function as the state. This nonstandard state is often called a Koopman observable and is usually approximated numerically by a superposition of functions drawn from a \textit{dictionary}. A widely used algorithm, is \textit{Extended Dynamic Mode Decomposition}, where the dictionary functions are drawn from a fixed, homogeneous class of functions. Recently, deep learning combined with EDMD has been used to learn novel dictionary functions in an algorithm called deep dynamic mode decomposition (deepDMD). The learned representation both (1) accurately models and (2) scales well with the dimension of the original nonlinear system. In this paper we analyze the learned dictionaries from deepDMD and explore the theoretical basis for their strong performance. We discover a novel class of dictionary functions to approximate Koopman observables. Error analysis of these dictionary functions show they satisfy a property of subspace approximation, which we define as uniform finite approximate closure. We discover that structured mixing of heterogeneous dictionary functions drawn from different classes of nonlinear functions achieve the same accuracy and dimensional scaling as deepDMD. This mixed dictionary does so with an order of magnitude reduction in parameters, while maintaining geometric interpretability. Our results provide a hypothesis to explain the success of deep neural networks in learning numerical approximations to Koopman operators., Comment: 14 pages, 7 figures, journal paper

We present two complementary techniques called catalysis and inhibition which allow one to determine if a given pattern is TP completable or TP non-completable, respectively. Empirically, these techniques require considering only one unspecified entry at a time in a vast majority of cases, which makes these techniques ripe for automation and a powerful framework for future work in the TP completion problem. With small modifications, these techniques are also applicable to the TN completion problem. We provide two major applications. First, we characterize all 4-by-4 patterns by completability. There are a total of 78 new obstructions of this size, six times as many as the 3-by-$n$ case for all $n$ combined. Second, we provide a characterization of the so-called 1-variable obstructions in the TN case, which includes as a corollary a characterization of patterns with a single unspecified entry. This also provides a novel partial result towards proving the conjecture that all TN-completable patterns are TP-completable., Comment: 30 pages, 0 figures. Some typos fixed and additional references

We prove that checking if a partial matrix is partial totally positive is co-NP-complete. This contrasts with checking a conventional matrix for total positivity, for which we provide a cubic time algorithm. Checking partial sign regularity with any signature, including partial total nonnegativity, is also co-NP-complete. Finally, we prove that checking partial total positivity in a partial matrix with logarithmically many unspecified entries may be done in polynomial time., Comment: 4 pages, 0 figures; added Section 4 and minor corrections

The Gauss--Lucas and B\^{o}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., Comment: This is an Accepted Manuscript of an article published by Taylor & Francis in The American Mathematical Monthly on 19-Dec-2019, available at https://www.tandfonline.com/doi/10.1080/00029890.2020.1671740

We consider path-connected sets of matrices and the induced paths between eigenvalues. We discuss the equivalence relation generated by these paths, and how it relates to the presence of higher multiplicity eigenvalues realized by the set. Particular interest is applied to the convex hull of matrices, where additional characterizations are provided of this phenomena, and computational methods are given for further study.

The still-unsolved problem of determining the set of eigenvalues realized by $n$-by-$n$ doubly stochastic matrices, those matrices with row sums and column sums equal to $1$, has attracted much attention in the last century. This problem is somewhat algebraic in nature, due to a result of Birkhoff demonstrating that the set of doubly stochastic matrices is the convex hull of the permutation matrices. Here we are interested in a general matrix group $G \subseteq GL_n(\mathbb{C})$ and the hull spectrum $\text{HS}(G)$ of eigenvalues realized by convex combinations of elements of $G$. We show that hull spectra of matrix groups share many nice properties. Moreover, we give bounds on the hull spectra of matrix groups, determine $\text{HS}(G)$ exactly for important classes of matrix groups, and study the hull spectra of representations of abstract groups., Comment: 19 pages. This work was completed at the 2019 Matrix Analysis REU at the College of William & Mary

It is known (see e.g. [2], [4], [5], [6]) that continuous variations in the entries of a complex square matrix induce continuous variations in its eigenvalues. If such a variation arises from one real parameter $\alpha \in [0, 1]$, then the eigenvalues follow continuous paths in the complex plane as ${\alpha}$ shifts from $0$ to $1$. The intent here is to study the nature of these eigenpaths, including their behavior under small perturbations of the matrix variations, as well as the resulting eigenpairings of the matrices that occur at ${\alpha} = 0$ and ${\alpha} = 1$. We also give analogs of our results in the setting of monic polynomials., Comment: 19 pages. This work was completed at the 2019 Matrix Analysis REU at College of William & Mary

The problem of determining $DS_n$, the complex numbers that occur as an eigenvalue of an $n$-by-$n$ doubly stochastic matrix, has been a target of study for some time. The Perfect-Mirsky region, $PM_n$, is contained in $DS_n$, and is known to be exactly $DS_n$ for $n \leq 4$, but strictly contained within $DS_n$ for $n = 5$. Here, we present a Boundary Conjecture that asserts that the boundary of $DS_n$ is achieved by eigenvalues of convex combinations of pairs of (or single) permutation matrices. We present a method to efficiently compute a portion of $DS_n$, and obtain computational results that support the Boundary Conjecture. We also give evidence that $DS_n$ is equal to $PM_n$ for certain $n > 5$.

Wannier90 is an open-source computer program for calculating maximally-localised Wannier functions (MLWFs) from a set of Bloch states. It is interfaced to many widely used electronic-structure codes thanks to its independence from the basis sets representing these Bloch states. In the past few years the development of Wannier90 has transitioned to a community-driven model; this has resulted in a number of new developments that have been recently released in Wannier90 v3.0. In this article we describe these new functionalities, that include the implementation of new features for wannierisation and disentanglement (symmetry-adapted Wannier functions, selectively-localised Wannier functions, selected columns of the density matrix) and the ability to calculate new properties (shift currents and Berry-curvature dipole, and a new interface to many-body perturbation theory); performance improvements, including parallelisation of the core code; enhancements in functionality (support for spinor-valued Wannier functions, more accurate methods to interpolate quantities in the Brillouin zone); improved usability (improved plotting routines, integration with high-throughput automation frameworks), as well as the implementation of modern software engineering practices (unit testing, continuous integration, and automatic source-code documentation). These new features, capabilities, and code development model aim to further sustain and expand the community uptake and range of applicability, that nowadays spans complex and accurate dielectric, electronic, magnetic, optical, topological and transport properties of materials., Comment: 26 pages, 8 figures

We prove the sufficiency of the Linear Superposition Principle for linear trees, which characterizes the spectra achievable by a real symmetric matrix whose underlying graph is a linear tree. The necessity was previously proven in 2014. This is the most general class of trees for which the inverse eigenvalue problem has been solved. We explore many consequences, including the Degree Conjecture for possible spectra, upper bounds for the minimum number of eigenvalues of multiplicity $1$, and the equality of the diameter of a linear tree and its minimum number of distinct eigenvalues, etc., Comment: 18 pages

We study several enumeration problems connected to linear trees, a broad class which includes stars, paths, generalized stars, and caterpillars. We provide generating functions for counting the number of linear trees on $n$ vertices, characterize the asymptotic growth rate of the number of nonisomorphic linear trees, and show that the distribution of $k$-linear trees on $n$ vertices follows a central limit theorem., Comment: 8 pages; v2 contains new central limit theorem, as suggested by the referee