On the perturbation of weighted group inverse of rectangular matrices

Cen (Math. Numer. Sin. 29:39–48, 2007) defined a weighted group inverse of rectangular matrices. For given matrices A∈C ^m×n and W∈C ^n×m , if X∈C ^m×n satisfies $$( W_{1} )\ AWXWA=A, \qquad ( W_{2} ) \ XWAWX=X,\qquad ( W_{3} )\ AWX=XWA $$ then X is called the W-weighted group inverse, which is denoted by $A_{W}^{\#}$ . In this paper, for given rectangular matrices A and E and B=A+E, we investigate the perturbation of the weighted group inverse $A_{W}^{\#}$ and present the upper bounds for $\|B_{W}^{\#} \|$ .     

Classes of matrices associated with the optimal assignment problem

Let E=[e_ij] be a matrix with integral elements, and let x be an indeterminate defined over the rational field Q. We investigate matrices of the form X=[x^e_ij] (i = 1,…, m; j = 1,…, n; m ⩽ n). We may multiply the lines (rows or columns) of the matrix X by suitable integral powers of x in various ways and thereby transform X into a matrix Y=[x^f_ij] such that the f_ij are nonnegative integers and each line of Y contains at least one element x⁰ = 1. We call Y a normalized form of X, and we denote by S(X) the class of all normalized forms associated with a given matrix X. The classes S(X) have a fascinating combinatorial structure, and the present paper is a natural outgrowth and extension of an earlier study. We introduce new concepts such as an elementary transformation called an interchange. We prove, for example, that two matrices in the same class are transformable into one another by interchanges. Our analysis of the class S(X) also yields new insights into the structure of the optimal assignments of the matrix E by way of the diagonal products of the matrix X.     

Minimum norm problems over transportation polytopes

We consider the problem of updating input-output matrices, i.e., for given (m,n) matrices A ? 0, W ? 0 and vectors u ? $\text{R}$^m, v?$\text{R}$ⁿ, find an (m,n) matrix X ? 0 with prescribed row sums Σⁿ_j=1X_ij = u_i (i = 1,…,m) and prescribed column sums Σ^m_i=1X_ij = v_j (j = 1,…,n) which fits the relations X_ij = A_ij + λ_iW_ij + W_ij + W_ijμ_j for all i,j and some λ?$\text{R}$^m, μ?$\text{R}$ⁿ. Here we consider the question of existence of a solution to this problem, i.e., we shall characterize those matrices A, W and vectors u,v which lead to a solvable problem. Furthermore we outline some computational results using an algorithm of [2].     

Orthogonal designs II

Orthogonal designs are a natural generalization of the Baumert-Hall arrays which have been used to construct Hadamard matrices. We continue our investigation of these designs and show that orthogonal designs of type (1,k) and ordern exist for everyk < n whenn = 2 ^t+2?3 andn = 2 ^t+2?5 (wheret is a positive integer). We also find orthogonal designs that exist in every order 2n and others that exist in every order 4n. Coupled with some results of earlier work, this means that theweighing matrix conjecture ‘For every ordern ≡ 0 (mod 4) there is, for eachk ?n, a square {0, 1, ? 1} matrixW = W(n, k) satisfyingWW ^t =kIn’ is resolved in the affirmative for all ordersn = 2^t+1?3,n = 2^t+1?5 (t a positive integer). The fact that the matrices we find are skew-symmetric for allk < n whenn ≡ 0 (mod 8) and because of other considerations we pose three other conjectures about weighing matrices having additional structure and resolve these conjectures affirmatively in a few cases. In an appendix we give a table of the known results for orders ? 64.     

The generic division rings

LetA=k (X ₁, X₂..., X_m) be the division ring generated by genericn×n matrices over a fieldk; thenA is not a crossed product in the following cases: (i) there exists a primeq such thatq ³ℛn;(ii)[k:Q]=m, whereQ is the field of rationals, then if eitherq ³ℛn for someq for whichq-1ℛm, orq ²/nn for some other prime; (iii)k=Z _p ^r a finite field ofp ^r elements and eitherq ³ℛn for sameqℛp ^r-1 orq ²ℛn for some other primes. Other cases are also considered.     

Necessary and sufficient conditions for multivariate majorization

Let X and Y be m × n matrices whose elements are in K, a real or complex field. We obtain necessary and sufficient conditions for the existence of a matrix A belonging to the convex hull of a certain subgroup of the general linear group GL_n(K) such that X = YA, which unite and generalize several known results concerning majorization.     

Random systems of equations in free abelian groups

We study the solvability of random systems of equations on the free abelian group ? ^m of rank m. Denote by SAT(? ^m , k, n) and \(SAT_{\mathbb{Q}^m } (\mathbb{Z}^m ,k,n)\) the sets of all systems of n equations of k unknowns in ? ^m satisfiable in ? ^m and ? ^m respectively. We prove that the asymptotic density \(\rho \left( {SAT_{\mathbb{Q}^m } (\mathbb{Z}^m ,k,n)} \right)\) of the set \(SAT_{\mathbb{Q}^m } (\mathbb{Z}^m ,k,n)\) equals 1 for n ≤ k and 0 for n > k. As regards, SAT(? ^m , k, n) for n < k, some new estimates are obtained for the lower and upper asymptotic densities and it is proved that they lie between (Π _j=k?n+1 ^k ζ(j))^?1 and \(\left( {\tfrac{{\zeta (k + m)}} {{\zeta (k)}}} \right)^n\) , where ξ(s) is the Riemann zeta function. For n ≤ k, a connection is established between the asymptotic density of SAT(? ^m , k, n) and the sums of inverse greater divisors over matrices of full rank. Starting from this result, we make a conjecture about the asymptotic density of SAT(? ^m , n, n). We prove that ρ(SAT(? ^m , k, n)) = 0 for n > k.     

Heuristics for exact nonnegative matrix factorization

The exact nonnegative matrix factorization (exact NMF) problem is the following: given an m-by-n nonnegative matrix X and a factorization rank r, find, if possible, an m-by-r nonnegative matrix W and an r-by-n nonnegative matrix H such that \(X = WH\). In this paper, we propose two heuristics for exact NMF, one inspired from simulated annealing and the other from the greedy randomized adaptive search procedure. We show empirically that these two heuristics are able to compute exact nonnegative factorizations for several classes of nonnegative matrices (namely, linear Euclidean distance matrices, slack matrices, unique-disjointness matrices, and randomly generated matrices) and as such demonstrate their superiority over standard multi-start strategies. We also consider a hybridization between these two heuristics that allows us to combine the advantages of both methods. Finally, we discuss the use of these heuristics to gain insight on the behavior of the nonnegative rank, i.e., the minimum factorization rank such that an exact NMF exists. In particular, we disprove a conjecture on the nonnegative rank of a Kronecker product, propose a new upper bound on the extension complexity of generic n-gons and conjecture the exact value of (i) the extension complexity of regular n-gons and (ii) the nonnegative rank of a submatrix of the slack matrix of the correlation polytope.     

Asymptotic distribution of singular values of powers of random matrices

Let x be a complex random variable such that \( {\mathbf{E}}x = 0,\,{\mathbf{E}}{\left| x \right|^2} = 1 \), and \( {\mathbf{E}}{\left| x \right|^4} < \infty \). Let \( {x_{ij}},i,j \in \left\{ {1,2, \ldots } \right\} \), be independent copies of x. Let \( {\mathbf{X}} = \left( {{N^{ - 1/2}}{x_{ij}}} \right) \), 1≤i,j≤N, be a random matrix. Writing X ^? for the adjoint matrix of X, consider the product X ^m X ^?m with some m ∈{1,2,...}. The matrix X ^m X ^?m is Hermitian positive semidefinite. Let λ₁,λ₂,...,λ _N be eigenvalues of X ^m X ^?m (or squared singular values of the matrix X ^m ). In this paper, we find the asymptotic distribution function \( {G^{(m)}}(x) = {\lim_{N \to \infty }}{\mathbf{E}}F_N^{(m)}(x) \) of the empirical distribution function \( F_N^{(m)}(x) = {N^{ - 1}}\sum\nolimits_{k = 1}^N {\mathbb{I}\left\{ {{\lambda_k} \leqslant x} \right\}} \), where \( \mathbb{I}\left\{ A \right\} \) stands for the indicator function of an event A. With m=1, our result turns to a well-known result of Marchenko and Pastur [V. Marchenko and L. Pastur, The eigenvalue distribution in some ensembles of random matrices, Math. USSR Sb., 1:457–483, 1967].     

Simultaneous singular value decomposition

We consider the following problem: Given a set of m×n real (or complex) matrices A₁,…,A_N, find an m×m orthogonal (or unitary) matrix P and an n×n orthogonal (or unitary) matrix Q such that P^*A₁Q,…,P^*A_NQ are in a common block-diagonal form with possibly rectangular diagonal blocks. We call this the simultaneous singular value decomposition (simultaneous SVD). The name is motivated by the fact that the special case with N=1, where a single matrix is given, reduces to the ordinary SVD. With the aid of the theory of *-algebra and bimodule it is shown that a finest simultaneous SVD is uniquely determined. An algorithm is proposed for finding the finest simultaneous SVD on the basis of recent algorithms of Murota-Kanno-Kojima-Kojima and Maehara-Murota for simultaneous block-diagonalization of square matrices under orthogonal (or unitary) similarity.     

Bijective linear maps on semimodules spanned by Boolean matrices of fixed rank

Let M_m,n(B) be the semimodule of all m×n Boolean matrices where B is the Boolean algebra with two elements. Let k be a positive integer such that 2?k?min(m,n). Let B(m,n,k) denote the subsemimodule of M_m,n(B) spanned by the set of all rank k matrices. We show that if T is a bijective linear mapping on B(m,n,k), then there exist permutation matrices P and Q such that T(A)=PAQ for all A∈B(m,n,k) or m=n and T(A)=PA^tQ for all A∈B(m,n,k). This result follows from a more general theorem we prove concerning the structure of linear mappings on B(m,n,k) that preserve both the weight of each matrix and rank one matrices of weight k². Here the weight of a Boolean matrix is the number of its nonzero entries.     

Linear preservers of matrices of rank-2

Let T be a linear operator on the space of all m×n matrices over any field. we prove that if T maps rank-2 matrices to rank-2 matrices then there exist nonsingular matrices U and V such that either T(X)=UXV for all matrices X, or m=n and T(X)=UX^tV for all matrices X where X^t denotes the transpose of X.     

The structure of the distribution of a couple of observable random variables in credibility theory

We consider Bühlmann's classical model in credibility theory and we assume that the set of possible values of the observable random variables X₁, X₂,… is finite, say with n elements. Then the distribution of a couple (X_r, X_s) (r ≠ s) amounts to a square real matrix of order n, that we call a credibility matrix. In order to estimate credibility matrices or to adjust roughly estimated credibility matrices, we study the set of all credibility matrices and some particular subsets of it.     

Sets of nonnegative matrices with positive inhomogeneous products

Let X be a set of k×k matrices in which each element is nonnegative. For a positive integer n, let P(n) be an arbitrary product of n matrices from X, with any ordering and with repetitions permitted. Define X to be a primitive set if there is a positive integer n such that every P(n) is positive [i.e., every element of every P(n) is positive]. For any primitive set X of matrices, define the index g(X) to be the least positive n such that every P(n) is positive. We show that if X is a primitive set, then g(X)?2^k?2. Moreover, there exists a primitive set Y such that g(Y) = 2^k?2.     

The solution of the equation AX + BX ⋆ = 0

We give a complete solution of the matrix equation AX?+?BX ^??=?0, where A, B?∈?? ^m×n are two given matrices, X?∈?? ^n×n is an unknown matrix, and ? denotes the transpose or the conjugate transpose. We provide a closed formula for the dimension of the solution space of the equation in terms of the Kronecker canonical form of the matrix pencil A?+?λB, and we also provide an expression for the solution X in terms of this canonical form, together with two invertible matrices leading A?+?λB to the canonical form by strict equivalence.     

The primitive Boolean matrices with the second largest scrambling index by Boolean rank

The scrambling index of an n × n primitive Boolean matrix A is the smallest positive integer k such that A ^k (A ^T) ^k = J, where A ^T denotes the transpose of A and J denotes the n×n all ones matrix. For an m×n Boolean matrix M, its Boolean rank b(M) is the smallest positive integer b such that M = AB for some m × b Boolean matrix A and b×n Boolean matrix B. In 2009, M. Akelbek, S. Fital, and J. Shen gave an upper bound on the scrambling index of an n×n primitive matrix M in terms of its Boolean rank b(M), and they also characterized all primitive matrices that achieve the upper bound. In this paper, we characterize primitive Boolean matrices that achieve the second largest scrambling index in terms of their Boolean rank.     

On Linear Preservers of Two-Sided Gut-Majorization On <Emphasis Type="Bold">M</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis>,<Emphasis Type="Italic">m</Emphasis></Subscript>

For X, Y ∈ M_n,m it is said that X is gut-majorized by Y, and we write X ?_gutY, if there exists an n-by-n upper triangular g-row stochastic matrix R such that X = RY. Define the relation ~_gut as follows. X ~_gutY if X is gut-majorized by Y and Y is gut-majorized by X. The (strong) linear preservers of ?_gut on ?ⁿ and strong linear preservers of this relation on M_n,m have been characterized before. This paper characterizes all (strong) linear preservers and strong linear preservers of ~_gut on ?ⁿ and M_n,m.     

Riesz potentials and integral geometry in the space of rectangular matrices

Riesz potentials on the space of rectangular n×m matrices arise in diverse “higher rank” problems of harmonic analysis, representation theory, and integral geometry. In the rank-one case m=1 they coincide with the classical operators of Marcel Riesz. We develop new tools and obtain a number of new results for Riesz potentials of functions of matrix argument. The main topics are the Fourier transform technique, representation of Riesz potentials by convolutions with a positive measure supported by submanifolds of matrices of rank<m, the behavior on smooth and L^p functions. The results are applied to investigation of Radon transforms on the space of real rectangular matrices.     

A note on a conjecture on permanents

Let Kn denote the set of all n × n nonnegative matrices whose entries have sum n, and let ϕ be a real function on K_n defined by ϕ (X) = Πⁿ_i=1Σⁿ_j=1x_ij + Πⁿ_j=1Σⁿ_i=1x_ij − per X for X = [x_ij] ϵ K_n. A matrix A ϵ K_n is called a ϕ -maximizing matrix on K_n if ϕ (A) ⩾ ϕ (X) for all X ϵ K_n. It is conjectured that J_n = [1/n]_{n × n} is the unique ϕ-maximizing matrix on K_n. In this note, the following are proved: (i) If A is a positive ϕ-maximizing matrix, then A = J_n. (ii) If A is a row stochastic ϕ-maximizing matrix, then A = J_n. (iii) Every row sum and every column sum of a ϕ-maximizing matrix lies between 1 − √2·n!/nⁿ and 1 + (n − 1)√2·n!/nⁿ. (iv) For any p.s.d. symmetric A ϵ K_n, ϕ (A) ⩽ 2 − n!/nⁿ with equality iff A = J_n. (v) ϕ attains a strict local maximum on K_n at J_n.     

Multiplicative infinite loop space theory

Let G be a finitely presented group given by its pre-abelian presentation <X1,…,Xm; Xe11ζ1,…,Xemmζ,ζm+1,…>, where ei≥0 for i = 1,…, m and ζj?G′ for j≥1. Let N be the subgroup of G generated by the normal subgroups [xeii, G] for i = 1,…, m. Then Dn+2(G)≡γn+2(G) (modNG′) for all n≥0, where G” is the second commutator subgroup of G,γn+2(G) is the (n+2)th term of the lower central series of G and Dn+2(G) = G∩(1+△n+2(G)) is the (n+2)th dimension subgroup of G.