A forbidden structure of ray nonsingular matrices

A complex square matrix is called a ray nonsingular matrix (RNS matrix) if its ray pattern implies that it is nonsingular. In this paper, a necessary condition for RNS matrices is provided by showing that if A=I−A(D)$A=I-A(D)$ is ray nonsingular, then the arc weighted digraph D contains no forbidden cycle chains.     

On minors of the compound matrix of a Laplacian

Let L   be an n×n$n\times n$ matrix with zero row and column sums, n?3$n?3$. We obtain a formula for any minor of the (n−2)$(n-2)$-th compound of L. An application to counting spanning trees extending a given forest is given.     

The Drazin inverse of a singular,unreduced tridiagonal matrix

For a tridiagonal, singular matrix A   we present a method for the computation of the polynomial p(λ)$p(\lambda )$ such that A^D=p(A)$A^D=p(A)$ holds, where A^D$A^D$ is the Drazin inverse of A. The approach is based on the recursion of characteristic polynomials of leading principal submatrices of A.     

A fast algorithm for the recursive calculation of dominant singular subspaces

In many engineering applications it is required to compute the dominant subspace of a matrix A   of dimension m×n$m\times n$, with m?n$m?n$. Often the matrix A is produced incrementally, so all the columns are not available simultaneously. This problem arises, e.g., in image processing, where each column of the matrix A represents an image of a given sequence leading to a singular value decomposition-based compression [S. Chandrasekaran, B.S. Manjunath, Y.F. Wang, J. Winkeler, H. Zhang, An eigenspace update algorithm for image analysis, Graphical Models and Image Process. 59 (5) (1997) 321–332]. Furthermore, the so-called proper orthogonal decomposition approximation uses the left dominant subspace of a matrix A where a column consists of a time instance of the solution of an evolution equation, e.g., the flow field from a fluid dynamics simulation. Since these flow fields tend to be very large, only a small number can be stored efficiently during the simulation, and therefore an incremental approach is useful [P. Van Dooren, Gramian based model reduction of large-scale dynamical systems, in: Numerical Analysis 1999, Chapman & Hall, CRC Press, London, Boca Raton, FL, 2000, pp. 231–247].     

Covering with universally Baire operators

We introduce a covering conjecture and show that it holds below A_DR+“Θ is regular”$A{D}_{\mathbb{R}}+\text{“}\Theta \text{is regular”}$. We then use it to show that in the presence of mild large cardinal axioms, PFA   implies that there is a transitive model containing the reals and ordinals and satisfying A_DR+“Θ is regular”$A{D}_{\mathbb{R}}+\text{“}\Theta \text{is regular”}$. The method used to prove the Main Theorem of this paper is the core model induction. The paper contains the first application of the core model induction that goes significantly beyond the region of AD⁺+_θ0<Θ$A{D}^{+}+{\theta }_0<\Theta$.     

Diagonals and numerical ranges of direct sums of matrices

For any n-by-n matrix A  , we consider the maximum number k=k(A)$k=k(A)$ for which there is a k-by-k compression of A   with all its diagonal entries in the boundary ∂W(A)$\partial W(A)$ of the numerical range W(A)$W(A)$ of A. If A   is a normal or a quadratic matrix, then the exact value of k(A)$k(A)$ can be computed. For a matrix A   of the form B⊕C$B\oplus C$, we show that k(A)=2$k(A)=2$ if and only if the numerical range of one summand, say, B is contained in the interior of the numerical range of the other summand C   and k(C)=2$k(C)=2$. For an irreducible matrix A  , we can determine exactly when the value of k(A)$k(A)$ equals the size of A  . These are then applied to determine k(A)$k(A)$ for a reducible matrix A   of size 4 in terms of the shape of W(A)$W(A)$.     

Some properties of generalized K-centrosymmetric H-matrices

Every n×n$n\times n$ generalized K-centrosymmetric matrix A   can be reduced into a 2×2$2\times 2$ block diagonal matrix (see [Z. Liu, H. Cao, H. Chen, A note on computing matrix–vector products with generalized centrosymmetric (centrohermitian) matrices, Appl. Math. Comput. 169 (2) (2005) 1332–1345]). This block diagonal matrix is called the reduced form of the matrix A. In this paper we further investigate some properties of the reduced form of these matrices and discuss the square roots of these matrices. Finally exploiting these properties, the development of structure-preserving algorithms for certain computations for generalized K-centrosymmetric H-matrices is discussed.     

Algebraic/combinatorial proofs of Cayley-type identities for derivatives of determinants and pfaffians

The classic Cayley identity states that

det(∂)(detX)^s=s(s+1)?(s+n−1)(detX)^s−1$\det (\partial ){(\det X)}^s=s(s+1)?(s+n-1){(\det X)}^{s-1}$

where X=(_xij)$X=(x_{ij})$ is an n×n$n\times n$ matrix of indeterminates and ∂=(∂/∂_xij)$\partial =(\partial /\partial x_{ij})$ is the corresponding matrix of partial derivatives. In this paper we present straightforward algebraic/combinatorial proofs of a variety of Cayley-type identities, both old and new. The most powerful of these proofs employ Grassmann algebra (= exterior algebra) and Grassmann–Berezin integration. Among the new identities proven here are a pair of “diagonal-parametrized” Cayley identities, a pair of “Laplacian-parametrized” Cayley identities, and the “product-parametrized” and “border-parametrized” rectangular Cayley identities.     

The complexity of tropical matrix factorization

The tropical arithmetic operations on R are defined by a⊕b=min{a,b}$a\oplus b=\min \{a,b\}$ and a⊗b=a+b$a\otimes b=a+b$. Let A be a tropical matrix and k   a positive integer, the problem of Tropical Matrix Factorization (TMF) asks whether there exist tropical matrices B∈R^m×k$B\in {\mathbf{R}}^{m\times k}$ and C∈R^k×n$C\in {\mathbf{R}}^{k\times n}$ satisfying B⊗C=A$B\otimes C=A$. We show that the TMF problem is NP-hard for every k≥7$k\ge 7$ fixed in advance, thus resolving a problem proposed by Barvinok in 1993.     

Log-convexity and strong q-log-convexity for some triangular arrays

We give a criterion for the log-convexity (resp. the strong q  -log-convexity) of the first column of certain infinite triangular array _(An,k)0?k?n${(A_{n,k})}_{0?k?n}$ of nonnegative numbers (resp. of polynomials in q with nonnegative coefficients), for which the recurrence relation is of the form

_An,k=_{fkAn−1,k−1}+_gkAn−1,k+_hkAn−1,k+1.$A_{n,k}=f_k{A}_{n-1,k-1}+g_k{A}_{n-1,k}+h_k{A}_{n-1,k+1}.$

This allows a unified treatment of the log-convexity of the Catalan-like numbers, as well as that of the q-log-convexity of some classical polynomials. In particular, we obtain simple proofs of the q-log-convexity of Narayana polynomials.     

S-Noetherian properties on amalgamated algebras along an ideal

Let A and B   be commutative rings with identity, f:A→B$f:A\to B$ a ring homomorphism and J an ideal of B  . Then the subring A?^fJ:={(a,f(a)+j)|a∈A and j∈J}$A{?}^{f}J:=\{(a,f(a)+j)|a\in A\text{and}j\in J\}$ of A×B$A\times B$ is called the amalgamation of A with B along with J with respect to f. In this paper, we investigate a general concept of the Noetherian property, called the S  -Noetherian property which was introduced by Anderson and Dumitrescu, on the ring A?^fJ$A{?}^{f}J$ for a multiplicative subset S   of A?^fJ$A{?}^{f}J$. As particular cases of the amalgamation, we also devote to study the transfers of the S  -Noetherian property to the constructions D+(_X1,…,_Xn)E[_X1,…,_Xn]$D+(X_1,\dots ,X_n)E[X_1,\dots ,X_n]$ and D+(_X1,…,_Xn)E?_X1,…,_Xn?$D+(X_1,\dots ,X_n)E?X_1,\dots ,X_n?$ and Nagata?s idealization.     

A general product of tensors with applications

We study a general product of two n  -dimensional tensors A$\mathbb{A}$ and B$\mathbb{B}$ with orders m?2$m?2$ and k?1$k?1$. This product satisfies the associative law, and is a generalization of the usual matrix product. Using this product, many concepts and known results of tensors can be simply expressed and/or proved, and a number of applications of it will be given. Using the associative law of this tensor product and some properties on the resultant of a system of homogeneous equations on n variables, we define the similarity and congruence of tensors (which are also the generalizations of the corresponding relations for matrices), and prove that similar tensors have the same characteristic polynomials, thus the same spectra. We study two special kinds of similarity: permutational similarity and diagonal similarity, and their applications in the study of the spectra of hypergraphs and nonnegative irreducible tensors. We also define the direct product of tensors (in matrix case it is also called the Kronecker product), and give its applications in the study of the spectra of two kinds of the products of hypergraphs. We also give applications of this general product in the study of nonnegative tensors, including a characterization of primitive tensors, the upper bounds of primitive degrees and the cyclic indices of some nonnegative irreducible tensors.     

Generalized matrix inversion is not harder than matrix multiplication

Starting from the Strassen method for rapid matrix multiplication and inversion as well as from the recursive Cholesky factorization algorithm, we introduced a completely block recursive algorithm for generalized Cholesky factorization of a given symmetric, positive semi-definite matrix A∈R^n×n$A\in {\mathbb{R}}^{n\times n}$. We used the Strassen method for matrix inversion together with the recursive generalized Cholesky factorization method, and established an algorithm for computing generalized {2,3}$\{2,3\}$ and {2,4}$\{2,4\}$ inverses. Introduced algorithms are not harder than the matrix–matrix multiplication.     

Block tridiagonal reduction of perturbed normal and rank structured matrices

It is well known that if a matrix A∈C^n×n$A\in {\mathbb{C}}^{n\times n}$ solves the matrix equation f(A,A^H)=0$f(A,A^H)=0$, where f(x,y)$f(x,y)$ is a linear bivariate polynomial, then A is normal; A   and A^H$A^H$ can be simultaneously reduced in a finite number of operations to tridiagonal form by a unitary congruence and, moreover, the spectrum of A is located on a straight line in the complex plane. In this paper we present some generalizations of these properties for almost normal matrices which satisfy certain quadratic matrix equations arising in the study of structured eigenvalue problems for perturbed Hermitian and unitary matrices.     

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.     

Bijections and symmetries for the factorizations of the long cycle

We study the factorizations of the permutation (1,2,…,n)$(1,2,\dots ,n)$ into k factors of given cycle types. Using representation theory, Jackson obtained for each k   an elegant formula for counting these factorizations according to the number of cycles of each factor. In the cases k=2,3$k=2,3$ Schaeffer and Vassilieva gave a combinatorial proof of Jackson?s formula, and Morales and Vassilieva obtained more refined formulas exhibiting a surprising symmetry property. These counting results are indicative of a rich combinatorial theory which has remained elusive to this point, and it is the goal of this article to establish a series of bijections which unveil some of the combinatorial properties of the factorizations of (1,2,…,n)$(1,2,\dots ,n)$ into k factors for all k  . We thereby obtain refinements of Jackson?s formulas which extend the cases k=2,3$k=2,3$ treated by Morales and Vassilieva. Our bijections are described in terms of “constellations”, which are graphs embedded in surfaces encoding the transitive factorizations of permutations.