Toeplitz matrices with banded inverses

Given a Toeplitz matrix T with banded inverse [i.e., (T^?1)_ij=0 for j?i>p], we show that the elements of T can be expressed in terms of the roots of a polynomial. Then, using properties we have previously established, we generalize this result appropriately to allow singular T and show that the converse also holds. Finally, we give a sufficient condition for the decay of the elements of T as one moves away from the diagonal.     

Band matrices with Toeplitz inverses

It is shown that a square band matrix H=(h_ij) with h_ij=0 for j? i>r and i?j>s, where r+s is less than the order of the matrix, has a Toeplitz inverse if and only if it has a special structure characterized by two polynomials of degrees r and s, respectively.     

On the evaluation of the Eigenvalues of a banded toeplitz block matrix

Let A = (a_ij) be an n × n Toeplitz matrix with bandwidth k + 1, K = r + s, that is, a_ij = a_j−i, i, J = 1,… ,n, a_i = 0 if i > s and if i < -r. We compute p(λ)= det(A - λI), as well as p(λ)/p′(λ), where p′(λ) is the first derivative of p(λ), by using O(k log k log n) arithmetic operations. Moreover, if a_i are m × m matrices, so that A is a banded Toeplitz block matrix, then we compute p(λ), as well as p(λ)/p′(λ), by using O(m³k(log² k + log n) + m²k log k log n) arithmetic operations. The algorithms can be extended to the computation of det(A − λB) and of its first derivative, where both A and B are banded Toeplitz matrices. The algorithms may be used as a basis for iterative solution of the eigenvalue problem for the matrix A and of the generalized eigenvalue problem for A and B.     

Anti-Hadamard matrices

An anti-Hadamard matrix may be loosely defined as a real (0, 1) matrix which is invertible, but only just. Let A be an invertible (0, 1) matrix with eigenvalues λ_i, singular values σ_i, and inverse B = (b_ij). We are interested in the four closely related problems of finding λ(n) = min_{A, i}|λ_i|, σ(n) = min_{A, i}σ_i, χ(n) = max_{A, i, j} |b_ij|, and μ(n) = max_AΣ_ijb²_ij. Then A is an anti-Hadamard matrix if it attains μ(n). We show that λ(n), σ(n) are between $\text{(2n)}{}^{\mathrm{?1}}\text{(}\text{n}\text{4}\text{)}{}^{\mathrm{<mtext>?n</mtext><mtext>2</mtext>}}$ and c√n (2.274)^?n, where c is a constant, $\text{c}\text{(2.274)}{}^{\mathrm{n}}\text{?χ(n)?2(}\text{n}\text{4}\text{)}{}^{\mathrm{<mtext>n</mtext><mtext>2</mtext>}}$, and $\text{c}\text{(5.172)}{}^{\mathrm{n}}\text{?μ(n)?4n}{}^2\text{(}\text{n}\text{4}\text{)}{}^{\mathrm{n}}$. We also consider these problems when A is restricted to be a Toeplitz, triangular, circulant, or (+1, ?1) matrix. Besides the obvious application—to finding the most ill-conditioned (0, 1) matrices—there are connections with weighing designs, number theory, and geometry.     

On constant discrete programming problems

Let H be a subset of the set S_n of all permutations

$\text{1}\text{2}\text{???}\text{n}\text{s(1)}\text{s(2)}\text{???}\text{s(n)}$

C=6c_ij6 a real n?n matrix L_c(s)=c_1s(1)+c_2s(2)+???+c_ns(n) for s ? H. A pair (H, C) is the existencee of reals a₁,b₁,a₂,b₂,…a_n,b_n, for which c_ij=a₁+b_j if (i,j)?D(H), where D(H)={(i,j):(?h?H)(j=h(i))}.For a pair (H,C) the specifity of it is proved in the case, when H is either a special cyclic class of permutations or a special union of cyclic classes. Specific pairs with minimal sets H are in some sense described.     

On the solutions to x′(t) = A(t) x (t) over all A(t), where P ⩽ A(t) ⩽ Q

Let P_ij and q_ij be positive numbers for i ≠ j, i, j = 1, …, n, and consider the set of matrix differential equations x′(t) = A(t) x(t) over all A(t), where a_ij(t) is piecewise continuous, a_ij(t) = ?∑_{i ≠ j}a_ij(t), and p_ij ? a_ij(t) ? q_ij all t. A solution x is also to satisfy ∑_{i = 1}ⁿx_i(0) = 1. Let C_t denote the set of all solutions, evaluated at t to equations described above. It is shown that $\text{C}{}_{\mathrm{t}}$, the topological closure of C_t, is a compact convex set for each t. Further, the set valued function $\text{C}{}_{\mathrm{t}}$, of t is continuous and $\text{limit}{}_{\mathrm{t\; \to \; \infty }}\text{C}\text{?}{}_{\mathrm{t}}\text{= ∩}\text{C}\text{?}{}_{\mathrm{t}}$.     

On a Conjecture of E. Dittert

Let K_n denote the set of all n X n nonnegative matrices whose entries have sum n, and let φ be a real valued function defined on K_n by φ(X) = π_iⁿ⁼¹ n, + π_j=1^c_j⁻ⁿ per X for X E K_n with row sum vector (r₁,…, r_n) and column sum vector (c_l,hellip;, c_n). For the same X, let φ_ij(X)= π_k≠ir_k + π_1≠jc₁ - per X(i| j). A ϵK_n is called a φ-maximizing matrix if φ(A) > φ(X) for all X ϵ K_n. Dittert's conjecture asserts that J_n = [1/n]_n×n is the unique (φ-maximizing matrix on K_n. In this paper, the following are proved: (i) If A = [a_ij] is a φ-maximizing matrix on K_n then φ_ij(A) = φ (A) if a_ij > 0, and φ_ij (A) ⩽ φ (A)if aij = 0. (ii) The conjecture is true for n = 3.     

A direct method to solve block banded block Toeplitz systems with non-banded Toeplitz blocks

A fast solution algorithm is proposed for solving block banded block Toeplitz systems with non-banded Toeplitz blocks. The algorithm constructs the circulant transformation of a given Toeplitz system and then by means of the Sherman-Morrison-Woodbury formula transforms its inverse to an inverse of the original matrix. The block circulant matrix with Toeplitz blocks is converted to a block diagonal matrix with Toeplitz blocks, and the resulting Toeplitz systems are solved by means of a fast Toeplitz solver.The computational complexity in the case one uses fast Toeplitz solvers is equal to ξ(m,n,k)=O(mn³)+O(k³n³) flops, there are m block rows and m block columns in the matrix, n is the order of blocks, 2k+1 is the bandwidth. The validity of the approach is illustrated by numerical experiments.     

On conjugate characteristic polynomial of a graph

Let $c=a+b\sqrt{m}$ and $\overline{c}=a-b\sqrt{m}$ , where a and b are two nonzero integers and m is a positive integer such that m is not a perfect square. We say that A ^c =[c _ij ] is the conjugate adjacency matrix of a graph G if c _ij =c for any two adjacent vertices i and j, $c_{ij}=\overline{c}$ for any two nonadjacent vertices i and j, and c _ij =0 if i=j. Let P _G ^c (λ)=|λ I?A ^c | denote the conjugate characteristic polynomial of G. Further, let e=e(G) and Δ=Δ(G) be the number of edges and number of triangles of G, respectively. Let G and H be two graphs of order n and let e(G)=e(H). In this work we prove that c ₃(G)=c ₃(H) if and only if Δ(G)=Δ(H) and $\Delta(\overline{G})=\Delta(\overline{H})$ , where $\overline{G}$ denotes the complement of G and c _k is the coefficient which corresponds to λ ^n?k with respect to P _G ^c (λ). Besides, we here give the conjugate spectrum and conjugate characteristic polynomial of all connected graphs of order n=2,3,4,5, with respect to the constant $c=1+\sqrt{2}$ .     

Extensions of band matrices with band inverses

Let R_ij be a given set of μ_i× μ_j matrices for i, j=1,…, n and |i?j| ?m, where 0?m?n?1. Necessary and sufficient conditions are established for the existence and uniqueness of an invertible block matrix =[F_ij], i,j=1,…, n, such that F_ij=R_ij for |i?j|?m, F admits either a left or right block triangular factorization, and (F^?1)_ij=0 for |i?j|>m. The well-known conditions for an invertible block matrix to admit a block triangular factorization emerge for the particular choice m=n?1. The special case in which the given R_ij are positive definite (in an appropriate sense) is explored in detail, and an inequality which corresponds to Burg's maximal entropy inequality in the theory of covariance extension is deduced. The block Toeplitz case is also studied.     

Sequences of orthogonal vectors with a fixed norm

Let A = (a_ij) be an n × m matrix with a_ij ∈ K, a field of characteristic not 2, where Σ_i=1ⁿa_ij² = e, 1 ≤ j ≤ m, and Σ_i=1ⁿa_ija_ij′ = 0 for j ≠ j′. The question then is when is it possible to extend A, by adding columns, to obtain a matrix with orthogonal columns of the same norm. The question is answered for n ? 7 ≤ m ≤ n as well as for more general cases. Complete solutions are given for global and local fields, the answer depending on what congruence class modulo 4 n belongs to and how few squares are needed to sum to e.     

Möbius Isoparametric Hypersurfaces in S n+1 with Two Distinct Principal Curvatures

A hypersurface x : M → S ⁿ⁺¹ without umbilic point is called a Möbius isoparametric hypersurface if its Möbius form Φ = ?ρ ^?2∑ _i (e _i (H) + ∑ _j (h _ij ?Hδ _ij )e _j (log ρ))θ _i vanishes and its Möbius shape operator $ {\Bbb {S}}A hypersurface x : M → S ^{n +1} without umbilic point is called a M?bius isoparametric hypersurface if its M?bius form Φ = −ρ⁻²∑ _i (e _i (H) + ∑ _j (h _ij −Hδ _ij )e _j (log ρ))θ _i vanishes and its M?bius shape operator ? = ρ⁻¹(S−Hid) has constant eigenvalues. Here {e _i } is a local orthonormal basis for I = dx·dx with dual basis {θ _i }, II = ∑ _ij h _ij θ _i ⊗θ _i is the second fundamental form, and S is the shape operator of x. It is clear that any conformal image of a (Euclidean) isoparametric hypersurface in S ^{n +1} is a M?bius isoparametric hypersurface, but the converse is not true. In this paper we classify all M?bius isoparametric hypersurfaces in S ^{n +1} with two distinct principal curvatures up to M?bius transformations. By using a theorem of Thorbergsson [1] we also show that the number of distinct principal curvatures of a compact M?bius isoparametric hypersurface embedded in S ^{n +1} can take only the values 2, 3, 4, 6. Received September 7, 2001, Accepted January 30, 2002     

Effective Fast Algorithms for Polynomial Spectral Factorization

Let p(z) be a polynomial of degree n having zeros |ξ₁|≤???≤|ξ _m |<1<|ξ _m+1|≤???≤|ξ _n |. This paper is concerned with the problem of efficiently computing the coefficients of the factors u(z)=∏ _i=1 ^m (z?ξ _i ) and l(z)=∏ _i=m+1 ⁿ (z?ξ _i ) of p(z) such that a(z)=z ^?m p(z)=(z ^?m u(z))l(z) is the spectral factorization of a(z). To perform this task the following two-stage approach is considered: first we approximate the central coefficients x _?n+1,. . .x _n?1 of the Laurent series x(z)=∑ _i=?∞ ^+∞ x _i z ⁱ satisfying x(z)a(z)=1; then we determine the entries in the first column and in the first row of the inverse of the Toeplitz matrix T=(x _i?j ) _i,j=?n+1,n?1 which provide the sought coefficients of u(z) and l(z). Two different algorithms are analyzed for the reciprocation of Laurent polynomials. One algorithm makes use of Graeffe's iteration which is quadratically convergent. Differently, the second algorithm directly employs evaluation/interpolation techniques at the roots of 1 and it is linearly convergent only. Algorithmic issues and numerical experiments are discussed.     

On Ochoa's special matrices in matrix classes

It is well known that the ideal classes of an order Z[μ], generated over Z by the integral algebraic number μ, are in a bijective correspondence with certain matrix classes, that is, classes of unimodularly equivalent matrices with rational integer coefficients. If the degree of μ is ?3, we construct explicitly a particularly simple ideal matrix for an ideal which is a product of different prime ideals of degree 1. We obtain the following special n×n matrix (c_ij) in the matrix class corresponding to the ideal class of our ideal: c_i+1,_i=1(i=1,…,n?2); c_ij=0(?i?n, 1?j?n? 2, and i≠j+1); c_nj=0(j)=2,…,n?1). The remaining coefficients are given as explicit polynomials in an integer z which depends on the ideal. It is shown that the matrix class of every regular ideal class of Z[μ] contains a special matrix of this kind.     

Alexandrov’s inequality and conjectures on some Toeplitz matrices

We study determinant inequalities for certain Toeplitz-like matrices over C. For fixed n and N ? 1, let Q be the n × (n + N − 1) zero-one Toeplitz matrix with Q_ij = 1 for 0 ? j − i ? N − 1 and Q_ij = 0 otherwise. We prove that det(QQ^∗) is the minimum of det(RR^∗) over all complex matrices R with the same dimensions as Q satisfying ∣R_ij∣ ? 1 whenever Q_ij = 1 and R_ij = 0 otherwise. Although R has a Toeplitz-like band structure, it is not required to be actually Toeplitz. Our proof involves Alexandrov’s inequality for polarized determinants and its generalizations. This problem is motivated by Littlewood’s conjecture on the minimum 1-norm of N-term exponential sums on the unit circle. We also discuss polarized Bazin-Reiss-Picquet identities, some connections with k-tree enumeration, and analogous conjectured inequalities for the elementary symmetric functions of QQ^∗.     

Powers of cyclotomic integers and difference sets

Let p be an odd prime, $\text{ζ =}\text{rxp}\text{(}\text{2πi}\text{p}\text{)}$, D a difference set mod p having a nontrivial multiplier, and ν = H(ζ), where H(x) is the Hall polynomial of D. For any α = Σ_i=0^p?1a_iζⁱ with rational a_i denote δ(α) = max ∥ a_i ? a_j ∥. Assuming that there are no nontrivial multiplicative dependence relations among the conjugates of ν, we obtain results for

. We then show that for most known families of difference sets mod p the required independence result is valid. A conjecture concerning the exact value of the first number is stated. The conjecture is confirmed in certain particular cases.     

The method of asymptotic stabilization to a given trajectory based on a correction of the initial data

Let S be an operator in a Banach space H and S ⁱ (u) (i = 0, 1, ..., u ∈ H) be the evolutionary process specified by S. The following problem is considered: for a given point z ₀ and a given initial condition a ₀, find a correction l such that the trajectory {S ⁱ (a ₀ + l)} approaches }S ⁱ (z ₀)} for 0 < i ≤ n. This problem is reduced to projecting a ₀ on the manifold ?^?(z ₀, f ⁽ⁿ⁾) defined in a neighborhood of z ₀ and specified by a certain function f ⁽ⁿ⁾. In this paper, an iterative method is proposed for the construction of the desired correction u = a ₀ + l. The convergence of the method is substantiated, and its efficiency for the blow-up Chafee-Infante equation is verified. A constructive proof of the existence of a locally stable manifold ?^?(z ₀, f) in a neighborhood of a trajectory of hyperbolic type is one of the possible applications of the proposed method. For the points in ?^?(z ₀, f), the value of n can be chosen arbitrarily large.     

Generalizations of theorems of Lyapunov and Stein

The matrix equation $\text{f}{}_{\mathrm{H}}\text{(A)=∑C}{}_{\mathrm{ij}}\text{A}{}^{\mathrm{1i}}\text{HA}{}^{\mathrm{j}}\text{=W, H >0}$, W ?0, is studied. In the case A¹H+HA = W[H?A¹HA = W], the controllability matrix of (A¹,W) is used to determine the number of eigenvalues of A on the imaginary axis [on the unit circle]. As an application a result of Pták on the critical exponent of the spectral norm is obtained. Estimates for the eigenvalues of A satisfying f_H(A) = M are given.