The Toeplitz-likeness of a matrix(Kailath et al. 1979) is the generalization of the notion that a matrix is Toeplitz. Block matrices with Toeplitz blocks, such as the Sylvester matrix corresponding to the resultant of two univariate polynomials, are Toeplitz-like, as are products and inverses of Toeplitz-like matrices. The displacement rank of a matrix is a measure for the degree of being Toeplitz-like. For example, an rxs block matrix with Toeplitz blocks has displacement rank r+ s whereas a generic IV x IV matrix has displacement rank IV. A matrix of displacement rank a can be implicitly represented by a sum of a matrices, each of which is the product of a lower triangular and an upper triangular Toeplitz matrices. Such a XLU representation can usually be obtained efficiently.

We consider the problem of computing a solution to a possibly singular linear system Az= b with coefficients in an arbitrary field, where A is an IV x IV matrix of displacement rank a given in ZLU representation. By use of randomization we show that if the system is solvable we can find a vector that is uniformly sampled from the solution manifold in 0 (cr21V (log iV) 2 loglog lV) expected arithmetic operations in the field of entries. In case no solution exists, this fact is discovered by our algorithm. In asymptotically the same time we can also compute the rank of A and the determinant of a non-singular A. Toeplitz and Toeplitz-like matrices and the corresponding linear systems are ubiquitous in control theory, of course, but also in symbolic computation. Examples