The elements of DeltaNet's core inverse matrix always lie within [-1, 1]

DeltaNet的核心逆矩阵的元素总是在[-1, 1]内 苏剑林 · 2026-01-26 · Mathematics matrix linear RNN attention

From A Brief History of Linear Attention: Imitation, Innovation, and Feedback, we've seen that the parallel form of DeltaNet involves an inverse matrix of the form $(\boldsymbol{I} + \boldsymbol{K}\boldsymbol{K}^{\top}\odot \boldsymbol{M}^-)^{-1}$. Recently, reader @Arch123 pointed out that experiments show the elements of this inverse matrix always lie within $[-1, 1]$, and asked whether this can be proved or disproved mathematically.

In this article, we will prove that this conclusion holds strictly, using two different approaches.

Problem statement

First, let's restate the problem precisely. Consider a matrix $\boldsymbol{K}=[\boldsymbol{k}_1,\boldsymbol{k}_2,\cdots,\boldsymbol{k}_n]^{\top}\in\mathbb{R}^{n\times d}$, where each $\boldsymbol{k}_i\in\mathbb{R}^{d\times 1}$ is a column vector with norm at most 1, and $\boldsymbol{M}\in\mathbb{R}^{n\times n}$ is a lower-triangular mask matrix, defined as

\begin{equation}M_{i,j} = \left\{\begin{aligned} &1, &i \geq j \\ &0, &i < j\end{aligned}\right.\end{equation}

$\boldsymbol{I}$ is the identity matrix, and $\boldsymbol{M}^- = \boldsymbol{M} - \boldsymbol{I}$. What we want to prove is:

\begin{equation}(\boldsymbol{I} + \boldsymbol{K}\boldsymbol{K}^{\top}\odot \boldsymbol{M}^-)^{-1}\quad\in\quad [-1, 1]^{n\times n}\end{equation}more

Let $\boldsymbol{X}=\boldsymbol{I} + \boldsymbol{K}\boldsymbol{K}^{\top}\odot \boldsymbol{M}^-$, and denote its inverse by $\boldsymbol{Y}$. Writing $\boldsymbol{X}$ out explicitly gives

\begin{equation}\boldsymbol{X}=\boldsymbol{I} + \boldsymbol{K}\boldsymbol{K}^{\top}\odot \boldsymbol{M}^- = \left(\begin{array}{cccccc} 1 & 0 & 0 & \cdots & 0 & 0 \\[5pt] \boldsymbol{k}_1^{\top}\boldsymbol{k}_2 & 1 & 0 & \cdots & 0 & 0 \\[5pt] \boldsymbol{k}_1^{\top}\boldsymbol{k}_3 & \boldsymbol{k}_2^{\top}\boldsymbol{k}_3 & 1 & \cdots & 0 & 0 \\[5pt] \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\[5pt] \boldsymbol{k}_1^{\top}\boldsymbol{k}_{n-1} & \boldsymbol{k}_2^{\top}\boldsymbol{k}_{n-1} & \boldsymbol{k}_3^{\top}\boldsymbol{k}_{n-1} & \cdots & 1 & 0 \\[5pt] \boldsymbol{k}_1^{\top}\boldsymbol{k}_n & \boldsymbol{k}_2^{\top}\boldsymbol{k}_n & \boldsymbol{k}_3^{\top}\boldsymbol{k}_n & \cdots & \boldsymbol{k}_{n-1}^{\top}\boldsymbol{k}_n & 1 \end{array}\right)\end{equation}

Since each $\boldsymbol{k}_i$ has norm at most 1, it's clear that every element of $\boldsymbol{X}$ lies within $[-1,1]$. What we need to prove is that every element of $\boldsymbol{Y}=\boldsymbol{X}^{-1}$ also lies within $[-1,1]$.

Mathematical induction

Since this inverse matrix arises in DeltaNet, it surely has a clear model-related background, and drawing on that background might help us prove the result more quickly — we'll leave that to the next section. In this section, let's think of it purely as a mathematical problem.

Diagonal-block property

In An Efficient Method for Inverting "Diagonal + Low-Rank" Triangular Matrices, we've already seen that lower-triangular matrices have some excellent properties: first, they are closed under matrix multiplication; second, they satisfy "the diagonal of the inverse equals the inverse of the diagonal," which can be generalized to block lower-triangular matrices, i.e., "the diagonal blocks of the inverse equal the inverses of the diagonal blocks."

From this, we obtain $\boldsymbol{Y}_{[:n-1,:n-1]}=(\boldsymbol{X}_{[:n-1,:n-1]})^{-1}$ as well as $\boldsymbol{Y}_{[1:,1:]}=(\boldsymbol{X}_{[1:,1:]})^{-1}$, where slicing is understood in the Numpy sense. This property suggests we can use mathematical induction on $n$. Suppose the conclusion holds for any $\boldsymbol{K}$ matrix satisfying the condition with size $(n-1)\times d$. Then for the matrix $\boldsymbol{X}$, we only need to consider the following two block decompositions:

\begin{equation}\boldsymbol{X} = \left(\begin{array}{ccccc:c} 1 & 0 & 0 & \cdots & 0 & 0 \\[5pt] \boldsymbol{k}_1^{\top}\boldsymbol{k}_2 & 1 & 0 & \cdots & 0 & 0 \\[5pt] \boldsymbol{k}_1^{\top}\boldsymbol{k}_3 & \boldsymbol{k}_2^{\top}\boldsymbol{k}_3 & 1 & \cdots & 0 & 0 \\[5pt] \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\[5pt] \boldsymbol{k}_1^{\top}\boldsymbol{k}_{n-1} & \boldsymbol{k}_2^{\top}\boldsymbol{k}_{n-1} & \boldsymbol{k}_3^{\top}\boldsymbol{k}_{n-1} & \cdots & 1 & 0 \\[5pt] \hdashline \boldsymbol{k}_1^{\top}\boldsymbol{k}_n & \boldsymbol{k}_2^{\top}\boldsymbol{k}_n & \boldsymbol{k}_3^{\top}\boldsymbol{k}_n & \cdots & \boldsymbol{k}_{n-1}^{\top}\boldsymbol{k}_n & 1 \end{array}\right) = \left(\begin{array}{c:cccc} 1 & 0 & 0 & \cdots & 0 & 0 \\[5pt] \hdashline \boldsymbol{k}_1^{\top}\boldsymbol{k}_2 & 1 & 0 & \cdots & 0 & 0 \\[5pt] \boldsymbol{k}_1^{\top}\boldsymbol{k}_3 & \boldsymbol{k}_2^{\top}\boldsymbol{k}_3 & 1 & \cdots & 0 & 0 \\[5pt] \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\[5pt] \boldsymbol{k}_1^{\top}\boldsymbol{k}_{n-1} & \boldsymbol{k}_2^{\top}\boldsymbol{k}_{n-1} & \boldsymbol{k}_3^{\top}\boldsymbol{k}_{n-1} & \cdots & 1 & 0 \\[5pt] \boldsymbol{k}_1^{\top}\boldsymbol{k}_n & \boldsymbol{k}_2^{\top}\boldsymbol{k}_n & \boldsymbol{k}_3^{\top}\boldsymbol{k}_n & \cdots & \boldsymbol{k}_{n-1}^{\top}\boldsymbol{k}_n & 1 \end{array}\right)\end{equation}

Then, based on $\boldsymbol{Y}_{[:n-1,:n-1]}=(\boldsymbol{X}_{[:n-1,:n-1]})^{-1}$ and $\boldsymbol{Y}_{[1:,1:]}=(\boldsymbol{X}_{[1:,1:]})^{-1}$, we can show that every element of $\boldsymbol{Y}$ except the lower-left block $Y_{n,1}$ lies within $[-1,1]$, so we only need to additionally prove $Y_{n,1}\in [-1,1]$.

Adjugate matrix

To prove $Y_{n,1}\in [-1,1]$, let's use the adjugate matrix to write $\boldsymbol{X}^{-1}$ out explicitly. Since $\boldsymbol{X}$ is a lower-triangular matrix with all diagonal entries equal to 1, its determinant is 1. Hence, by the adjugate-based inversion formula, we have

\begin{equation}Y_{n,1} = (-1)^{n+1}\det\left(\begin{array}{ccccc} \boldsymbol{k}_1^{\top}\boldsymbol{k}_2 & 1 & 0 & \cdots & 0 & 0 \\[5pt] \boldsymbol{k}_1^{\top}\boldsymbol{k}_3 & \boldsymbol{k}_2^{\top}\boldsymbol{k}_3 & 1 & \cdots & 0 & 0 \\[5pt] \boldsymbol{k}_1^{\top}\boldsymbol{k}_4 & \boldsymbol{k}_2^{\top}\boldsymbol{k}_4 & \boldsymbol{k}_3^{\top}\boldsymbol{k}_4 & \cdots & 0 & 0 \\[5pt] \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\[5pt] \boldsymbol{k}_1^{\top}\boldsymbol{k}_{n-1} & \boldsymbol{k}_2^{\top}\boldsymbol{k}_{n-1} & \boldsymbol{k}_3^{\top}\boldsymbol{k}_{n-1} & \cdots & \boldsymbol{k}_{n-2}^{\top}\boldsymbol{k}_{n-1} & 1 \\[5pt] \boldsymbol{k}_1^{\top}\boldsymbol{k}_n & \boldsymbol{k}_2^{\top}\boldsymbol{k}_n & \boldsymbol{k}_3^{\top}\boldsymbol{k}_n & \cdots & \boldsymbol{k}_{n-2}^{\top}\boldsymbol{k}_n & \boldsymbol{k}_{n-1}^{\top}\boldsymbol{k}_n \end{array}\right)\end{equation}

This is a lower-triangular matrix with the subdiagonal entries also set to 1, so the determinant computation is a bit more involved — though not overly so, since the last column has only two nonzero entries. Expanding the determinant along the last column reduces it to the difference of two $n-1$-order determinants, a pattern that again points us toward mathematical induction.

Product form

Let's try computing the first few results by hand:

\begin{gather}Y_{2,1} = -\boldsymbol{k}_1^{\top}\boldsymbol{k}_2 ,\qquad Y_{3,1} = \det\left(\begin{array}{cc} \boldsymbol{k}_1^{\top}\boldsymbol{k}_2 & 1 \\[5pt] \boldsymbol{k}_1^{\top}\boldsymbol{k}_3 & \boldsymbol{k}_2^{\top}\boldsymbol{k}_3 \end{array}\right) = \boldsymbol{k}_1^{\top}\boldsymbol{k}_2\boldsymbol{k}_2^{\top}\boldsymbol{k}_3 - \boldsymbol{k}_1^{\top}\boldsymbol{k}_3 = -\boldsymbol{k}_1^{\top}(\boldsymbol{I}-\boldsymbol{k}_2\boldsymbol{k}_2^{\top})\boldsymbol{k}_3 \\[8pt] Y_{4,1} = -\det\left(\begin{array}{ccc} \boldsymbol{k}_1^{\top}\boldsymbol{k}_2 & 1 & 0 \\[5pt] \boldsymbol{k}_1^{\top}\boldsymbol{k}_3 & \boldsymbol{k}_2^{\top}\boldsymbol{k}_3 & 1 \\[5pt] \boldsymbol{k}_1^{\top}\boldsymbol{k}_4 & \boldsymbol{k}_2^{\top}\boldsymbol{k}_4 & \boldsymbol{k}_3^{\top}\boldsymbol{k}_4 \end{array}\right) = \det\left(\begin{array}{cc} \boldsymbol{k}_1^{\top}\boldsymbol{k}_2 & 1 \\[5pt] \boldsymbol{k}_1^{\top}\boldsymbol{k}_4 & \boldsymbol{k}_2^{\top}\boldsymbol{k}_4 \end{array}\right) -\det\left(\begin{array}{cc} \boldsymbol{k}_1^{\top}\boldsymbol{k}_2 & 1 \\[5pt] \boldsymbol{k}_1^{\top}\boldsymbol{k}_3 & \boldsymbol{k}_2^{\top}\boldsymbol{k}_3 \end{array}\right) \boldsymbol{k}_3^{\top}\boldsymbol{k}_4 = -\boldsymbol{k}_1^{\top}(\boldsymbol{I}-\boldsymbol{k}_2\boldsymbol{k}_2^{\top})(\boldsymbol{I}-\boldsymbol{k}_3\boldsymbol{k}_3^{\top})\boldsymbol{k}_4\end{gather}

From this we can conjecture

\begin{equation}Y_{n,1} = -\boldsymbol{k}_1^{\top}(\boldsymbol{I}-\boldsymbol{k}_2\boldsymbol{k}_2^{\top})(\boldsymbol{I}-\boldsymbol{k}_3\boldsymbol{k}_3^{\top})\cdots (\boldsymbol{I}-\boldsymbol{k}_{n-1}\boldsymbol{k}_{n-1}^{\top})\boldsymbol{k}_n \end{equation}

I'll leave it to the reader to prove this conjecture by mathematical induction. Assuming this conjecture has been proved, then from the condition $\Vert\boldsymbol{k}_i\Vert\leq 1$ we get $\Vert(\boldsymbol{I}-\boldsymbol{k}_i\boldsymbol{k}_i^{\top})\boldsymbol{x}\Vert^2 = \Vert\boldsymbol{x}\Vert^2 + (\boldsymbol{k}_i^{\top} \boldsymbol{x})^2 (\Vert\boldsymbol{k}_i\Vert^2 - 2) \leq \Vert\boldsymbol{x}\Vert^2$, and therefore

\begin{equation}|Y_{n,1}| \leq \Vert\boldsymbol{k}_1\Vert\times \Vert(\boldsymbol{I}-\boldsymbol{k}_2\boldsymbol{k}_2^{\top})(\boldsymbol{I}-\boldsymbol{k}_3\boldsymbol{k}_3^{\top})\cdots (\boldsymbol{I}-\boldsymbol{k}_{n-1}\boldsymbol{k}_{n-1}^{\top})\boldsymbol{k}_n\Vert \leq \Vert\boldsymbol{k}_1\Vert\times \Vert\boldsymbol{k}_n\Vert \leq 1\end{equation}

This completes the proof of $Y_{n,1}\in [-1,1]$, and by mathematical induction, $\boldsymbol{Y}\in[-1, 1]^{n\times n}$ holds identically.

Dual computation

The direct proof in the previous section feels somewhat "brute-force." Later, @zhxlin from the FLA group pointed out that we could return to the original context of this inverse matrix — DeltaNet itself — and compute DeltaNet in two different ways; comparing the results yields an explicit expression for the inverse matrix, giving a relatively cleaner proof.

Inverse-matrix form

We know that the recursive form of DeltaNet is

\begin{equation}\boldsymbol{S}_t = \boldsymbol{S}_{t-1}(\boldsymbol{I} - \boldsymbol{k}_t\boldsymbol{k}_t^{\top}) + \boldsymbol{v}_t\boldsymbol{k}_t^{\top} = \boldsymbol{S}_{t-1} + (\boldsymbol{v}_t - \boldsymbol{S}_{t-1} \boldsymbol{k}_t)\boldsymbol{k}_t^{\top}\end{equation}

where $\boldsymbol{S}_0 = \boldsymbol{0}$. Let's first look at the second equality. Define $\boldsymbol{u}_t=\boldsymbol{v}_t - \boldsymbol{S}_{t-1} \boldsymbol{k}_t$; then

\begin{equation}\boldsymbol{S}_t = \boldsymbol{S}_{t-1} + \boldsymbol{u}_t\boldsymbol{k}_t^{\top} = \sum_{i=1}^t \boldsymbol{u}_i\boldsymbol{k}_i^{\top}\end{equation}

so

\begin{equation}\boldsymbol{u}_t = \boldsymbol{v}_t - \boldsymbol{S}_{t-1} \boldsymbol{k}_t = \boldsymbol{v}_t - \left(\sum_{i=1}^{t-1} \boldsymbol{u}_i\boldsymbol{k}_i^{\top}\right) \boldsymbol{k}_t = \boldsymbol{v}_t - \sum_{i=1}^{t-1} \boldsymbol{u}_i(\boldsymbol{k}_i^{\top} \boldsymbol{k}_t)\end{equation}

Defining $\boldsymbol{U}=[\boldsymbol{u}_1,\boldsymbol{u}_2,\cdots,\boldsymbol{u}_n]^{\top}, \boldsymbol{V}=[\boldsymbol{v}_1,\boldsymbol{v}_2,\cdots,\boldsymbol{v}_n]^{\top}$, the above is equivalent to $\boldsymbol{U} = \boldsymbol{V} - (\boldsymbol{K}\boldsymbol{K}^{\top}\odot \boldsymbol{M}^-)\boldsymbol{U}$, or $\boldsymbol{U}=(\boldsymbol{I} + \boldsymbol{K}\boldsymbol{K}^{\top}\odot \boldsymbol{M}^-)^{-1}\boldsymbol{V}$ — this is where the inverse matrix $(\boldsymbol{I} + \boldsymbol{K}\boldsymbol{K}^{\top}\odot \boldsymbol{M}^-)^{-1}$ comes from, and it is the key to parallel computation in DeltaNet and its successors such as GDN and KDA.

Recursive expansion

Now let's look at the first equality. Expanding it step by step directly gives

\begin{equation}\boldsymbol{S}_t = \boldsymbol{v}_1\boldsymbol{k}_1^{\top} \boldsymbol{H}_{2\to t} + \cdots + \boldsymbol{v}_{t-1}\boldsymbol{k}_{t-1}^{\top} \boldsymbol{H}_{t\to t} + \boldsymbol{v}_t\boldsymbol{k}_t^{\top} = \sum_{i=1}^t \boldsymbol{v}_i\boldsymbol{k}_i^{\top} \boldsymbol{H}_{i+1\to t} \end{equation}

where $\boldsymbol{H}_{r\to t} \triangleq (\boldsymbol{I} - \boldsymbol{k}_r\boldsymbol{k}_r^{\top})(\boldsymbol{I} - \boldsymbol{k}_{r+1}\boldsymbol{k}_{r+1}^{\top})\cdots(\boldsymbol{I} - \boldsymbol{k}_t\boldsymbol{k}_t^{\top})$, with the convention $\boldsymbol{H}_{t+1\to t}=\boldsymbol{I}$.

Substituting the above into the definition of $\boldsymbol{u}_t$ gives

\begin{equation}\boldsymbol{u}_t = \boldsymbol{v}_t - \boldsymbol{S}_{t-1} \boldsymbol{k}_t = \boldsymbol{v}_t - \sum_{i=1}^{t-1} \boldsymbol{v}_i\boldsymbol{k}_i^{\top} \boldsymbol{H}_{i+1\to t-1}\boldsymbol{k}_t\end{equation}

Comparing results

Still writing $\boldsymbol{Y}=(\boldsymbol{I} + \boldsymbol{K}\boldsymbol{K}^{\top}\odot \boldsymbol{M}^-)^{-1}$, we have that $\boldsymbol{U}=\boldsymbol{Y}\boldsymbol{V}$ gives $\boldsymbol{u}_t = \sum_{i=1}^n Y_{t, i} \boldsymbol{v}_i$. Comparing with the expression above, we can read off

\begin{equation}Y_{t, i} = \left\{\begin{aligned}& 0, & i > t \\ & 1, & i = t \\ & -\boldsymbol{k}_i^{\top} \boldsymbol{H}_{i+1\to t-1}\boldsymbol{k}_t, & i < t \\ \end{aligned}\right.\end{equation}

So we only need to prove $|\boldsymbol{k}_i^{\top} \boldsymbol{H}_{i+1\to t-1}\boldsymbol{k}_t|\leq 1$, which follows immediately from $\Vert\boldsymbol{k}_i\Vert\leq 1$ together with the result $\Vert(\boldsymbol{I}-\boldsymbol{k}_i\boldsymbol{k}_i^{\top})\boldsymbol{x}\Vert \leq \Vert\boldsymbol{x}\Vert$ already established in the first proof:

\begin{equation}|\boldsymbol{k}_i^{\top} \boldsymbol{H}_{i+1\to t-1}\boldsymbol{k}_t| \leq \Vert\boldsymbol{k}_i\Vert\times \Vert\boldsymbol{H}_{i+1\to t-1}\boldsymbol{k}_t\Vert \leq \Vert\boldsymbol{k}_i\Vert\times \Vert\boldsymbol{k}_t\Vert \leq 1\end{equation}

This establishes the conclusion to be proved.

Summary

This article has given two proofs of the boundedness of the core inverse matrix in DeltaNet.