The Eigenvalues of Very Sparse Random Symmetric Matrices

Let W _n be an n × n random symmetric sparse matrix with independent identically distributed entries such that the values 1 and 0 are taken with probabilities p/n and 1-p/n, respectively; here is independent of n. We show that the limit of the expected spectral distribution functions of W _n has a discrete part. Moreover, the set of positive probability points is dense in (- +). In particular, the points , and 0 belong to this set.     

The Shanno-Toint Procedure for Updating Sparse Symmetric Matrices

Two recent methods (Shanno, 1978; Toint, 1980) for revisingestimates of sparse second derivative matrices in quasi-Newtonoptimization algorithms reduce to variable metric formulae whenthere are no sparsity conditions. It is proved that these methodsare equivalent. Further, some examples are given to show thatthe procedure may make the second derivative approximationsworse when the objective function is quadratic. Therefore theconvergence properties of the procedure are sometimes less goodthan the convergence properties of other published methods forrevising sparse second derivative approximations.     

Indefinite QR Factorization

Let A be a Hermitian positive definite matrix given by its rectangular factor G such that A=G^*G. It is well known that the Cholesky factorization of A is equivalent to the QR factorization of G. In this paper, an analogue of the QR factorization for Hermitian indefinite matrices is constructed. This problem has been considered by many authors, but the problem of zero diagonal elements has not been solved so far. Here we show how to overcome this difficulty. AMS subject classification (2000) 65F25, 46C20, 65F15     

An Incomplete Cholesky Factorization for Dense Symmetric Positive Definite Matrices

In this paper, we study the use of an incomplete Cholesky factorization (ICF) as a preconditioner for solving dense symmetric positive definite linear systems. This method is suitable for situations where matrices cannot be explicitly stored but each column can be easily computed. Analysis and implementation of this preconditioner are discussed. We test the proposed ICF on randomly generated systems and large matrices from two practical applications: semidefinite programming and support vector machines. Numerical comparison with the diagonal preconditioner is also presented.     

Stability of the Matrix Factorization for Solving Block Tridiagonal Symmetric Indefinite Linear Systems

In this paper, we propose a new factorization method for block tridiagonal symmetric indefinite matrices. We also discuss the stability of the factorization method. As a measurement of stability, an effective condition number is derived by using backward error analysis and perturbation analysis. It shows that under some suitable assumptions, the solution obtained by this factorization method is acceptable. Numerical results demonstrate that the factorization is stable if its condition number is not too large. This revised version was published online in July 2006 with corrections to the Cover Date.     

Direct Solution of Sets of Linear Equations whose Matrix is Sparse, Symmetric and Indefinite

We consider the use of 1?1 and 2?2 pivots for direct solutionof sets of linear equations whose matrix is sparse and symmetric.Inclusion of 2?2 pivots permits a stable decomposition to beobtained in the indefinite case and we demonstrate that in practicethere is little loss of speed even in positive definite cases.A pivotal strategy suitable for the sparse case is proposedand compared experimentally with alternatives. We present ananalysis of error, explain how the stability may be monitoredcheaply, discuss automatic scaling and consider implementationdetails.     

关于稳定可逆矩阵的分解(英文)

证明了稳定可逆矩阵相似于两个循环矩阵的积.并且进一步地证明了稳定可逆矩阵可表成对角矩阵与换位子的积.     

Pascal矩阵的一种显式分解

本文引入了两种广义Pascal矩阵凡,P_n,k,Q_n,k以及两种广义Pascal函数矩阵O_n,k[x,y],Q_n,k[x,y],证明了Pascal矩阵能够表示成(0,1)-Jordan矩阵的乘积而且Pascal函数矩阵能分解成双对角矩阵的乘积.     

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.     

The Significant Order of Symmetric Tridiagonal Matrices

It is demonstrated that an eigenvalue of a symmetric tridiagonalmatrix as calculated by the Sturm sequence bisection procedure,is determined in general by a leading principal partition ofthe whole matrix. The order of this leading principal partitionis called the significant order of the matrix. The significantorder depends upon the specific eigenvalue being calculated,and upon the working precision of the computer. This numericalphenomenon may be employed to accelerate the bisection procedure.In applications it either indicates the adequacy or otherwiseof the working precision for finite matrices, or in the caseof theoretically infinite matrices, the effective truncationorder for the precision employed.     

对称正交反对称矩阵反问题

设P为一给定的对称正交矩阵, 记SAR\+n\-P={A∈R\+\{n×n\}|A\+T=A,(PA)\+T=-PA}. 该文考虑下列问题问题Ⅰ〓给定X∈R\+\{n×m, Λ=diag(λ\-1,λ\-2,…, λ\-m)∈R\+\{m×m\}, 求A∈SAR\+n\-P使AX=XΛ,问题Ⅱ〓给定X,B∈R\+\{n×m, 求A∈SAR\+n\-P使  ‖AX-B‖=min.问题Ⅲ设[AKA～]∈R\+\{n×n\},求A\+*∈S\-E使 ‖[AKA～]-A\+*‖=inf[DD(X]A∈S\-E[DD)]‖[AKA～]-A‖, 其中S\-E为问题Ⅱ的解集合, ‖·‖表示Frobenius范数.该文得到了问题Ⅰ有解的充要条件及解集合的表达式, 给出了解集合S\-E的通式和逼近解A\+*的具体表达式.     

双对称本原矩阵k-点指数的极矩阵

一个n阶本原矩阵A的k-点指数是A的最小幂指数,使得在这个幂中,存在着k个全1行．最近我们得到了n阶双对称本原矩阵的k-点指数的上确界．本文将在此基础上,以伴随图的形式给出其极矩阵的完全刻划．     

Use of the Lanczos Method for Finding Complete Sets of Eigenvalues of Large Sparse Symmetric Matrices

A way of using the Lanczos method to find all the eigenvaluesof a large sparse symmetric matrix is described, and some empiricalobservations on the manner in which the method works in practiceare given. The method seems to be accurate, fast, and not verydemanding on storage. A formula for the number of iterationsnecessary to get the eigenvalues is proposed.     

基于反Krylov矩阵正交分解的半可分矩阵

在本文中，我们证明了对一个反Krylov矩阵作QR分解后，利用得到的正交矩阵可以将一个具有互异特征值的对称矩阵转化为一个半可分矩阵的形式，这个结果表明了反Krylov矩阵与半可分矩阵之间的联系．另外，我们还证明了这类对称半可分矩阵在QR达代下矩阵结构保持不变性．     

Symmetric Weighing Matrices Constructed using Group Matrices

A weighing matrix of order n and weight m² is a square matrix M of order n with entries from {-1,0,+1} such that MM^T=m²I where I is the identity matrix of order n. If M is a group matrix constructed using a group of order n, M is called a group weighing matrix. Recently, group weighing matrices were studied intensively, especially when the groups are cyclic and abelian. In this paper, we study the abelian group weighing matrices that are symmetric, i.e.M^T=M. Some new examples are found. Also we obtain a few exponent bounds on abelian groups that admit symmetric group weighing matrices. In particular, we prove that there is no symmetric abelian group weighing matrices of order 2p^r and weight p² where p is a prime and p≥ 5.Communicated by: K.T. Arasu     

广义对称矩阵反问题有解的条件

本利用矩阵的奇异值分解讨论了一类广义对矩阵阵反问题，得到了此类矩阵反问题有解的充分必要条件及通解的表达式。     

双对称本原矩阵κ-点指数的极矩阵

一个n阶本原矩阵A的κ-点指数是A的最小幂指数,使得在这个幂中,存在着κ个全1行.最近我们得到了n阶双对称本原矩阵的κ-点指数的上确界.本文将在此基础上,以伴随图的形式给出其极矩阵的完全刻划.     

对称中心本原矩阵的指数集

This paper first establishes a distance inequality of the associated diagraph of a central symmetric primitive matrix, then characters the exponent set of central symmetric primitive matrices, and proves that the exponent set of central symmetric primitive matrices of order n is {1, 2,… ,n-1}. There is no gap in it.     

On Sparse Parity Check Matrices

We consider the extremal problem to determine the maximal number of columns of a 0-1 matrix with rows and at most ones in each column such that each columns are linearly independent modulo . For fixed integers and , we shall prove the probabilistic lower bound = ; for a power of , we prove the upper bound which matches the lower bound for infinitely many values of . We give some explicit constructions.