Positive diagonal scaling of a nonnegative tensor to one with prescribed slice sums

In this paper we give necessary and sufficient conditions on a nonnegative tensor to be diagonally equivalent to a tensor with prescribed slice sums. These conditions are variations of Bapat-Raghavan and Franklin-Lorenz conditions.     

Low rank perturbation of regular matrix polynomials

Let A(λ) be a complex regular matrix polynomial of degree ? with g elementary divisors corresponding to the finite eigenvalue λ₀. We show that for most complex matrix polynomials B(λ) with degree at most ? satisfying rank the perturbed polynomial (A+B)(λ) has exactly elementary divisors corresponding to λ₀, and we determine their degrees. If does not exceed the number of λ₀-elementary divisors of A(λ) with degree greater than 1, then the λ₀-elementary divisors of (A+B)(λ) are the elementary divisors of A(λ) corresponding to λ₀ with smallest degree, together with rank(B(λ)-B(λ₀)) linear λ₀-elementary divisors. Otherwise, the degree of all the λ₀-elementary divisors of (A+B)(λ) is one. This behavior happens for any matrix polynomial B(λ) except those in a proper algebraic submanifold in the set of matrix polynomials of degree at most ?. If A(λ) has an infinite eigenvalue, the corresponding result follows from considering the zero eigenvalue of the perturbed dual polynomial.     

Determinantal divisors of products of matrices over Dedekind domains

Given three lists of ideals of a Dedekind domain, the question is raised whether there exist two matrices A and B with entries in the given Dedekind domain, such that the given lists of ideals are the determinantal divisors of A, B, and AB, respectively. To answer this question, necessary and sufficient conditions are developed in this article.     

Algorithmic copositivity detection by simplicial partition

We present new criteria for copositivity of a matrix, i.e., conditions which ensure that the quadratic form induced by the matrix is nonnegative over the nonnegative orthant. These criteria arise from the representation of the quadratic form in barycentric coordinates with respect to the standard simplex and simplicial partitions thereof. We show that, as the partition gets finer and finer, the conditions eventually capture all strictly copositive matrices. We propose an algorithmic implementation which considers several numerical aspects. As an application, we present results on the maximum clique problem. We also briefly discuss extensions of our approach to copositivity with respect to arbitrary polyhedral cones.     

Manifolds of idemopotent matrices

Let M_n be the set of n×n matrices and r a nonnegative integer with r ≤ n. It is known,from Lie groups, that the rank r idempotent matrices in M_n form an arcwise connected 2n (n-r)-dimensional analytic manifold. This paper provides an elementary proof of this result making it accessible to a larger audience.     

Isospectral flow method for nonnegative inverse eigenvalue problem with prescribed structure

The nonnegative inverse eigenvalue problem is that given a family of complex numbers λ={λ₁,…,λ_n}, find a nonnegative matrix of order n with spectrum λ. This problem is difficult and remains unsolved partially. In this paper, we focus on its generalization that the reconstructed nonnegative matrices should have some prescribed entries. It is easy to see that this new problem will come back to the common nonnegative inverse eigenvalue problem if there is no constraint of the locations of entries. A numerical isospectral flow method which is developed by hybridizing the optimization theory and steepest descent method is used to study the reconstruction. Moreover, an error estimate of the numerical iteration for ordinary differential equations on the matrix manifold is presented. After that, a numerical method for the nonnegative symmetric inverse eigenvalue problem with prescribed entries and its error estimate are considered. Finally, the approaches are verified by the numerical test results.     

Triangularizing matrix polynomials

For an algebraically closed field F$\mathbb{F}$, we show that any matrix polynomial P(λ)∈F[λ]^n×m$P(\lambda )\in \mathbb{F}{[\lambda ]}^{n\times m}$, n?m$n?m$, can be reduced to triangular form, preserving the degree and the finite and infinite elementary divisors. We also characterize the real matrix polynomials that are triangularizable over the real numbers and show that those that are not triangularizable are quasi-triangularizable with diagonal blocks of sizes 1×1$1\times 1$ and 2×2$2\times 2$. The proofs we present solve the structured inverse problem of building up triangular matrix polynomials starting from lists of elementary divisors.     

Intervals of totally nonnegative matrices

Totally nonnegative matrices, i.e., matrices having all their minors nonnegative, and matrix intervals with respect to the checkerboard ordering are considered. It is proven that if the two bound matrices of such a matrix interval are nonsingular and totally nonnegative (and in addition all their zero minors are identical) then all matrices from this interval are also nonsingular and totally nonnegative (with identical zero minors).     

Subdirect sums of P(P0)-matrices and totally nonnegative matrices

In this paper, the problem of when the sub-direct sum of two strictly diagonally dominant P-matrices is a strictly diagonally dominant P-matrix is studied. In particular, it is shown that the subdirect sum of overlapping principal submatrices of strictly diagonally dominant P-matrices is a strictly diagonally dominant P-matrix. It is also established that the 2-subdirect sum of two totally nonnegative matrices is a totally nonnegative matrix under some conditions. It is obtained that a partial totally nonnegative matrix, whose graph of the specified entries is a monotonically labeled 2-chordal graph, has a totally nonnegative completion. Finally, a positive answer to the question (IV) in Fallat and Johnson [Shaun M. Fallat, C.R. Johnson, J.R. Torregrosa, A.M. Urbano, P-matrix completions under weak symmetry assumptions, Linear Algebra Appl. 312 (2000) 73-91] is given for P₀-matrices.     

The characterization of operators preserving primitivity for matrix k-tuples

We obtain a complete characterization of surjective additive operators acting on the Cartesian product of several matrix spaces over an antinegative semiring without zero divisors, which map primitive matrix k-tuples to primitive matrix k-tuples.     

Solving inverse eigenvalue problems via Householder and rank-one matrices

A brief and practical algorithm is introduced to solve symmetric inverse eigenvalue problems, which we call HROU algorithm. The algorithm is based on Householder transformations and rank one updating. We give some basic properties and the computational amount and develop sensitivity analysis of HROU algorithm. Furthermore, we develop HROU algorithm into a multi-level and adaptive one, named MLAHROU, to solve symmetric nonnegative inverse eigenvalue problems. New sufficient conditions to ensure symmetric nonnegative matrices and symmetric M-matrices are given. Many numerical examples are given to verify our theory, compare with existing results and show the efficiency of our algorithms.     

Conics in the Grothendieck ring

The subring of the Grothendieck ring of k-varieties generated by smooth conics is described, giving many zero divisors. The proof uses only elementary projective geometry.     

A quantization of conjugacy classes of matrices

We construct a generator system of the annihilator of the generalized Verma module of gl(n,C) induced from any character of any parabolic subalgebra as an analogue of minors and elementary divisors. The generator system has a quantization parameter ε and it generates the defining ideal of the conjugacy class of square matrices at the classical limit ε=0.     

Bijective linear rank preservers for spaces of matrices over antinegative semirings

We classify the bijective linear operators on spaces of matrices over antinegative commutative semirings with no zero divisors which preserve certain rank functions such as the symmetric rank, the factor rank and the tropical rank. We also classify the bijective linear operators on spaces of matrices over the max-plus semiring which preserve the Gondran-Minoux row rank or the Gondran-Minoux column rank.     

On visualization scaling, subeigenvectors and Kleene stars in max algebra

The purpose of this paper is to investigate the interplay arising between max algebra, convexity and scaling problems. The latter, which have been studied in nonnegative matrix theory, are strongly related to max algebra. One problem is that of strict visualization scaling, defined as, for a given nonnegative matrix A, a diagonal matrix X such that all elements of X^-1AX are less than or equal to the maximum cycle geometric mean of A, with strict inequality for the entries which do not lie on critical cycles. In this paper such scalings are described by means of the max algebraic subeigenvectors and Kleene stars of nonnegative matrices as well as by some concepts of convex geometry.     

Inequalities for Gondran-Minoux rank and idempotent semirings

The rank-sum, rank-product, and rank-union inequalities for Gondran-Minoux rank of matrices over idempotent semirings are considered. We prove these inequalities for matrices over quasi-selective semirings without zero divisors, which include matrices over the max-plus semiring. Moreover, it is shown that the inequalities provide the linear algebraic characterization for the class of quasi-selective semirings. Namely, it is proven that the inequalities hold for matrices over an idempotent semiring S without zero divisors if and only if S is quasi-selective. For any idempotent semiring which is not quasi-selective it is shown that the rank-sum, rank-product, and rank-union inequalities do not hold in general. Also, we provide an example of a selective semiring with zero divisors such that the rank-sum, rank-product, and rank-union inequalities do not hold in general.     

Bounds on eigenvalues of the Hadamard product and the Fan product of matrices

We prove an upper bound for the spectral radius of the Hadamard product of nonnegative matrices and a lower bound for the minimum eigenvalue of the Fan product of M-matrices. These improve two existing results.     

The solution methods for the largest eigenvalue (singular value) of nonnegative tensors and convergence analysis

In this paper we study two solution methods for finding the largest eigenvalue (singular value) of general square (rectangular) nonnegative tensors. For a positive tensor, one can find the largest eigenvalue (singular value) based on the properties of the positive tensor and the power-type method. While for a general nonnegative tensor, we use a series of decreasing positive perturbations of the original tensor and repeatedly recall power-type method for finding the largest eigenvalue (singular value) of a positive tensor with an inexact strategy. We prove the convergence of the method for the general nonnegative tensor. Under a certain assumption, the computing complexity of the method is established. Motivated by the interior-point method for the convex optimization, we put forward a one-step inner iteration power-type method, whose convergence is also established under certain assumption. Additionally, by using embedding technique, we show the relationship between the singular values of the rectangular tensor and the eigenvalues of related square tensor, which suggests another way for finding the largest singular value of nonnegative rectangular tensor besides direct power-type method for this problem. Finally, numerical examples of our algorithms are reported, which demonstrate the convergence behaviors of our methods and show that the algorithms presented are promising.     

Explicit solution of the row completion problem for matrix pencils

In this paper we give new, explicit and simplified conditions for the problem of determining the possible strict equivalence class of a pencil with prescribed rows (columns). This improves the result from [1] and solves an important particular case of the challenge problem posed by Loiseau et al. [7]. All results that we present are obtained over arbitrary fields.