A constructive proof of the Cartan-Dieudonné-Scherk Theorem in the real or complex case

The Cartan-Dieudonné-Scherk Theorem states that for fields of characteristic other than 2, every orthogonality can be written as the product of a certain minimal number of reflections across hyperplanes. The earliest proofs are not constructive, and constructive proofs either do not achieve minimal results or have been restricted to special cases. This paper presents a constructive proof in the real or complex field of the decomposition of a generalized orthogonal matrix into the product of the minimal number of generalized Householder matrices.     

Shape optimisation analysing the inner structure of sensitivity matrices

This contribution deals with sensitivity analysis in nodal based shape optimisation. Sensitivity analysis is one of the most important parts of a structural optimisation algorithm. The efficiency of the algorithm mainly depends on the obtained sensitivity information. The pseudo load and sensitivity matrices which appear in sensitivity analysis are commonly used to derive and to calculate the gradients and the Hessian matrices of objective functions and of constraints. The aim of this contribution is to show that these matrices contain additional useful information which is not used in structural optimisation until now. We demonstrate the opportunities and capabilities of the new information which are obtained by singular value decomposition (SVD) of the pseudo load and sensitivity matrices and by eigenvalue decomposition of the Hessian matrix. Furthermore, we avoid jagged boundaries in shape optimisation by applying a density filtering technique well-known in topology optimisation. Numerical examples illustrate the advocated theoretical concept. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A structure of the Bang-Bang representation for 3×3 embeddable matrices

Summary Necessary and sufficient conditions are given for a 3×3 stochastic matrix to be embeddable by 6 elementary stochastic matrices (Poisson matrices). For a 3×3 embeddable matrix, a structure of the minimal Bang-Bang representation, i.e. the one that contains the smallest number of elementary matrices, is obtained. Based on the minimal Bang-Bang representation an algorithm for determining the embeddability of a 3×3 stochastic matrix is given.I would like to thank Søren Johansen for helpful comments and stimulating discussions on the subject of this paper     

A heuristic for decomposing traffic matrices in TDMA satellite communication

A heuristic for decomposing traffic matrices in TDMA satellite communication. With the time-division multiple access (TDMA) technique in satellite communication the problem arises to decompose a givenn×n traffic matrix into a weighted sum of a small number of permutation matrices such that the sum of the weights becomes minimal. There are polynomial algorithms when the number of permutation matrices in a decomposition is allowed to be as large asn ². When the number of matrices is restricted ton, the problem is NP-hard. In this paper we propose a heuristic based on a scaling technique which for each number of allowed matrices in the range fromn ton ² allows to give a performance guarantee with respect to the total weight of the solution. As a subroutine we use new heuristic methods for decomposing a matrix of small integers into as few matrices as possible without exceeding the lower bound on the total weight. Computational results indicate that the method might also be practical.This work was supported by the Fonds zur Förderung der wissenschaftlichen Forschung, Project S32/01.     

Bidiagonal decomposition of totally positive Bernstein-Vandermonde matrices

The class of Bernstein-Vandermonde matrices (a generalization of Vandermonde matrices arising when the monomial basis is replaced by the Bernstein basis) is considered. A convenient ordering of their rows makes these matrices strictly totally positive. By using results related to total positivity and Neville elimination, an algorithm for computing the bidiagonal decomposition of a Bernstein-Vandermonde matrix is constructed. The use of explicit expressions for the determinants involved in the process serves to make the algorithm both fast and accurate. One of the applications of our algorithm is the design of fast and accurate algorithms for solving Lagrange interpolation problems when using the Bernstein basis, an approach useful for the field of Computer Aided Geometric Design since it avoids the stability problems involved with basis transformations between the Bernstein and the monomial bases. A different application consists of the use of the bidiagonal decomposition as an intermediate step of the computation of the eigenvalues and the singular value decomposition of a totally positive Bernstein-Vandermonde matrix. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Algorithms for finding the minimal polynomials and inverses of resultant matrices

In this paper, algorithms for computing the minimal polynomial and the common minimal polynomial of resultant matrices over any field are presented by means of the approach for the Gröbner basis of the ideal in the polynomial ring, respectively, and two algorithms for finding the inverses of such matrices are also presented. Finally, an algorithm for the inverse of partitioned matrix with resultant blocks over any field is given, which can be realized by CoCoA 4.0, an algebraic system over the field of rational numbers or the field of residue classes of modulo prime number. We get examples showing the effectiveness of the algorithms.     

求首尾和r-循环矩阵的极小多项式的算法

研究了域上首尾和r-循环矩阵，利用多项式环的理想的Groebner基的算法给出了任意域上首尾和r-循环矩阵的极小多项式和公共极小多项式的一种算法.同时给出了这类矩阵逆矩阵的一种求法。     

Level-m scaled circulant factor matrices over the complex number field and the quaternion division algebra

The level-m scaled circulant factor matrix over the complex number field is introduced. Its diagonalization and spectral decomposition and representation are discussed. An explicit formula for the entries of the inverse of a level-m scaled circulant factor matrix is presented. Finally, an algorithm for finding the inverse of such matrices over the quaternion division algebra is given.     

Takagi’s decomposition of a symmetric unitary matrix as a finite algorithm

Takagi’s decomposition is an analog (for complex symmetric matrices and for unitary similarities replaced by unitary congruences) of the eigenvalue decomposition of Hermitian matrices. It is shown that, if a complex matrix is not only symmetric but is also unitary, then its Takagi decomposition can be found by quadratic radicals, that is, by means of a finite algorithm that involves arithmetic operations and quadratic radicals. A similar fact is valid for the eigenvalue decomposition of reflections, which are Hermitian unitary matrices.     

求鳞状循环因子矩阵的极小多项式的算法

提出了任意域上鳞状循环因子矩阵 ,利用多项式环的理想的Go bner基的算法给出了任意域上鳞状循环因子矩阵的极小多项式和公共极小多项式的一种算法 .同时给出了这类矩阵逆矩阵的一种求法 .在有理数域或模素数剩余类域上 ,这一算法可由代数系统软件Co CoA4 .0实现 .数值例子说明了算法的有效性     

Approximation of Matrices and a Family of Gander Methods for Polar Decomposition

Two matrix approximation problems are considered: approximation of a rectangular complex matrix by subunitary matrices with respect to unitarily invariant norms and a minimal rank approximation with respect to the spectral norm. A characterization of a subunitary approximant of a square matrix with respect to the Schatten norms, given by Maher, is extended to the case of rectangular matrices and arbitrary unitarily invariant norms. Iterative methods, based on the family of Gander methods and on Higham’s scaled method for polar decomposition of a matrix, are proposed for computing subunitary and minimal rank approximants. Properties of Gander methods are investigated in details. AMS subject classification (2000) 65F30, 15A18     

Method of dual matrices for function minimization

In this paper, the method of dual matrices for the minimization of functions is introduced. The method, which is developed on the model of a quadratic function, is characterized by two matrices at each iteration. One matrix is such that a linearly independent set of directions can be generated, regardless of the stepsize employed. The other matrix is such that, at the point where the first matrix fails to yield a gradient linearly independent of all the previous gradients, it generates a displacement leading to the minimal point. Thus, the one-dimensional search is bypassed. For a quadratic function, it is proved that the minimal point is obtained in at mostn + 1 iterations, wheren is the number of variables in the function. Since the one-dimensional search is not needed, the total number of gradient evaluations for convergence is at mostn + 2.Three algorithms of the method are presented. A reverse algorithm, which permits the use of only one matrix, is also given. Considerations pertaining to the applications of this method to the minimization of a quadratic function and a nonquadratic function are given. It is believed that, since the one-dimensional search can be bypassed, a considerable amount of computational saving can be achieved.This paper, supported by the National Science Foundation, Grant No. GP-32453, is based on Ref. 1.     

On the optimality of Krylov information

Let F be an orthogonally invariant class of nonsingular matrices. Examples of such F are symmetric matrices and positive definite matrices. For the problems of solving a system of linear equations or of finding an eigenpair of a matrix, we show that the minimal residual algorithm using Krylov information has almost minimal complexity. The general results are used to derive tight complexity bounds for several classes of matrices.     

A shortest path-based approach to the multileaf collimator sequencing problem

The multileaf collimator sequencing problem is an important component in effective cancer treatment delivery. The problem can be formulated as finding a decomposition of an integer matrix into a weighted sequence of binary matrices whose rows satisfy a consecutive ones property. Minimising the cardinality of the decomposition is an important objective and has been shown to be strongly NP-hard, even for a matrix restricted to a single column or row. We show that in this latter case it can be solved efficiently as a shortest path problem, giving a simple proof that the one-row problem is fixed-parameter tractable in the maximum intensity. We develop new linear and constraint programming models exploiting this result. Our approaches significantly improve the best known for the problem, bringing real-world sized problem instances within reach of exact algorithms.     

Uncertainty and Option Value in Land Allocation Problems

In intensity-modulated radiation therapy (IMRT) not only is the shape of the beam controlled, but combinations of open and closed multileaf collimators modulate the intensity as well. In this paper, we offer a mixed integer programming approach which allows optimization over beamlet fluence weights as well as beam and couch angles. Computational strategies, including a constraint and column generator, a specialized set-based branching scheme, a geometric heuristic procedure, and the use of disjunctive cuts, are described. Our algorithmic design thus far has been motivated by clinical cases. Numerical tests on real patient cases reveal that good treatment plans are returned within 30 minutes. The MIP plans consistently provide superior tumor coverage and conformity, as well as dose homogeneity within the tumor region while maintaining a low irradiation to important critical and normal tissues.     

Decomposition of Matrices into Involutory Matrices and Symmetric Matrices

Let \Omega be a field, and let F denote the Frobenius matrix: $[F = \left( {\begin{array}{*{20}{c}} 0&{ - {\alpha _n}}\{{E_{n - 1}}}&\alpha \end{array}} \right)\]$ where \alpha is an n-1 dimentional vector over Q, and E_n- 1 is identity matrix over \Omega. Theorem 1. There hold two elementary decompositions of Frobenius matrix: (i) F=SJB, where S, J are two symmetric matrices, and B is an involutory matrix; (ii) F=CQD, where O is an involutory matrix, Q is an orthogonal matrix over \Omega, and D is a diagonal matrix. We use the decomposition (i) to deduce the following two theorems: Theorem 2. Every square matrix over \Omega is a product of twe symmetric matrices and one involutory matrix. Theorem 3. Every square matrix over \Omega is a product of not more than four symmetric matrices. By using the decomposition (ii), we easily verify the following Theorem 4(Wonenburger-Djokovic') . The necessary and sufficient condition that a square matrix A may be decomposed as a product of two involutory matrices is that A is nonsingular and similar to its inverse A^-1 over Q (See [2, 3]). We also use the decomosition (ii) to obtain Theorem 5. Every unimodular matrix is similar to the matrix CQB, where C, B are two involutory matrices, and Q is an orthogonal matrix over Q. As a consequence of Theorem 5. we deduce immediately the following Theorem 6 (Gustafson-Halmos-Radjavi). Every unimodular matrix may be decomposed as a product of not more than four involutory matrices (See [1] ). Finally, we use the decomposition (ii) to derive the following Thoerem 7. If the unimodular matrix A possesses one invariant factor which is not constant polynomial, or the determinant of the unimodular matrix A is I and A possesses two invariant factors with the same degree (>0), then A may be decomposed as a product of three involutory matrices. All of the proofs of the above theorems are constructive.     

基于均值的Toeplitz矩阵填充的子空间算法

本文提出一种基于均值的Toeplitz矩阵填充的子空间算法.通过在左奇异向量空间中对已知元素的最小二乘逼近,形成了新的可行矩阵;并利用对角线上的均值化使得迭代后的矩阵保持Toeplitz结构,从而减少了奇异向量空间的分解时间.理论上,证明了在一定条件下该算法收敛于一个低秩的Toeplitz矩阵.通过不同已知率的矩阵填充数值实验展示了Toeplitz矩阵填充的新算法比阈值增广Lagrange乘子算法在时间上和精度上更有效.     

On the representability of totally unimodular matrices on bidirected graphs

We present a polynomial time algorithm to construct a bidirected graph for any totally unimodular matrix B by finding node-edge incidence matrices Q and S such that QB=S. Seymour’s famous decomposition theorem for regular matroids states that any totally unimodular (TU) matrix can be constructed through a series of composition operations called k-sums starting from network matrices and their transposes and two compact representation matrices B₁,B₂ of a certain ten element matroid. Given that B₁,B₂ are binet matrices we examine the k-sums of network and binet matrices. It is shown that thek-sum of a network and a binet matrix is a binet matrix, but binet matrices are not closed under this operation for k=2,3. A new class of matrices is introduced, the so-called tour matrices, which generalise network, binet and totally unimodular matrices. For any such matrix there exists a bidirected graph such that the columns represent a collection of closed tours in the graph. It is shown that tour matrices are closed under k-sums, as well as under pivoting and other elementary operations on their rows and columns. Given the constructive proofs of the above results regarding the k-sum operation and existing recognition algorithms for network and binet matrices, an algorithm is presented which constructs a bidirected graph for any TU matrix.     

On a Toeplitz Representation of the H1/2 Norm

Some representations of the H1/2 norm are used as Schur complement preconditioner in PCG based domain decomposition algorithms for elliptic problems. These norm representations are efficient preconditioners but the corresponding matrices are dense, so they need FFT algorithm for matrix-vector multiplications. Here we give a new matrix representation of this norm by a special Toeplitz matrix. It contains only O(log(n)) different entries at each row, where n is the number of rows and so a matrix-vector computation can be done by O(nlog(n)) arithmetic operation without using FFT algorithm. The special properties of this matrix assure that it can be used as preconditioner. This is proved by estimating spectral equivalence constants and this fact has also been verified by numerical tests.