# DETERMINISTIC INVERSION OF SOME MATRICES WITH DISPLACEMENT STRUCTURE

CLAUDE-PIERRE JEANNEROD*

**Abstract.** We consider the problem of inverting an $n \times n$ matrix with displacement rank $\alpha$, and describe in particular a very simple way to reduce Toeplitz-like/Hankel-like inversion to block-Toeplitz/block-Hankel inversion in time $\tilde{O}(\alpha^{\omega-1}n)$, where $\omega$ is an exponent for dense, unstructured matrix multiplication. This makes it possible to perform deterministically and in the same amount of time the inversion of any of the displacement-structured matrices from [1].

**1. Introduction.** We consider the problem $\text{inv}(\mathcal{L}, \alpha)$ from [1], that is as follows: given an $\mathcal{L}$-generator $(G, H)$ of length $\alpha \le n$ for $A \in \mathbb{K}^{n \times n}$, return an $\mathcal{L}'$-generator $(G', H')$ of length at most $\alpha$ for $A^{-1}$, or assert that $A$ is not invertible.

Here $\mathbb{K}$ is a field, $\mathcal{L}$ denotes a displacement operator of the form $\nabla_{M,N}: A \mapsto MA - AN$ or $\Delta_{M,N}: A \mapsto A - MAN$ for some fixed $M, N \in \mathbb{K}^{n \times n}$, and $\mathcal{L}'$ is such that $\mathcal{L}' = \nabla_{M,N}$ if $\mathcal{L} = \nabla_{M,N}$, and $\mathcal{L}' = \Delta_{M,N}$ if $\mathcal{L} = \Delta_{M,N}$. The values of $M$ and $N$ considered in [1] are parameterized by some families of polynomials that allow to cover in a uniform way various classical structures for $A$, such as Toeplitz/Hankel-like, Vandermonde-like, and Cauchy-like structures. For an invertible displacement operator $\mathcal{L}$ and a positive integer $\alpha$, an $\mathcal{L}$-generator of length $\alpha$ for $A \in \mathbb{K}^{n \times n}$ is a matrix pair $(G, H)$ such that $G, H \in \mathbb{K}^{n \times \alpha}$ and $\mathcal{L}(A) = GH^T$.

Let $\mathcal{C}_{\text{inv}}(\mathcal{L}, \alpha)$ be such that the problem $\text{inv}(\mathcal{L}, \alpha)$ can be solved using $\mathcal{C}_{\text{inv}}(\mathcal{L}, \alpha)$ arithmetic operations in $\mathbb{K}$. Let also $\omega$ be such that two $n \times n$ matrices over $\mathbb{K}$ can be multiplied using $O(n^\omega)$ arithmetic operations in $\mathbb{K}$, and let $f(n)$ denote any function in $\tilde{O}(n)$. The bounds on $\mathcal{C}_{\text{inv}}(\mathcal{L}, \alpha)$ established in [1], that are all of the form $O(\alpha^{\omega-1}f(n)) \subseteq \tilde{O}(\alpha^{\omega-1}n)$, were obtained in two main steps:

* A deterministic reduction from $\mathcal{L}$ to the Hankel operator $\nabla_{\mathbb{Z}_{n,0}, \mathbb{Z}_{n,1}^T}$, where $\mathbb{Z}_{n,\varphi}$ denotes the cyclic down-shift matrix, leading to the cost bound

$$ \mathcal{C}_{\text{inv}}(\mathcal{L}, \alpha) \le \mathcal{C}_{\text{inv}}(\nabla_{\mathbb{Z}_{n,0}, \mathbb{Z}_{n,1}^T}, \alpha + 2) + O(\alpha f(n) + \alpha^{\omega-1}n). $$

* A probabilistic (Las Vegas) algorithm for solving $\text{inv}(\nabla_{\mathbb{Z}_{n,0}, \mathbb{Z}_{n,1}^T}, \alpha)$, whose associated cost is

$$ \mathcal{C}_{\text{inv}}(\nabla_{\mathbb{Z}_{n,0}, \mathbb{Z}_{n,1}^T}, \alpha) = O(\alpha^{\omega-1} f(n)). $$

More precisely, when the algorithm in the second step does not return 'failure' then it returns correctly either 'A is singular' or the pair $(-A^{-1}G, A^{-T}H)$, which is a $\nabla_{\mathbb{Z}_{n,1}^T, \mathbb{Z}_{n,0}}$-generator of length $\alpha$ for $A^{-1}$.

As an application, this probabilistic inversion algorithm can be combined with the deterministic multiplication algorithm of [1] to deduce, when $A$ is invertible and given by $(G, H)$ and when $B$ is any $n \times \beta$ matrix with $\beta = O(\alpha)$, quantities such as $A^{-1}B$ and $A^{-T}B$ in time $\tilde{O}(\alpha^{\omega-1}n)$.

In what follows, we give a very simple way to derandomize the above $\tilde{O}(\alpha^{\omega-1}n)$ solution to $\text{inv}(\nabla_{\mathbb{Z}_{n,0}, \mathbb{Z}_{n,1}^T}, \alpha)$. All we need is the ability to recover $AB$ and $A^T B$ from $(G, H, B)$ in time $\tilde{O}(\alpha n)$ when $B$ has $O(1)$ columns, and in time $\tilde{O}(\alpha^{\omega-1}n)$ when $B$ has $O(\alpha)$ columns, as done in [1]. This makes it possible to reduce to block Hankel matrix inversion, for which a deterministic cost bound $\tilde{O}(\alpha^{\omega-1}n)$ is known [2].

<footnote>* Inria, Univ. Lyon, CNRS, ENS de Lyon, UCBL - LIP UMR 5668, Lyon, France - claude-pierre.jeannerod@inria.fr - December 30, 2025.</footnote>
This note is only about the inversion problem for a structured matrix $A \in \mathbb{K}^{n \times n}$, and its application to computing $A^{-1}B$ and $A^{-T}B$. For the linear system solving problem, that is, finding a solution $x$ to $Ax = b$ with $A \in \mathbb{K}^{n \times m}$ or asserting that no such $x$ exists, a deterministic cost bound $\tilde{O}(\alpha^{\omega-1} \max(n, m))$ is also possible [4, 5].

**2. Preliminary reductions.** For convenience, we start with a basic reduction (see for example [7]) from the Hankel-like Sylvester operator $\nabla_{Z_{n,0}, Z_{n,1}^T}$ to the Toeplitz-like Stein operator $\Delta_{Z_{n,0}, Z_{n,0}^T}$. Since $Z_{n,1}^T = Z_{n,1}^{-1} = J_n Z_{n,1} J_n$ with $J_n$ the $n \times n$ reversal matrix (with ones on the antidiagonal and zeros elsewhere), multiplying both sides of

$$ \nabla_{Z_{n,0}, Z_{n,1}^T}(A) = GH^T $$

on the right by $-Z_{n,1}$ leads to $\Delta_{Z_{n,0}, Z_{n,1}}(A) = RS^T$, where $R := -G$ and $S := Z_{n,1}^T H$ can be deduced from $G$ and $H$ in time $O(\alpha n)$. Then, multiplying both sides of $\Delta_{Z_{n,0}, Z_{n,1}}(A) = RS^T$ on the right by $J_n$ and using the fact that $J_n^2$ is the $n \times n$ identity matrix $I_n$, we obtain $A J_n - Z_{n,0} \cdot A J_n \cdot J_n Z_{n,1} J_n = R(J_n S)^T$. Recalling that $J_n Z_{n,1} J_n = Z_{n,1}^T$ and since $Z_{n,1}^T = Z_{n,0}^T + e_{n,n} e_{n,1}^T$ with $e_{n,i}$ the $i$th unit vector in dimension $n$, we arrive at $A J_n - Z_{n,0} \cdot A J_n \cdot Z_{n,0}^T = UV^T$, where $U := [R | Z_{n,0} A e_{n,1}]$ and $V := [J_n S | e_{n,1}]^T$ are in $\mathbb{K}^{n \times (\alpha+1)}$ and can be deduced from $G, H, R, S$ in time $\tilde{O}(\alpha n)$, in particular by reconstructing the first column of $A$. To summarize,

$$ \Delta_{Z_{n,0}, Z_{n,0}^T}(\tilde{A}) = \tilde{G} \tilde{H}^T, \quad \tilde{A} := A J_n, \quad \tilde{G} := [-G | Z_{n,0} A e_{n,1}], \quad \tilde{H} := [Z_{n,1} J_n H | e_{n,1}], $$

and the $n \times (\alpha + 1)$ matrices $\tilde{G}$ and $\tilde{H}$ can be deduced from $G$ and $H$ in time $\tilde{O}(\alpha n)$. Hence, $A$ is invertible iff $\tilde{A}$ is invertible, and if $\tilde{A}$ is invertible and one can compute expressions of the form $\tilde{A}^{-1}B$ and $\tilde{A}^{-T}B$ in time $\tilde{O}(\alpha^{\omega-1}n)$ from $G, H, B$, then one can compute $-\tilde{A}^{-1}G$ and $\tilde{A}^{-T}H$ in time $\tilde{O}(\alpha^{\omega-1}n)$ from $G$ and $H$ by taking $B \in \{G, H\}$ and pre-multiplying by $\pm J_n$.

Thus, it now suffices to focus on the following problem $\text{mult inv}(\Delta_{Z_{n,0}, Z_{n,0}^T}, \alpha)$: given a $\Delta_{Z_{n,0}, Z_{n,0}^T}$-generator $(G, H)$ of length $\alpha \le n$ for $A \in \mathbb{K}^{n \times n}$ and given an arbitrary matrix $B \in \mathbb{K}^{n \times O(\alpha)}$, return $(A^{-1}B, A^{-T}B)$, or assert that $A$ is not invertible. We have just seen that

$$ \mathcal{C}_{\text{inv}}(\nabla_{Z_{n,0}, Z_{n,1}^T}, \alpha) \le \mathcal{C}_{\text{mult inv}}(\Delta_{Z_{n,0}, Z_{n,0}^T}, \alpha + 1) + \tilde{O}(\alpha n), $$

and it remains to show that $\text{mult inv}(\Delta_{Z_{n,0}, Z_{n,0}^T}, \alpha)$ can be solved deterministically using $\tilde{O}(\alpha^{\omega-1}n)$ arithmetic operations in $\mathbb{K}$. This will be done in the next sections, assuming $\alpha$ divides $n$ for simplicity.

Our second reduction shows that this assumption can be made with no loss of generality, as follows. If $\Delta_{Z_{n,0}, Z_{n,0}^T}(A) = GH^T$ with $G, H \in \mathbb{K}^{n \times \alpha}$ and $B \in \mathbb{K}^{n \times O(\alpha)}$ with $\alpha$ not dividing $n$, then define the augmented matrix $\tilde{A} = \text{diag}(A, I_m)$ for some integer $m \ge 2$ to be fixed later, and let $\tilde{B} = [B | 0]^T$ be obtained by padding $m$ zero rows. Then $A$ is invertible iff $\tilde{A}$ is invertible; furthermore, if $\tilde{A}$ is invertible then $\tilde{A}^{-1}B$ and $\tilde{A}^{-T}B$ can be read off the first $n$ rows of $\tilde{A}^{-1}B$ and $\tilde{A}^{-T}B$, respectively. Defining $\tilde{n} := n + m$ and using $Z_{\tilde{n},0} = \text{diag}(Z_{n,0}, Z_{m,0}) + e_{\tilde{n},n+1} e_{\tilde{n},n}$, it can be checked that $\tilde{A} - Z_{\tilde{n},0} \tilde{A} Z_{\tilde{n},0}^T$ has rank at most $\alpha := \alpha + 2$ and, furthermore, that a $\Delta_{Z_{\tilde{n},0}, Z_{\tilde{n},0}^T}$-generator $(\tilde{G}, \tilde{H})$ of length $\underline{\alpha} \le \underline{n}$ for $\tilde{A} \in \mathbb{K}^{n \times n}$ can be computed from $(\tilde{G}, \tilde{H})$ in time $\tilde{O}(\alpha n)$, in particular by reconstructing the last row and the last column of $A$. Taking $m := \underline{\alpha}[n/\underline{\alpha}] - n$ ensures that $\underline{\alpha}$ divides $\underline{n}$ and that $\underline{n} < n + \underline{\alpha} + 2 \le 2n + 2$. Hence it will suffice to be able to solve $\text{mult inv}(\Delta_{Z_{\tilde{n},0}, Z_{\tilde{n},0}^T}, \alpha)$ in time $\tilde{O}(\underline{\alpha}^{\omega-1}\underline{n}) \subseteq \tilde{O}(\alpha^{\omega-1}n)$.
**3. Splitting and shuffling.** Let $\alpha, \beta, n$ be three integers such that $n$ is a multiple of $\alpha$ and $\beta = O(\alpha)$. Let also $G, H \in \mathbb{K}^{n \times \alpha}$ and $B \in \mathbb{K}^{n \times \beta}$ be given, and write $A$ to denote the matrix in $\mathbb{K}^{n \times n}$ defined by $\Delta_{\mathbb{Z}_{n,0}, \mathbb{Z}_{n,0}^T}(A) = GH^T$. Here and hereafter, $d := n/\alpha$.

**3.1. Splitting.** We start by splitting the lower shift matrix as $\mathbb{Z}_{n,0} = Z + EF^T$, where

$$Z = \mathbb{I}_{\alpha} \otimes \mathbb{Z}_{d,0}, \quad E = [e_{n,jd+1}]_{1 \le j < \alpha}, \quad F = [e_{n,jd}]_{1 \le j < \alpha}.$$

Here the block-diagonal matrix $Z$ has the block $\mathbb{Z}_{d,0}$ duplicated $\alpha$ times on its diagonal, and $E, F$ are $n \times (\alpha - 1)$ matrices whose rank is $\alpha - 1$ and whose product $EF^T$ contains the 1's from the columns of $\mathbb{Z}_{n,0}$ of index $d, 2d, \dots, (\alpha - 1)d$. Similarly, we split the transpose of $\mathbb{Z}_{n,0}$ as $\mathbb{Z}_{n,0}^T = Z^T + FE^T$, noting that $Z^T = \mathbb{I}_{\alpha} \otimes \mathbb{Z}_{d,0}^T$. It can then be checked that $A - ZAZ^T$ has rank at most $3\alpha$ (in fact, at most $3\alpha - 2$) and that a corresponding generator can be deduced from $(G, H)$ in time $\tilde{O}(\alpha^{\omega^{-1}n})$ via the reconstruction of $\alpha - 1$ rows and $\alpha - 1$ columns of $A$. More precisely, it follows from $Z = \mathbb{Z}_{n,0} - EF^T$ and $A - \mathbb{Z}_{n,0}A\mathbb{Z}_{n,0}^T = GH^T$ that the matrix $A$ satisfies

$$A - ZAZ^T = GH^T + E \cdot F^T A \mathbb{Z}_{n,0}^T + ZAF \cdot E^T \\ = G_1 H_1^T + G_2 H_2^T + G_3 H_3^T,$$

where $G_1 = G, H_1 = H, G_2 = [E|0], H_2 = [\mathbb{Z}_{n,0}^T F|0], G_3 = [ZAF|0],$ and $H_3 = [E|0]$. (We add a zero column at the end of the last four matrices only to ensure for simplicity that the six matrices under consideration all have exactly $\alpha$ columns.) Since $F \in \mathbb{K}^{n \times (\alpha - 1)}$, one can deduce from $(G, H)$ the matrices $A^T F$ and $AF$ in time $\tilde{O}(\alpha^{\omega^{-1}n})$, and then pre-multiply the results by either $\mathbb{Z}_{n,0}$ or $Z$ in time $O(\alpha n)$.

**3.2. Shuffling.** We now transform $Z$ into a block lower-shift matrix by means of a permutation matrix $P := P_{\alpha,d} \in \mathbb{K}^{n \times n}$ (called perfect shuffle permutation [3]) such that $P(\mathbb{I}_{\alpha} \otimes \mathbb{Z}_{d,0})P^{-1} = \mathbb{Z}_{d,0} \otimes \mathbb{I}_{\alpha}$. Writing $\tilde{Z} = \mathbb{Z}_{d,0} \otimes \mathbb{I}_{\alpha}$ to denote this shuffled matrix and defining $\tilde{A} = PAP^{-1}$ and $(\tilde{G}_j, \tilde{H}_j) = (PG_j, PH_j)$ for $j = 1, 2, 3$, it can be checked that

$$\tilde{A} - \tilde{Z}\tilde{A}\tilde{Z}^T = \tilde{G}_1\tilde{H}_1^T + \tilde{G}_2\tilde{H}_2^T + \tilde{G}_3\tilde{H}_3^T.$$

Then, using the fact that $\tilde{Z}^d$ is the zero matrix, we deduce that

$$(1) \qquad \tilde{A} = L_1 U_1 + L_2 U_2 + L_3 U_3,$$

where $L_j$ and $U_j$ are the block lower/upper-triangular Toeplitz matrices (and thus special block Krylov matrices)

$$(2) \qquad L_j = L(\tilde{G}_j) := [\tilde{G}_j | \tilde{Z}\tilde{G}_j | \dots | \tilde{Z}^{d-1}\tilde{G}_j], \quad U_j = L(\tilde{H}_j)^T, \quad j = 1, 2, 3.$$

Each matrix $L_j$ and $U_j$ is $n \times n$ and has a block triangular Toeplitz structure, with blocks of dimensions $\alpha \times \alpha$.

An interpretation of identity (1) might be as follows: up to a perfect shuffling of its rows and columns, the matrix $A$, which is an arbitrary Toeplitz-like matrix of displacement rank $\alpha$, can be seen as a block Toeplitz-like matrix of block-displacement rank $O(1)$; furthermore, an associated generator, namely, $([\tilde{G}_1|\tilde{G}_2|\tilde{G}_3], [\tilde{H}_1|\tilde{H}_2|\tilde{H}_3])$, can be deduced from $(G, H)$ in time $\tilde{O}(\alpha^{\omega^{-1}n})$ by recovering $O(\alpha)$ rows and columns of $A$.

Since $A = P^{-1}\tilde{A}P$, we see that $A$ is invertible iff $\tilde{A}$ is invertible. Furthermore, if $\tilde{A}$ is invertible, then $(A^{-1}B, A^{-T}B) = (P^{-1}\tilde{A}^{-1}B, P^{-1}\tilde{A}^{-T}B)$ with $\tilde{B} := PB$. Since the
matrices B, $\tilde{A}^{-1}\tilde{B}$, and $\tilde{A}^{-T}\tilde{B}$ have dimensions $n \times \beta$ with $\beta = O(\alpha)$, left multiplying them by P or $P^{-1}$ can be done in time $O(\alpha n)$ and so it remains to be able to compute $(\tilde{A}^{-1}\tilde{B}, \tilde{A}^{-T}\tilde{B})$ from $([\tilde{G}_1|\tilde{G}_2|\tilde{G}_3], [\tilde{H}_1|\tilde{H}_2|\tilde{H}_3])$ and $\tilde{B}$ in time $O(\alpha^{\omega-1}n)$. This is the goal of what follows.

**4. Embedding and block shuffling.** We start by associating with the $n \times n$ matrix $\tilde{A}$ from (1) the following $4n \times 4n$ matrix $\tilde{\mathcal{A}}$:

$$ \tilde{\mathcal{A}} = \begin{bmatrix} -\mathbb{I}_{3n} & U \\ \mathbb{L} & \mathbb{L} \end{bmatrix}, \quad \mathbb{L} = [\mathbb{L}_1 | \mathbb{L}_2 | \mathbb{L}_3], \quad U = [\mathbb{U}_1^T | \mathbb{U}_2^T | \mathbb{U}_3^T]^T. $$

The embedded matrices $\mathbb{L}$ and $U$ are defined from the $n \times n$ block triangular Toeplitz matrices $\mathbb{L}_j$ and $U_j$ in (2) and thus have dimensions $n \times 3n$ and $3n \times n$, respectively. Since $\tilde{A} = \mathbb{L}U$, it can be checked that $\tilde{\mathcal{A}}$ admits the following block factorization:

$$ \tilde{\mathcal{A}} = \begin{bmatrix} \mathbb{I}_{3n} & \mathbb{I}_n \\ -\mathbb{L} & \mathbb{I}_n \end{bmatrix} \begin{bmatrix} -\mathbb{I}_{3n} & \mathbb{I}_n \\ \mathbb{A} & \mathbb{U} \end{bmatrix} \begin{bmatrix} \mathbb{I}_{3n} & -\mathbb{U} \\ \mathbb{I}_n & \mathbb{I}_n \end{bmatrix}. $$

Consequently, $\tilde{\mathcal{A}}$ is invertible iff $\tilde{\mathcal{A}}$ is invertible. Furthermore, if $\tilde{\mathcal{A}}$ is invertible then, by defining $\tilde{\mathcal{B}} = [0 | \tilde{\mathcal{B}}^T]^T \in \mathbb{K}^{4n \times \beta}$ with $\tilde{\mathcal{B}} = \mathbb{P}\mathbb{B} \in \mathbb{K}^{n \times \beta}$ as in the previous section, we can check that $\tilde{\mathcal{A}}^{-1}\tilde{\mathcal{B}}$ and $\tilde{\mathcal{A}}^{-T}\tilde{\mathcal{B}}$ can be read off the last $n$ rows of $\tilde{\mathcal{A}}^{-1}\tilde{\mathcal{B}}$ and $\tilde{\mathcal{A}}^{-T}\tilde{\mathcal{B}}$, respectively.

We now turn to the permutation of some block rows and columns of this augmented matrix $\tilde{\mathcal{A}}$ in order to make it a $4n \times 4n$ block Toeplitz matrix with $4\alpha \times 4\alpha$ blocks. More precisely, let the matrix $\mathcal{A} \in \mathbb{K}^{4n \times 4n}$ be defined by

$$ \mathcal{A} = Q\tilde{\mathcal{A}}Q^{-1}, \quad Q := \mathcal{P}_{4,d} \otimes \mathbb{I}_{\alpha}. $$

Here, $\tilde{\mathcal{A}}$ is viewed as a block $4 \times 4$ matrix $\tilde{\mathcal{A}} = [\mathcal{T}_{i,j}]_{1 \le i,j \le 4}$ whose every block $\mathcal{T}_{i,j}$ is a $d \times d$ Toeplitz matrix (whose entries are themselves $\alpha \times \alpha$ blocks). The permutation matrix $Q \in \mathbb{K}^{4n \times 4n}$ therefore applies the perfect shuffle $\mathcal{P}_{4,d}$ in a block-wise manner to the block entries of the $\mathcal{T}_{i,j}$ (with the Kronecker product by $\mathbb{I}_{\alpha}$ being dictated by the fact that the entries of the $\mathcal{T}_{i,j}$'s have dimensions $\alpha \times \alpha$). It can then be checked that $\mathcal{A}$ is a block $d \times d$ Toeplitz matrix whose every block is a $4 \times 4$ matrix (whose entries are themselves $\alpha \times \alpha$ blocks):

$$ (3) \qquad \mathcal{A} = [\mathcal{A}_{i-j}]_{1 \le i,j \le d}, \qquad \mathcal{A}_k \in \mathbb{K}^{4\alpha \times 4\alpha}, \quad |k| < d. $$

The entries of the $2d-1$ blocks $\mathcal{A}_k$ are obtained by permuting those of the first block columns of the block lower triangular Toeplitz matrices $\mathbb{L}_j$ and $\mathbb{U}_j^T$ in (2). Hence they can be deduced from $([\tilde{G}_1|\tilde{G}_2|\tilde{G}_3], [\tilde{H}_1|\tilde{H}_2|\tilde{H}_3])$ in time $O(\alpha^2 d) \subseteq O(\alpha n)$.

Furthermore, $\tilde{\mathcal{A}}$ is invertible iff $\mathcal{A}$ is invertible; if $\mathcal{A}$ is invertible then, taking $\mathcal{B} := Q\tilde{\mathcal{B}}$ with $\tilde{\mathcal{B}} \in \mathbb{K}^{4n \times \beta}$ as before, we have $(\tilde{\mathcal{A}}^{-1}\tilde{\mathcal{B}}, \tilde{\mathcal{A}}^{-T}\tilde{\mathcal{B}}) = (Q^{-1}\mathcal{A}^{-1}\mathcal{B}, Q^{-1}\mathcal{A}^{-T}\mathcal{B})$. Hence, given the $\mathcal{A}_k$ and $\mathcal{B}$, it remains to determine if $\mathcal{A}$ in (3) is invertible and, if so, to compute $Q^{-1}\mathcal{A}^{-1}\mathcal{B}$ and $Q^{-1}\mathcal{A}^{-T}\mathcal{B}$.

**5. Block Toeplitz matrix inversion.** Since the matrix $\mathcal{A} \in \mathbb{K}^{4n \times 4n}$ in (3) is block Toeplitz with blocks of order $s := 4\alpha$, it can be transformed in time $O(\alpha n)$ into the block Hankel matrix $\mathcal{H} := \mathcal{A}\mathbb{R}$ with $\mathbb{R} := \mathbb{J}_d \otimes \mathbb{I}_s$ a block reflection matrix. Since the block size $s$ divides $4n$, we can rely directly on [6, 2] to compute some matrix Padé approximants from which the invertibility of $\mathcal{H}$ (and thus of $\mathcal{A}$) can be detected and then, if possible, a generator for the inverse $\mathcal{H}^{-1} = \mathbb{R}^{-1}\mathcal{A}^{-1}$ can be computed,
all this in deterministic time $\tilde{O}(\alpha^{\omega-1}n)$. Since $\mathcal{A}^{-1} = RH^{-1}$, one can check that the inversion formula from [6] that is used in [2] leads to

$$ \mathcal{A}^{-1} = \mathcal{L}_1\mathcal{U}_1 + \mathcal{L}_2\mathcal{U}_2 \quad \text{and} \quad \mathcal{A}^{-T} = \mathcal{U}_1^T\mathcal{L}_1^T + \mathcal{U}_2^T\mathcal{L}_2^T, $$

where $\mathcal{L}_1, \mathcal{L}_2, \mathcal{U}_1, \mathcal{U}_2 \in \mathbb{K}^{4n \times 4n}$ are block lower-triangular Toeplitz matrices with $4\alpha \times 4\alpha$ blocks that can be deduced from the generator of $\mathcal{H}^{-1}$ in time $O(\alpha n)$.

Hence $\mathcal{Q}^{-1}\mathcal{A}^{-1}\mathcal{B}$ can be evaluated as $\mathcal{Q}^{-1}(\mathcal{L}_1(\mathcal{U}_1\mathcal{B})) + \mathcal{Q}^{-1}(\mathcal{L}_2(\mathcal{U}_2\mathcal{B}))$ and, similarly, $\mathcal{Q}^{-1}\mathcal{A}^{-T}\mathcal{B} = \mathcal{Q}^{-1}(\mathcal{U}_1^T(\mathcal{L}_1^T\mathcal{B})) + \mathcal{Q}^{-1}(\mathcal{U}_2^T(\mathcal{L}_2^T\mathcal{B}))$. Since $\mathcal{B} \in \mathbb{K}^{4n \times \beta}$ with $\beta = O(\alpha)$ and thanks to the block triangular Toeplitz structure of the $\mathcal{L}_j$ and $\mathcal{U}_j$, this can be done in deterministic time $\tilde{O}(\alpha^{\omega-1}n)$ by means of $O(1)$ products of polynomial matrices of degree less than $d = n/\alpha$ and dimensions $4\alpha \times 4\alpha$.

REFERENCES

[1] A. BOSTAN, C.-P. JEANNEROD, C. MOUILLERON, AND É. SCHOST, On matrices with displacement structure: generalized operators and faster algorithms, SIAM J. Matrix Anal. Appl., 38 (2017), pp. 733–775.

[2] W. EBERLY, M. GIESBRECHT, P. GIORGI, A. STORJOHANN, AND G. VILLARD, Faster inversion and other black box matrix computations using efficient block projections, in ISSAC 2007 Proceedings, ACM, 2007, pp. 143–150.

[3] G. H. GOLUB AND C. F. V. LOAN, Matrix Computations, Johns Hopkins University Press, Baltimore, MD, USA, fourth ed., 2013.

[4] S. KHICHANE, Algorithms for structured approximation and interpolation, 2025. Internship report, MPRI, Université Paris Cité – LIP6, Sorbonne Université.

[5] S. KHICHANE AND V. NEIGER, 2025. Personal communication.

[6] G. LABAHN, D. CHOI, AND S. CABAY, The inverses of block Hankel and block Toeplitz matrices, SIAM J. Comput., 19 (1990), pp. 98–123.

[7] V. Y. PAN, Structured Matrices and Polynomials, Birkhäuser Boston Inc., 2001.