Solving the generalized sylvester matrix equation Σ i=1p AiXBi + Σ j=1q CjYDj=E over reflexive and anti-reflexive matrices

A matrix P ∈ ℝ ^n×n is called a generalized reflection if P ^T = P and P ²=I. An n×n matrix A is said to be a reflexive (anti-reflexive) with respect to P if A PAP (A = −PAP). In the present paper, two iterative methods are derived for solving the generalized Sylvester matrix equation Σ _i=1 ^p A _i XB _i + Σ _j=1 ^q C _j YD _j =E (including the Sylvester and Lyapunov matrix equations as special cases) over reflexive and anti-reflexive matrices respectively. It is proven that the iterative methods, respectively, consistently converge to the reflexive and anti-reflexive solutions of the matrix equation for any initial reflexive and anti-reflexive matrices. Finally, a numerical example is given to demonstrate the effectiveness of the derived methods.     

Optimal Finite Characterization of Linear Problems with Inexact Data

Abstract. For many linear problems, in order to check whether a certain property is true for all matrices A from an interval matrix A, it is sufficient to check this property for finitely many “vertex” matrices A ∈ A. J. Rohn has discovered that we do not need to use all 2ⁿ² vertex matrices, it is sufficient to only check these properties for 2²ⁿ⁻¹ ≪ 2ⁿ² vertex matrices of a special type A_yz. In this paper, we show that a further reduction is impossible: without checking all 2²ⁿ⁻¹ matrices A_yz, we cannot guarantee that the desired property holds for all A ϵ A. Thus, these special vertex matrices provide an optimal finite characterization of linear problems with inexact data.     

A Contribution to the Feasibility of the Interval Gaussian Algorithm

We apply the interval Gaussian algorithm to an n × n interval matrix [A] whose comparison matrix 〈[A]〉 is generalized diagonally dominant. For such matrices we prove conditions for the feasibility of this method, among them a necessary and sufficient one. Moreover, we prove an equivalence between a well-known sufficient criterion for the algorithm on H matrices and a necessary and sufficient one for interval matrices whose midpoint is the identity matrix. For the more general class of interval matrices which also contain the identity matrix, but not necessarily as midpoint, we derive a criterion of infeasibility. For general matrices [A] we show how the feasibility of reducible interval matrices is connected with that of irreducible ones. Dedicated to Professor Dr. H. J. Stetter, Wien, on the occasion of his 75th birthday     

An accelerated randomized Kaczmarz method via low-rank approximation

The Kaczmarz method for finding the solution to an overdetermined consistent system of linear equation Ax=b(A∈R^m×n) is an iterative algorithm that has found many applications ranging from computer tomography to digital signal processing. Recently, Strohmer and Vershynin proposed randomized Kaczmarz, and proved its exponential convergence. In this paper, motivated by idea of precondition, we present a modified version of the randomized Kaczmarz method where an orthogonal matrix was multiplied to both sides of the equation Ax=b, and the orthogonal matrix is obtained by low-rank approximation. Our approach fits the problem when m is huge and m?n. Theoretically, we improve the convergence rate of the randomized Kaczmarz method. The numerical results show that our approach is faster than the standard randomized Kaczmarz.     

A more efficient algorithm for the min-plus multiplication

The (min, + ) product C of two n × n matrices A and B is defined as C _ij = min_1≦k≦n A _ik + B _kj . This paper presents an algorithm to compute the (min, +) product of two n × n matrices. The algorithm follows the approach described by Fredman, but is faster than Fredman's own algorithm: its time complexity is either O(n ³/√log₂ n) or even O(n ^2.5√log₂ n), if one adheres to the uniform-cost RAM model faithfully.

This result implies the existence of O(n ³/√log₂ n) algorithms for the problems that (min, +) matrix multiplication is equivalent to, such as the all-pairs shortest paths problem.

As the presented algorithm uses operations on sets, the formal analysis of its time complexity raises a few interesting questions about the applicability of the standard RAM complexity model.     

An alternative solution to the H∞-optimal control problem

In this paper we present an alternative solution to the problem min _{X ε H^n×n∞} |A + BXC|_∞ where A, B, rmand C are rational matrices in H^n×n_∞. The solution circumvents the need to extract the matrix inner factors of B and C, providing a multivariable extension of Sarason's H^∞-interpolation theory [1] to the case of matrix-valued B(s) and C(s). The result has application to the diagonally-scaled optimization problem int |D(A + BXC)D⁻¹|_∞, where the infimum is over D, X εH^n×n_∞, D diagonal.     

How Strong Is Strong Regularity?

We compare the notions of regularity and strong regularity of interval matrices. For an n × n interval matrix A we construct 2ⁿ open convex cones, all of them lying in the interior of the nonnegative orthant. It is shown that regularity of A is characterized by nonemptiness of all these cones, whereas strong regularity is characterized by nonemptiness of their intersection.     

Fractal-like Matrices

We introduce special sparse n×n-matrices (n=2 ^k ) containing up to 3 ^k ≈n ^1.585 nonzero elements. Their structure is inherited from the famous Sierpinski triangle and is not sensitive to matrix multiplication and inversion. The arithmetical complexity of taking product or inverse of such matrices is proved to be O(n ²).     

Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic

In Valiant’s theory of arithmetic complexity, the classes VP and VNP are analogs of P and NP. A fundamental problem concerning these classes is the Permanent and Determinant Problem: Given a field \mathbbF{\mathbb{F}} of characteristic ≠ 2, and an integer n, what is the minimum m such that the permanent of an n × n matrix X = (x_ij) can be expressed as a determinant of an m × m matrix, where the entries of the determinant matrix are affine linear functions of x_ij ’s, and the equality is in \mathbbF[X]{\mathbb{F}}[{\bf X}]. Mignon and Ressayre (2004) proved a quadratic lower bound m = W(n²)m = \Omega(n^{2}) for fields of characteristic 0. We extend the Mignon–Ressayre quadratic lower bound to all fields of characteristic ≠ 2.     

Simultaneously controllable fuzzy matrices

Let F be a set of n × n fuzzy matrices. F is called simultaneously controllable if there exists a permutation matrix P such that for each A ε F, C = [c_ij] = P A P^T satisfies c_ij ≥ c_ji for i > j, where is the max-min composition. In this paper, the necessary and sufficient conditions for a set of n × n fuzzy matrices to be simultaneously controllable will be established. A constructive algorithm which can determine a simultaneously controllable set of n × n fuzzy matrices is presented as well.     

Stability of linear infinite-dimensional systems revisited

The paper is devoted to a study of stability questions for linear infinite-dimensional discrete-time and continuous-time systems. The concepts of power stability and l ^p Instability for a linear discrete-time system x _k+1 = Ax _k (where x _k ε X, X is a Banach space, A is linear and bounded) are introduced and studied. Relationships between these concepts and the inequality r(A) < 1, where r(A) denotes the spectral radius of A, are also given. The discrete-time results are used for a simple derivation of some well-known properties of exponentially stable and L^p-stable linear continuous-time systems described by [xdot](t) = Ax(t) (A generates here a strongly continuous semigroup of linear and bounded operators on X). Some remarks on norms related to stable systems are also included.     

Construction and algebraic characterizations of a planar four-index transportation problem equivalent to a circularization network flow problem

In this study, a circularization network flow problem with m?+?n?+?2 nodes and (m?+?1)(n?+?1) arcs is described as a planar four-index transportation problem of order 1?×?m?×?n?×?1. Construction and several algebraic characterizations of the planar four-index transportation problem of order 1?×?m?×?n?×?1 are investigated using the generalized inverse and singular value decomposition of its coefficient matrix. The results are compared with some results we obtained on the transportation problem with m sources and n destinations. It is shown that these problems can be solved in terms of eigenvectors of the matrices J _m and J _n , where J _m is a m?×?m matrix whose entries are 1.     

A Generalization of Magic Squares with Applications to Digital Halftoning

A semimagic square of order n is an n×n matrix containing the integers 0,…,n ²−1 arranged in such a way that each row and column add up to the same value. We generalize this notion to that of a zero k×k -discrepancy matrix by replacing the requirement that the sum of each row and each column be the same by that of requiring that the sum of the entries in each k×k square contiguous submatrix be the same. We show that such matrices exist if k and n are both even, and do not if k and n are relatively prime. Further, the existence is also guaranteed whenever n=k ^m , for some integers k,m≥2. We present a space-efficient algorithm for constructing such a matrix. Another class that we call constant-gap matrices arises in this construction. We give a characterization of such matrices. An application to digital halftoning is also mentioned. A preliminary version of this paper appeared in Proceedings of International Symposium on Algorithms and Computation, Hong Kong, December, 2004. Part of the work on the paper has been carried out when B.A. was visiting JAIST. Work of B.A. on this paper was supported in part by NSF ITR Grant CCR-00-81964. Work of T.A. was partially supported by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Scientific Research (B).     

On Nesterov's smooth Chebyshev–Rosenbrock function

We discuss a modification of the chained Rosenbrock function introduced by Nesterov. This function r _N is a polynomial of degree 4 defined for x∈? ⁿ . Its only stationary point is the global minimizer x*=(1, 1, …, 1)^T with optimal value zero. A point x ⁽⁰⁾ in the box B:=<texlscub>x |?1≤x _i ≤1 for 1≤i≤n</texlscub>with r _N (x ⁽⁰⁾)=1 is given such that there is a continuous piecewise linear descent path within B that starts at x ⁽⁰⁾ and leads to x*. It is shown that any continuous piecewise linear descent path starting at x ⁽⁰⁾ consists of at least an exponential number of 0.72·1.618 ⁿ linear segments before reducing the value of r _N to 0.25. Moreover, there exists a uniform bound, independent of n, on the Lipschitz constant for the second derivative of r _N within B.     

Sui sistemi lineari contenenti un parametro

Given a system of linear equations with matrix of the coefficients of the formA+tB, whereA andB aren×n real matrices,A symmetric positive definite,B skew, we present an iterative procedure for solving a sequence of such systems, generated by assigning discrete increasing real values to the parametert.      

Further results on the algebraic characterizations of a minimum cost network flow problem equivalent to the transportation problem

In this study a minimum cost network flow problem with m+n+2 nodes and mn arcs, which is equivalent to the transportation problem with m sources and n destinations, is described as an axial four-index transportation problem of order 1×m×n×1. Several algebraic characterizations of this problem of order 1×m×n×1 are investigated using the singular value decomposition and generalized inverses of its coefficient matrix. The results are compared with some results on the planar four-index transportation problem. It is shown that these problems have common algebraic characterizations and can be solved in terms of eigenvectors of the matrices J _m and J _n where J _m is an m×m matrix, all of whose entries are 1.     

Black brane solutions related to non-singular Kac-Moody algebras

A multidimensional gravitational model containing scalar fields and antisymmetric forms is considered. The manifold is chosen in the form M = M ₀ × M ₁ × … × M _n , where M _i are Einstein spaces (i ≥ 1). The sigma-model approach and exact solutions with intersecting composite branes (e.g., solutions with harmonic functions and black brane ones) with intersection rules related to non-singular Kac-Moody (KM) algebras (e.g., hyperbolic ones) are considered. Some examples of black brane solutions are presented, e.g., those corresponding to hyperbolic KM algebras: H ₂(q, q) (q > 2), HA ₂⁽¹⁾ = A ₂⁺⁺ and to the Lorentzian KM algebra P ₁₀.     

Solutions to the generalized Sylvester matrix equations by a singular value decomposition

In this paper,solutions to the generalized Sylvester matrix equations AX-XF=BY and MXN-X=TY with A,M∈Rn×n,B,T∈Rn×n,F,N∈Rp×p and the matrices N,F being in companion form,are established by a singular value decomposition of a matrix with dimensions n×(n pr).The algorithm proposed in this paper for the euqation AX-XF=BY does not require the controllability of matrix pair(A,B)andthe restriction that A,F do not have common eigenvalues.Since singular value decomposition is adopted,the algorithm is numerically stable and may provide great convenience to the computation of the solution to these equations,and can perform important functions in many design problems in control systems theory.