Solving balanced Procrustes problem with some constraints by eigenvalue decomposition

The balanced Procrustes problem with some special constraints such as symmetric orthogonality and symmetric idempotence are considered. By one time eigenvalue decomposition of the matrix product generated by the matrices A and B, the constrained solutions are constructed simply. Similar strategy is applied to the problem with the corresponding P-commuting constraints with a given symmetric matrix P. Numerical examples are presented to show the efficiency of the proposed methods.     

Overdetermined linear systems satisfying nonnegativity constraints

Let A be a nonnegative m × n matrix, and let b be a nonnegative vector of dimension m. Also, let S be a subspace of $\text{R}$ⁿ such that if P_S is the orthogonal projector onto S, then P_S ? 0. A necessary condition is given for the matrix A to satisfy the following property: For all b ? 0, if min[boxV]b ? Ax[boxV] is attained at x = x₀, then x₀ ? 0 and x₀ ? S. It is also shown that if a nonnegative matrix A has a nonnegative generalized inverse, then any submatrix of A also possesses a nonnegative generalized inverse.     

Nonnegative matrices having nonnegative Drazin pseudoinverses

Necessary and sufficient conditions for nonnegative matrices having nonnegative Drazin pseudoinverses are obtained. A decomposition theorem which characterizes the class of all nonnegative matrices with nonnegative Drazin pseudoinverses is proved, thus answering a question raised by several people. It is also shown that if a row (or column) stochastic matrix has a nonnegative Drazin pseudoinverse A(^d), then A(^d) is some power of A. These results extend known results for nonnegative group-monotone matrices.     

Maximal number of distinct H-eigenpairs for a two-dimensional real tensor

Based on the generalized characteristic polynomial introduced by J. Canny in Generalized characteristic polynomials [J. Symbolic Comput., 1990, 9(3): 241–250], it is immediate that for any m-order n-dimensional real tensor, the number of distinct H-eigenvalues is less than or equal to n(m?1) ^n?1. However, there is no known bounds on the maximal number of distinct Heigenvectors in general. We prove that for any m ? 2, an m-order 2-dimensional tensor A exists such that A has 2(m ? 1) distinct H-eigenpairs. We give examples of 4-order 2-dimensional tensors with six distinct H-eigenvalues as well as six distinct H-eigenvectors. We demonstrate the structure of eigenpairs for a higher order tensor is far more complicated than that of a matrix. Furthermore, we introduce a new class of weakly symmetric tensors, called p-symmetric tensors, and show under certain conditions, p-symmetry will effectively reduce the maximal number of distinct H-eigenvectors for a given two-dimensional tensor. Lastly, we provide a complete classification of the H-eigenvectors of a given 4-order 2-dimensional nonnegative p-symmetric tensor. Additionally, we give sufficient conditions which prevent a given 4-order 2-dimensional nonnegative irreducible weakly symmetric tensor from possessing six pairwise distinct H-eigenvectors.     

Factorization of cp-rank-3 completely positive matrices

A symmetric positive semi-definite matrix A is called completely positive if there exists a matrix B with nonnegative entries such that A = BB^?. If B is such a matrix with a minimal number p of columns, then p is called the cp-rank of A. In this paper we develop a finite and exact algorithm to factorize any matrix A of cp-rank 3. Failure of this algorithm implies that A does not have cp-rank 3. Our motivation stems from the question if there exist three nonnegative polynomials of degree at most four that vanish at the boundary of an interval and are orthonormal with respect to a certain inner product.     

Lower bound inequalities for norms of symmetrized tensor powers

Let V be a complex inner product space of positive dimension m with inner product 〈·,·〉, and let T_n(V) denote the set of all n-linear complex-valued functions defined on V×V×?×V (n-copies). By S_n(V) we mean the set of all symmetric members of T_n(V). We extend the inner product, 〈·,·〉, on V to T_n(V) in the usual way, and we define multiple tensor products A₁⊗A₂⊗?⊗A_n and symmetric products A₁·A₂?A_n, where q₁,q₂,…,q_n are positive integers and A_i∈T_qi(V) for each i, as expected. If A∈S_n(V), then A^k denotes the symmetric product A·A?A where there are k copies of A. We are concerned with producing the best lower bounds for ‖A^k‖², particularly when n=2. In this case we are able to show that ‖A^k‖² is a symmetric polynomial in the eigenvalues of a positive semi-definite Hermitian matrix, M_A, that is closely related to A. From this we are able to obtain many lower bounds for ‖A^k‖². In particular, we are able to show that if ω denotes 1/r where r is the rank of M_A, and , then

     

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.     

On matrix measures and convex Liapunov functions

In this paper, we extend the concept of the measure of a matrix to encompass a measure induced by an arbitrary convex positive definite function. It is shown that this “modified” matrix measure has most of the properties of the usual matrix measure, and that many of the known applications of the usual matrix measure can therefore be carried over to the modified matrix measure. These applications include deriving conditions for a mapping to be a diffeomorphism on Rⁿ, and estimating the solution errors that result when a nonlinear network is approximated by a piecewise linear network. We also develop a connection between matrix measures and Liapunov functions. Specifically, we show that if V is a convex positive definite function and A is a Hurwitz matrix, then μ_V(A) < 0, if and only if V is a Liapunov function for the system $\text{x}\text{?}\text{= Ax}$. This linking up between matrix measures and Liapunov functions leads to some results on the existence of a “common” matrix measure μ_V(·) such that μ_V(A_i) < 0 for each of a given set of matrices A₁,…, A_m. Finally, we also give some results for matrices with nonnegative off-diagonal terms.     

On a decomposition of conditionally positive-semidefinite matrices

A symmetric matrix C is said to be copositive if its associated quadratic form is nonnegative on the positive orthant. Recently it has been shown that a quadratic form x'Qx is positive for all x that satisfy more general linear constraints of the form Ax?0, x≠0 iff Q can be decomposed as a sum Q=A'CA+S, with Cstrictly copositive and S positive definite. However, if x'Qx is merely nonnegative subject to the constraints Ax?0, it does not follow that Q admits such a decomposition with C copositive and S positive semidefinite. In this paper we give a characterization of those matrices A for which such a decomposition is always possible.     

On the nonsingular symmetric factors of a real matrix

For a given real square matrix A this paper describes the following matrices: (¹) all nonsingular real symmetric (r.s.) matrices S such that A = S^?1T for some symmetric matrix T.All the signatures (defined as the absolute value of the difference of the number of positive eigenvalues and the number of negative eigenvalues) possible for feasible S in (¹) can be derived from the real Jordan normal form of A. In particular, for any A there is always a nonsingular r.s. matrix S with signature S ? 1 such that A = S^?1T.     

Perturbation analysis for the trace quotient problem

Given a symmetric matrix B?∈?? ^m×m and a symmetric and positive-definite matrix W?∈?? ^m×m , maximizing the ratio trace(V ^? BV)/trace(V ^? WV) with respect to V?∈?? ^m×? (??≤?m) subject to the orthogonal constraint V ^? V?=?I _? is called the trace quotient problem or the trace ratio problem (TRP). TRP arises originally from the linear discriminant analysis (LDA), which is a popular approach for feature extraction and dimension reduction. It has been known that TRP is equivalent to a nonlinear extreme eigenvalue problem and very efficient method has been proposed to find a global optimal solution successfully. The matrices B and W arising in LDA are constructed from samples, and thereby are contaminated by noises and errors. In this article, we perform a perturbation analysis for TRP assuming the original B and W are perturbed. The upper perturbation bounds of both the global optimal value and the set of global optimal solutions are derived, and numerical investigation is carried out to illustrate these perturbation estimates.     

Copositive matrices and definiteness of quadratic forms subject to homogeneous linear inequality constraints

A symmetric matrix C is called copositive if the quadratic form x′Cx is nonnegative for all nonnegative values of the variables (x₁,x₂,…,x_n)=x′. A known sufficient condition for a quadratic form x′Qx to be positive unless x=0, subject to the linear inequality constraints Ax?0, is that there should exist a copositive matrix C such that Q?A′CA is positive definite. The main result of this paper establishes the necessity of this condition. For x'Qx to be merely nonnegative subject to Ax ? 0, the situation is less straightforward. The necessity of the existence of a copositive matrix C such that Q?A′CA is positive semidefinite is proved only under various additional hypotheses regarding the size or rank of A, and counterexamples are given to show that, in general, no such matrix may exist, even when Slater's constraint qualification holds. Our approach to these existence questions also furnishes certain tests for positivity or mere nonnegativity of x′Qx subject to Ax?0, in which specific symmetric matrices, constructed by rational operations from A and Q and depending upon a single real parameter v, must be tested for positive definiteness or strict copositivity for large values of v. This technique is illustrated by several examples.     

A computational method for the indefinite quadratic programming problem

We present an algorithm for the quadratic programming problem of determining a local minimum of ?(x)=$\text{1}\text{2}$x^TQx+c^Tx such that A^Tx?b where Q ymmetric matrix which may not be positive definite. Our method combines the active constraint strategy of Murray with the Bunch-Kaufman algorithm for the stable decomposition of a symmetric matrix. Under the active constraint strategy one solves a sequence of equality constrained problems, the equality constraints being chosen from the inequality constraints defining the original problem. The sequence is chosen so that ?(x) continues to decrease and x remains feasible. Each equality constrained subproblem requires the solution of a linear system with the projected Hessian matrix, which is symmetric but not necessarily positive definite. The Bunch-Kaufman algorithm computes a decomposition which facilitates the stable determination of the solution to the linear system. The heart of this paper is a set of algorithms for updating the decomposition as the method progresses through the sequence of equality constrained problems. The algorithm has been implemented in a FORTRAN program, and a numerical example is given.     

On monotonicity of the Lanczos approximation to the matrix exponential

We prove strictly monotonic error decrease in the Euclidian norm of the Krylov subspace approximation of exp(A)φ, where φ and A are respectively a vector and a symmetric matrix. In addition, we show that the norm of the approximate solution grows strictly monotonically with the subspace dimension.     

A rank characterization of the number of final classes of a nonnegative matrix

Let A be a nonnegative square matrix, and let D be a diagonal matrix whose iith element is $\text{(Ax)}{}_{\mathrm{i}}\text{x}{}_{\mathrm{i}}$, where x is a (fixed) positive vector. It is shown that the number of final classes of A equals n?rank(A?D). We also show that null(A?D) = null(A?D)², and that this subspace is spanned by a set of nonnegative elements. Our proof uses a characterization of nonnegative matrices having a positive eigenvector corresponding to their spectral radius.     

Improving an inequality for sums of elements of matrix powers

The inequality 3su A³ ⩾ su A su A², which is known to hold for any symmetric nonnegative 3 X 3 matrix A, is sharpened in three different ways. Here su denotes the sum of elements.     

Transposing a matrix by similarity operations

A matrix T is said to co-transpose a square matrix A if T^?1AT=A′ and T^?1A′T=A. For every n?3 there exists a real n×n matrix which cannot be co-transposed by any matrix. However, it is shown that the following classes of real matrices can be co-transposed by a symmetric matrix of order two: 2×2 matrices, normal matrices, and matrices whose square is symmetric.     

Singular value decompositions of complex symmetric matrices

If the complex square matrix A is symmetric, i.e. A=A^T, then it has a symmetric singular value decomposition A=Q∑Q^T. An algorithm is presented for the computation of this decomposition.     

The scrambling index of symmetric primitive matrices

A nonnegative square matrix A is primitive if some power A^k>0 (that is, A^k is entrywise positive). The least such k is called the exponent of A. In [2], Akelbek and Kirkland defined the scrambling index of a primitive matrix A, which is the smallest positive integer k such that any two rows of A^k have at least one positive element in a coincident position. In this paper, we give a relation between the scrambling index and the exponent for symmetric primitive matrices, and determine the scrambling index set for the class of symmetric primitive matrices. We also characterize completely the symmetric primitive matrices in this class such that the scrambling index is equal to the maximum value.     

On a characterization of tridiagonal matrices by M. Fiedler

In this note two new proofs are given of the following characterization theorem of M. Fiedler: Let C_n, n?2, be the class of all symmetric, real matrices A of order n with the property that rank (A + D) ? n - 1 for any diagonal real matrix D. Then for any A ε C_n there exists a permutation matrix P such that PAP^T is tridiagonal and irreducible.