Is there a name for this type of matrix? (Reference Request) - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T20:45:51Z http://mathoverflow.net/feeds/question/71024 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/71024/is-there-a-name-for-this-type-of-matrix-reference-request Is there a name for this type of matrix? (Reference Request) Jeremy West 2011-07-22T22:02:28Z 2011-07-26T19:14:48Z <p>I am working on a problem were I encounter matrices of the form</p> <p>$X = \begin{bmatrix}\frac{1}{1 - a_ib_j}\end{bmatrix}_{ij}$</p> <p>I am aware of Cauchy matrices, which have the form</p> <p>$X = \begin{bmatrix}\frac{1}{a_i - b_j}\end{bmatrix}_{ij}$</p> <p>(sometimes written with a plus rather than a minus). Many of the results I need I can actually obtain by factoring the above matrix as a product of a diagonal matrix with a Cauchy matrix (assuming the $a_i \neq 0$), as in:</p> <p>$X = \mathbb{diag}(a_i^{-1})\begin{bmatrix}\frac{1}{a_i^{-1} - b_j}\end{bmatrix}.$</p> <p>These matrices arise when computing solutions to matrix equations of the form</p> <p>$X - AXB^T = C$</p> <p>which are discrete-time analogs of Sylvester equations:</p> <p>$AX + XB = C.$</p> <p>(Also, related are Lyapunov equations and algebraic Riccati equations). It seems that these must appear in the literature somewhere, but I haven't been able to find them. My question is:</p> <blockquote> <ol> <li><p>Do matrices of the form $X = \begin{bmatrix}\frac{1}{1 - a_ib_j}\end{bmatrix}_{ij}$ have a name in the literature?</p></li> <li><p>Is anyone aware of good references for general results on these matrices? For example, there are general results on the determinant and inverses of Cauchy matrices.</p></li> </ol> </blockquote> <p>As I mentioned, I have already found a determinant formula and a formula for the inverse of the matrix using the factorization I mentioned above. But it would be helpful to know of further results if they exist and I would like to properly cite the literature as well.</p> http://mathoverflow.net/questions/71024/is-there-a-name-for-this-type-of-matrix-reference-request/71030#71030 Answer by S. Sra for Is there a name for this type of matrix? (Reference Request) S. Sra 2011-07-22T23:13:37Z 2011-07-22T23:13:37Z <p>Not an answer, but some comments and a suggestion.</p> <p>The place I have previously seen $(1-a_ib_j)^{-1}$ is in Theorem~7.12.1 in <em>Enumerative Combinatorics</em> volume 2, by R. Stanley, where he mentions Cauchy's identity that describes $\prod_{ij}(1-a_ib_j)^{-1}$ as a sum of Schur functions.</p> <p>In the notes to Chapter 7, Stanley mentions other connections of the above matrix to Cauchy's work, where he mentions for example the nice formula:</p> <p>$$\textrm{det}(A) = \frac{V(a)V(b)}{\prod_{ij}(1-a_ib_j)},$$</p> <p>where $V(a)$ is the Vandermonde determinant. </p> <p><strong>Suggestion:</strong> In light of the abovementioned connections, I think it would not be wrong to call your matrix $A$ a (product form) <em>Cauchy matrix</em>.</p> http://mathoverflow.net/questions/71024/is-there-a-name-for-this-type-of-matrix-reference-request/71064#71064 Answer by Federico Poloni for Is there a name for this type of matrix? (Reference Request) Federico Poloni 2011-07-23T12:48:06Z 2011-07-23T12:48:06Z <p>Given two diagonal matrices $D_1,D_2$, matrices such that $\nabla(X):=D_1X-XD_2$ is low-rank are known in literature as <em>Cauchy-like</em> matrices. This includes your case, as $\operatorname{diag}(a_i^{-1})X-X\operatorname{diag}(b_j)$ is rank 1, assuming $a\neq 0$ as you did.</p> <p>Cauchy-like matrices with <em>displacement rank</em> (i.e., $\operatorname{rk} \nabla(X)$) equals to 1 are basically Cauchy matrices diagonally scaled from both sides, as you realized in your case, and the formulas for determinant and inverse can be adapted with little effort.</p> <p>Linear systems with all displacement rank-structured matrices, including Toeplitz, Vandermonde, and Hankel, can be solved using the GKO algorithm (Gohberg-Kailath-Olshevsky, '95). </p> <p>On related subjects, there are a book by Kailath and Sayed, "fast reliable algorithms for matrices with structure" and an old book by Heinig and Rost, but in many cases you may be better off reading directly the papers.</p> <p>Shameless self-plug: if you are interested in solving linear systems with this kind of matrices, you may also like two recent papers on the subject, one by Aricò and Rodriguez and one by myself, appeared on Numer. Algo. less than one year ago.</p>