Hoffman polynomials of nonnegative irreducible matrices and strongly connected digraphs

For a nonnegative n × n matrix A, we find that there is a polynomial f(x)∈R[x] such that f(A) is a positive matrix of rank one if and only if A is irreducible. Furthermore, we show that the lowest degree such polynomial f(x) with tr f(A) = n is unique. Thus, generalizing the well-known definition of the Hoffman polynomial of a strongly connected regular digraph, for any irreducible nonnegative n × n matrix A, we are led to define its Hoffman polynomial to be the polynomial f(x) of minimum degree satisfying that f(A) is positive and has rank 1 and trace n. The Hoffman polynomial of a strongly connected digraph is defined to be the Hoffman polynomial of its adjacency matrix. We collect in this paper some basic results and open problems related to the concept of Hoffman polynomials.     

Approximating classes of sequences: The Hermitian case

Given a sequence {A_n} of matrices A_n of increasing dimension d_n with d_k>d_q for k>q, k,q∈N, we recently introduced the concept of approximating class of sequences (a.c.s.) in order to define a basic approximation theory for matrix sequences. We have shown that such a notion is stable under inversion, linear combinations, and product, whenever natural and mild conditions are satisfied. In this note we focus our attention on the Hermitian case and we show that is an a.c.s. for {f(A_n)}, if is an a.c.s. for {A_n}, {A_n} is sparsely unbounded, and f is a suitable continuous function defined on R. We also discuss the potential impact and future developments of such a result.     

Factoring matrices with a tree-structured sparsity pattern

Let A be a matrix whose sparsity pattern is a tree with maximal degree d_max. We show that if the columns of A are ordered using minimum degree on |A|+|A|^∗, then factoring A using a sparse LU with partial pivoting algorithm generates only O(d_maxn) fill, requires only O(d_maxn) operations, and is much more stable than LU with partial pivoting on a general matrix. We also propose an even more efficient and just-as-stable algorithm called sibling-dominant pivoting. This algorithm is a strict partial pivoting algorithm that modifies the column preordering locally to minimize fill and work. It leads to only O(n) work and fill. More conventional column pre-ordering methods that are based (usually implicitly) on the sparsity pattern of |A|^∗|A| are not as efficient as the approaches that we propose in this paper.     

On a new notion of the solution to an ill-posed problem

A new understanding of the notion of the stable solution to ill-posed problems is proposed. The new notion is more realistic than the old one and better fits the practical computational needs. A method for constructing stable solutions in the new sense is proposed and justified. The basic point is: in the traditional definition of the stable solution to an ill-posed problem Au=f, where A is a linear or nonlinear operator in a Hilbert space H, it is assumed that the noisy data {f_δ,δ} are given, ‖f−f_δ‖≤δ, and a stable solution u_δ:=R_δf_δ is defined by the relation lim_δ→0‖R_δf_δ−y‖=0, where y solves the equation Au=f, i.e., Ay=f. In this definition y and f are unknown. Any f∈B(f_δ,δ) can be the exact data, where B(f_δ,δ):={f:‖f−f_δ‖≤δ}.The new notion of the stable solution excludes the unknown y and f from the definition of the solution. The solution is defined only in terms of the noisy data, noise level, and an a priori information about a compactum to which the solution belongs.     

Implementation of a restarted Krylov subspace method for the evaluation of matrix functions

A new implementation of restarted Krylov subspace methods for evaluating f(A)b for a function f, a matrix A and a vector b is proposed. In contrast to an implementation proposed previously, it requires constant work and constant storage space per restart cycle. The convergence behavior of this scheme is discussed and a new stopping criterion based on an error indicator is given. The performance of the implementation is illustrated for three parabolic initial value problems, requiring the evaluation of exp(A)b.     

Block tridiagonal reduction of perturbed normal and rank structured matrices

It is well known that if a matrix A∈C^n×n$A\in {\mathbb{C}}^{n\times n}$ solves the matrix equation f(A,A^H)=0$f(A,A^H)=0$, where f(x,y)$f(x,y)$ is a linear bivariate polynomial, then A is normal; A   and A^H$A^H$ can be simultaneously reduced in a finite number of operations to tridiagonal form by a unitary congruence and, moreover, the spectrum of A is located on a straight line in the complex plane. In this paper we present some generalizations of these properties for almost normal matrices which satisfy certain quadratic matrix equations arising in the study of structured eigenvalue problems for perturbed Hermitian and unitary matrices.     

Directional approximation of the jacobians in ROW-methods

In this paper a new technique for avoiding exact Jacobians in ROW methods is proposed. The Jacobiansf' _n are substituted by matricesA _n satisfying a directional consistency conditionA _n f _n =f' _n f _n +O(h). In contrast to generalW-methods this enables us to reduce the number of order conditions and we construct a 2-stage method of order 3 and families of imbedded 4-stage methods of order 4(3). The directional approximation of the Jacobians has been realized via rank-1 updating as known from quasi-Newton methods.     

Spectrally arbitrary ray patterns

An n×n ray pattern A is said to be spectrally arbitrary if for every monic nth degree polynomial f(x) with coefficients from C, there is a matrix in the pattern class of A such that its characteristic polynomial is f(x). In this article the authors extend the nilpotent-Jacobi method for sign patterns to ray patterns, establishing a means to show that an irreducible ray pattern and all its superpatterns are spectrally arbitrary. They use this method to establish that a particular family of n×n irreducible ray patterns with exactly 3n nonzeros is spectrally arbitrary. They then show that every n×n irreducible, spectrally arbitrary ray pattern has at least 3n-1 nonzeros.     

Generalized moments of additive functions

Elliott's generalization of the Turán-Kubilius inequality is further generalized by establishing an upper bound for the sum Σ_n≤xF(∣f(n) ? A∣), where f is a complex-valued additive arithmetical function, A an arbitrary number and F an arbitrary nonnegative-valued increasing function. A connected problem for group-valued functions is also considered.     

Upper and lower bounds on norms of functions of matrices

Given an n by n matrix A, we look for a set S in the complex plane and positive scalars m and M such that for all functions p bounded and analytic on S and throughout a neighborhood of each eigenvalue of A, the inequalities

m·inf{‖f‖_L^∞(S):f(A)=p(A)}?‖p(A)‖?M·inf{‖f‖_L^∞(S):f(A)=p(A)}     

Unary operations with long pre-periods

It is well known that the congruence lattice ConA of an algebra A is uniquely determined by the unary polynomial operations of A (see e.g. [K. Denecke, S.L. Wismath, Universal Algebra and Applications in Theoretical Computer Science, Chapman & Hall, CRC Press, Boca Raton, London, New York, Washington DC, 2002 [2]]). Let A be a finite algebra with |A|=n. If Imf=A or |Imf|=1 for every unary polynomial operation f of A, then A is called a permutation algebra. Permutation algebras play an important role in tame congruence theory [D. Hobby, R. McKenzie, The structure of finite algebras, Contemporary Mathematics, vol. 76, Providence, Rhode Island, 1988 [3]]. If f:A→A is not a permutation then A⊃Imf and there is a least natural number λ(f) with Imf^λ(f)=Imf^λ(f)+1. We consider unary operations with λ(f)=n-1 for n?2 and λ(f)=n-2 for n?3 and look for equivalence relations on A which are invariant with respect to such unary operations. As application we show that every finite group which has a unary polynomial operation with one of these properties is simple or has only normal subgroups of index 2.     

Points of Weak-Norm Continuity in the Unit Ball of Banach Spaces

Using the M-structure theory, we show that several classical function spaces and spaces of operators on them fail to have points of weak-norm continuity for the identity map on the unit ball. This gives a unified approach to several results in the literature that establish the failure of strong geometric structure in the unit ball of classical function spaces. Spaces covered by our result include the Bloch spaces, dual of the Bergman space L¹_a and spaces of operators on them, as well as the space C(T)/A, where A is the disc algebra on the unit circle T. For any unit vector f in an infinite-dimensional function algebra A we explicitly construct a sequence {f_n} in the unit ball of A that converges weakly to f but not in the norm.     

An algorithm for computing the hull of the solution set of interval linear equations

Described is a not-a-priori-exponential algorithm which for each n×n interval matrix A and for each interval n-vector in a finite number of steps either computes the interval hull of the solution set of the system of interval linear equations Ax=b, or finds a singular matrix S∈A.     

Comparison of the best uniform approximations of analytic functions in the disk and on its boundary

Denote by C _A the set of functions that are analytic in the disk |z| < 1 and continuous on its closure |z| ≤ 1; let ? _n , n = 0, 1, 2, ..., be the set of rational functions of degree at most n. Denote by R _n (f) (R _n (f) _A ) the best uniform approximation of a function f ∈ C _A on the circle |z| = 1 (in the disk |z| ≤ 1) by the set ? _n . The following equality is proved for any n ≥ 1: sup{R _n (f) _A /R _n (f): f ∈ C _A ? ? _n } = 2. We also consider a similar problem of comparing the best approximations of functions in C _A by polynomials and trigonometric polynomials.     

Minimisation of functions of a positive semidefinite matrix A subject to AX = 0

A common problem in multivariate analysis is that of minimising or maximising a function f of a positive semidefinite matrix A subject possibly to AX = 0. Typically A is a variance-covariance matrix. Using the theory of nearest point projections in Hilbert spaces, it is shown that the solution satisfies the equation f′(A) + M ? A = 0, where A = P₀(M) and P₀ is a certain projection operator.     

A posteriori error estimate for computing tr(f(A)) by using the Lanczos method

An outstanding problem when computing a function of a matrix, f(A), by using a Krylov method is to accurately estimate errors when convergence is slow. Apart from the case of the exponential function that has been extensively studied in the past, there are no well‐established solutions to the problem. Often, the quantity of interest in applications is not the matrix f(A) itself but rather the matrix–vector products or bilinear forms. When the computation related to f(A) is a building block of a larger problem (e.g., approximately computing its trace), a consequence of the lack of reliable error estimates is that the accuracy of the computed result is unknown. In this paper, we consider the problem of computing tr(f(A)) for a symmetric positive‐definite matrix A by using the Lanczos method and make two contributions: (a) an error estimate for the bilinear form associated with f(A) and (b) an error estimate for the trace of f(A). We demonstrate the practical usefulness of these estimates for large matrices and, in particular, show that the trace error estimate is indicative of the number of accurate digits. As an application, we compute the log determinant of a covariance matrix in Gaussian process analysis and underline the importance of error tolerance as a stopping criterion as a means of bounding the number of Lanczos steps to achieve a desired accuracy.     

Matrix Bounds on the Spectral Condition Number

The purpose of this paper is to obtain some new lower and upper bounds on κ(A)+κ^-1(A), where κ(A) is the spectral condition number of an n×n nonsingular matrix A, and compare these with previously known bounds.     

A combinatorial problem involving graphs and matrices

In this paper we discuss a combinatorial problem involving graphs and matrices. Our problem is a matrix analogue of the classical problem of finding a system of distinct representatives (transversal) of a family of sets and relates closely to an extremal problem involving 1-factors and a long standing conjecture in the dimension theory of partially ordered sets. For an integer n ?1, let n denote the n element set {1,2,3,…, n}. Then let A be a k×t matrix. We say that A satisfies property P(n, k) when the following condition is satisfied: For every k-taple (x₁,x₂,…,x_k?n^k there exist k distinct integers j₁,j₂,…,j_k so that x_i= a_ii for i= 1,2,…,k. The minimum value of t for which there exists a k × t matrix A satisfying property P(n,k) is denoted by f(n,k). For each k?1 and n sufficiently large, we give an explicit formula for f(n, k): for each n?1 and k sufficiently large, we use probabilistic methods to provide inequalities for f(n,k).     

Practical computation of matrix functions

Several new representations for an analytic function f(A) of a complex matrix A, and in particular for e^At and A^t, are derived, which also are numerically useful in that they avoid the computation of eigenvalues of A.     

Asymptotic estimates of sums involving the Moebius function

Let p(n) denote the smallest prime factor of an integer n>1 and let p(1)=∞. We study the asymptotic behavior of the sum M(x,y)=Σ_{1≤n≤x,p(n)>y}μ(n) and use this to estimate the size of A(x)=max_|f|≤1|Σ_2≤n<xμ(n)f(p(n))|, where μ(n) is the Moebius function. Applications of bounds for A(x), M(x,y) and similar quantities are discussed.