Embeddings through discrete sets of balls

We investigate whether a Stein manifold M which allows proper holomorphic embedding into ℂ ⁿ can be embedded in such a way that the image contains a given discrete set of points and in addition follow arbitrarily close to prescribed tangent directions in a neighbourhood of the discrete set. The infinitesimal version was proven by Forstnerič to be always possible. We give a general positive answer if the dimension of M is smaller than n/2 and construct counterexamples for all other dimensional relations. The obstruction we use in these examples is a certain hyperbolicity condition.     

The recognition of symmetric latin squares

A latin square S is isotopic to another latin square S′ if S′ can be obtained from S by permuting the row indices, the column indices and the symbols in S. Because the three permutations used above may all be different, a latin square which is isotopic to a symmetric latin square need not be symmetric. We call the problem of determining whether a latin square is isotopic to a symmetric latin square the symmetry recognition problem. It is the purpose of this article to give a solution to this problem. For this purpose we will introduce a cocycle corresponding to a latin square which transforms very simply under isotopy, and we show this cocycle contains all the information needed to determine whether a latin square is isotopic to a symmetric latin square. Our results relate to 1‐factorizations of the complete graph on n + 1 vertices, K_{n + 1}. There is a well known construction which can be used to make an n × n latin square from a 1‐factorization on n + 1 vertices. The symmetric idempotent latin squares are exactly the latin squares that result from this construction. The idempotent recognition problem is simple for symmetric latin squares, so our results enable us to recognize exactly which latin squares arise from 1‐factorizations of K_{n + 1}. As an example we show that the patterned starter 1‐factorization for the group G gives rise to a latin square which is in the main class of the Cayley latin square for G if and only if G is abelian. Hence, every non‐abelian group gives rise to two latin squares in different main classes. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 291–300, 2008     

The retraction algorithm for factoring banded symmetric matrices

Let A be an n × n symmetric matrix of bandwidth 2m + 1. The matrix need not be positive definite. In this paper we will present an algorithm for factoring A which preserves symmetry and the band structure and limits element growth in the factorization. With this factorization one may solve a linear system with A as the coefficient matrix and determine the inertia of A, the number of positive, negative, and zero eigenvalues of A. The algorithm requires between 1/2nm² and 5/4nm² multiplications and at most (2m + 1)n locations compared to non‐symmetric Gaussian elimination which requires between nm² and 2nm² multiplications and at most (3m + 1)n locations. Our algorithm reduces A to block diagonal form with 1 × 1 and 2 × 2 blocks on the diagonal. When pivoting for stability and subsequent transformations produce non‐zero elements outside the original band, column/row transformations are used to retract the bandwidth. To decrease the operation count and the necessary storage, we use the fact that the correction outside the band is rank‐1 and invert the process, applying the transformations that would restore the bandwidth first, followed by a modified correction. This paper contains an element growth analysis and a computational comparison with LAPACKs non‐symmetric band routines and the Snap‐back code of Irony and Toledo. Copyright © 2007 John Wiley & Sons, Ltd.     

Symmetries that latin squares inherit from 1‐factorizations

A 1‐factorization of a graph is a decomposition of the graph into edge disjoint perfect matchings. There is a well‐known method, which we call the ??‐construction, for building a 1‐factorization of K_n,n from a 1‐factorization of K_{n + 1}. The 1‐factorization of K_n,n can be written as a latin square of order n. The ??‐construction has been used, among other things, to make perfect 1‐factorizations, subsquare‐free latin squares, and atomic latin squares. This paper studies the relationship between the factorizations involved in the ??‐construction. In particular, we show how symmetries (automorphisms) of the starting factorization are inherited as symmetries by the end product, either as automorphisms of the factorization or as autotopies of the latin square. Suppose that the ??‐construction produces a latin square L from a 1‐factorization F of K_{n + 1}. We show that the main class of L determines the isomorphism class of F, although the converse is false. We also prove a number of restrictions on the symmetries (autotopies and paratopies) which L may possess, many of which are simple consequences of the fact that L must be symmetric (in the usual matrix sense) and idempotent. In some circumstances, these restrictions are tight enough to ensure that L has trivial autotopy group. Finally, we give a cubic time algorithm for deciding whether a main class of latin squares contains any square derived from the ??‐construction. The algorithm also detects symmetric squares and totally symmetric squares (latin squares that equal their six conjugates). © 2005 Wiley Periodicals, Inc. J Combin Designs 13: 157–172, 2005.     

Detecting “dense” columns in interior point methods for linear programs

During the iterations of interior point methods symmetric indefinite systems are decomposed by LD̂L ^T factorization. This step can be performed in a special way where the symmetric indefinite system is transformed to a positive definite one, called the normal equations system. This approach proved to be efficient in most of the cases and numerically reliable, due to the positive definite property. It has been recognized, however, that in case the linear program contains “dense” columns, this approach results in an undesirable fill–in during the computations and the direct factorization of the symmetric indefinite system is more advantageous. The paper describes a new approach to detect cases where the system of normal equations is not preferable for interior point methods and presents a new algorithm for detecting the set of columns which is responsible for the excessive fill–in in the matrix AA ^T . By solving large–scale linear programming problems we demonstrate that our heuristic is reliable in practice. This work was supported in part by the Hungarian Scientific Research Fund OTKA K60480.     

A twisted factorization method for symmetric SVD of a complex symmetric tridiagonal matrix

This paper presents an O(n²) method based on the twisted factorization for computing the Takagi vectors of an n‐by‐n complex symmetric tridiagonal matrix with known singular values. Since the singular values can be obtained in O(n²) flops, the total cost of symmetric singular value decomposition or the Takagi factorization is O(n²) flops. An analysis shows the accuracy and orthogonality of Takagi vectors. Also, techniques for a practical implementation of our method are proposed. Our preliminary numerical experiments have verified our analysis and demonstrated that the twisted factorization method is much more efficient than the implicit QR method, divide‐and‐conquer method and Matlab singular value decomposition subroutine with comparable accuracy. Copyright © 2009 John Wiley & Sons, Ltd.     

A fast method to block-diagonalize a Hankel matrix

In this paper, we consider an approximate block diagonalization algorithm of an n×n real Hankel matrix in which the successive transformation matrices are upper triangular Toeplitz matrices, and propose a new fast approach to compute the factorization in O(n ²) operations. This method consists on using the revised Bini method (Lin et al., Theor Comp Sci 315: 511–523, 2004). To motivate our approach, we also propose an approximate factorization variant of the customary fast method based on Schur complementation adapted to the n×n real Hankel matrix. All algorithms have been implemented in Matlab and numerical results are included to illustrate the effectiveness of our approach.     

HYPERPLANE TRANSVERSALS OF HOMOTHETICAL,CENTRALLY SYMMETRIC POLYTOPES

Let P ⊂ R ⁿ be a centrally symmetric, convex n-polytope with 2r vertices, n ≥ 2. Let P be a family of m ≥ n + 1 homothetical copies of P. Based on an algorithmical approach to center hyperplanes of finite point sets in Minkowski spaces with polyhedral norms, we show that a hyperplane transversal of all members of P (if it exists) can be found in O(rm) time when the dimension n is fixed. This revised version was published online in August 2006 with corrections to the Cover Date.     

CM–fields and skew–symmetric matrices

Cohen and Odoni prove that every CM–field can be generated by an eigenvalue of some skew–symmetric matrix with rational coefficients. It is natural to ask for the minimal dimension of such a matrix. They show that every CM–field of degree 2n is generated by an eigenvalue of a skew–symmetric matrix over Q of dimension at most 4n+2. The aim of the present paper is to improve this bound.     

On canonical factorization of rational matrix functions

This paper concerns the problem of canonical factorization of a rational matrix functionW() which is analytic but may benot invertible at infinity. The factors are obtained explicitly in terms of the realization of the original matrix function. The cases of symmetric factorization for selfadjoint and positive rational matrix functions are considered separately.     

Spectral factorization of rectangular rational matrix functions with application to discrete Wiener-Hopf equations

The properties of a discrete Wiener-Hopf equation are closely related to the factorization of the symbol of the equation. We give a necessary and sufficient condition for existence of a canonical Wiener-Hopf factorization of a possibly nonregular rational matrix function W relative to a contour which is a positively oriented boundary of a region in the finite complex plane. The condition involves decomposition of the state space in a minimal realization of W and, if it is satisfied, we give explicit formulas for the factors. The results are generalized by means of centered realizations to arbitrary rational matrix functions. The proposed approach can be used to solve discrete Wiener-Hopf equations whose symbols are rational matrix functions which admit canonical factorization relative to the unit circle.     

A structure of doubly stochastic Markov chains

Kingman and Williams [6] showed that a pattern of positive elements can occur in a transition matrix of a finite state, nonhomogeneous Markov chain if and only if it may be expressed as a finite product of reflexive and transitive patterns. In this paper we solve a similar problem for doubly stochastic chains. We prove that a pattern of positive elements can occur in a transition matrix of a doubly stochastic Markov chain if and only if it may be expressed as a finite product of reflexive, transitive, and symmetric patterns. We provide an algorithm for determining whether a given pattern may be expressed as a finite product of reflexive, transitive, and symmetric patterns. This result has implications for the embedding problem for doubly stochastic Markov chains. We also give the application of the obtained characterization to the chain majorization.     

Wilkinson's inertia‐revealing factorization and its application to sparse matrices

We propose a new inertia‐revealing factorization for sparse symmetric matrices. The factorization scheme and the method for extracting the inertia from it were proposed in the 1960s for dense, banded, or tridiagonal matrices, but they have been abandoned in favor of faster methods. We show that this scheme can be applied to any sparse symmetric matrix and that the fill in the factorization is bounded by the fill in the sparse QR factorization of the same matrix (but is usually much smaller). We describe our serial proof‐of‐concept implementation and present experimental results, studying the method's numerical stability and performance.     

Modified Cholesky algorithms: a catalog with new approaches

Given an n ×  n symmetric possibly indefinite matrix A, a modified Cholesky algorithm computes a factorization of the positive definite matrix A +  E, where E is a correction matrix. Since the factorization is often used to compute a Newton-like downhill search direction for an optimization problem, the goals are to compute the modification without much additional cost and to keep A +  E well-conditioned and close to A. Gill, Murray and Wright introduced a stable algorithm, with a bound of ||E||₂ =  O(n ²). An algorithm of Schnabel and Eskow further guarantees ||E||₂ =  O(n). We present variants that also ensure ||E||₂ =  O(n). Moré and Sorensen and Cheng and Higham used the block LBL ^T factorization with blocks of order 1 or 2. Algorithms in this class have a worst-case cost O(n ³) higher than the standard Cholesky factorization. We present a new approach using a sandwiched LTL ^T -LBL ^T factorization, with T tridiagonal, that guarantees a modification cost of at most O(n ²). H.-r. Fang’s work was supported by National Science Foundation Grant CCF 0514213. D. P. O’Leary’s work was supported by National Science Foundation Grant CCF 0514213 and Department of Energy Grant DEFG0204ER25655.     

Characterizations of rectangular totally and strictly totally positive matrices

An n×m real matrix A is said to be totally positive (strictly totally positive) if every minor is nonnegative (positive). In this paper, we study characterizations of these classes of matrices by minors, by their full rank factorization and by their thin QR factorization.     

Lower Bounds on Matrix Factorization Ranks via Noncommutative Polynomial Optimization

We use techniques from (tracial noncommutative) polynomial optimization to formulate hierarchies of semidefinite programming lower bounds on matrix factorization ranks. In particular, we consider the nonnegative rank, the positive semidefinite rank, and their symmetric analogs: the completely positive rank and the completely positive semidefinite rank. We study convergence properties of our hierarchies, compare them extensively to known lower bounds, and provide some (numerical) examples.

     

Embedding partial totally symmetric quasigroups

This paper concerns the embedding problem for partial totally symmetric quasigroups. For all n?9, it is shown that any partial totally symmetric quasigroup of order n can be embedded in a totally symmetric quasigroup of order v if v is even and v?2n+4, and this is the best possible such inequality.     

On a conjugate directions method for solving strictly convex QP problem

Problem of solving the strictly convex, quadratic programming problem is studied. The idea of conjugate directions is used. First we assume that we know the set of directions conjugate with respect to the hessian of the goal function. We apply n simultaneous directional minimizations along these conjugate directions starting from the same point followed by the addition of the directional corrections. Theorem justifying that the algorithm finds the global minimum of the quadratic goal function is proved. The way of effective construction of the required set of conjugate directions is presented. We start with a vector with zero value entries except the first one. At each step new vector conjugate to the previously generated is constructed whose number of nonzero entries is larger by one than in its predecessor. Conjugate directions obtained by means of the above construction procedure with appropriately selected parameters form an upper triangular matrix which in exact computations is the Cholesky factor of the inverse of the hessian matrix. Computational cost of calculating the inverse factorization is comparable with the cost of the Cholesky factorization of the original second derivative matrix. Calculation of those vectors involves exclusively matrix/vector multiplication and finding an inverse of a diagonal matrix. Some preliminary computational results on some test problems are reported. In the test problems all symmetric, positive definite matrices with dimensions from \(14\times 14\) to \(2000\times 2000\) from the repository of the Florida University were used as the hessians.     

Matrix Functions Consimilar to the Identity and Singular Integral Operators

In this paper we establish the connection between singular integral operators with conjugation and matrix functions consimilar to the identity. We show that any matrix function consimilar to the identity is factorable (in some space L _p ) if and only if it admits a special factorization, that we call antisymmetric, and that this antisymmetric factorization has a direct connection with the factorization of singular integral operators with conjugation. Submitted: April 27, 2007. Accepted: January 23, 2008.     

Uniform and minimal {0,1} – cp matrices

Let A be an n?×?n real matrix. A is called {0,1}-cp if it can be factorized as A?=?BB ^T with b_ij =0 or 1. The smallest possible number of columns of B in such a factorization is called the {0,1}-rank of A. A {0,1}-cp matrix A is called minimal if for every nonzero nonnegative n?×?n diagonal matrix D, A-D is not {0,1}-cp, and r-uniform if it can be factorized as A=BB ^T, where B is a (0,?1) matrix with r 1s in each column. In this article, we first present a necessary condition for a nonsingular matrix to be {0,1}-cp. Then we characterize r-uniform {0,1}-cp matrices. We also obtain some necessary conditions and sufficient conditions for a matrix to be minimal {0,1}-cp, and present some bounds for {0,1}-ranks.