OctoInform Beta

OpenAI preprint, September 2026 · §1. Introduction · §1.2

§1.2 (setting): affine linear pencils and feasibility: An affine pencil of order qq evaluated entrywise at d×dd\times d matrices and flattened is A0⊗Id+∑iAi⊗XiA_0\otimes I_d+\sum_i A_i\otimes X_i

Matrix evaluations of affine pencils are Kronecker sums.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Noncommutative rational formulas in x1,…,xnx_1,\dots,x_n are studied through linear pencils: square matrices whose entries are affine forms a0+a1x1+…+anxna_0+a_1x_1+\dots+a_nx_n with rational coefficients. Substituting d×dd\times d matrices for the variables turns a pencil of order qq into a matrix of order qdqd. The library relates the entrywise evaluation of a pencil at matrices to a sum of Kronecker products by treating the constant term as one more variable, with a matrix of its own.

Affine Forms and Pencils

An affine linear form aa in nn variables is a pair (a0,(a1,…,an))(a_0,(a_1,\dots,a_n)) of a rational constant a0a_0 and nn rational coefficients.✦ The coefficient vector of an affine linear form aa in nn variables is (a0,a1,…,an)∈ℚn+1(a_0,a_1,\dots,a_n)\in\mathbb{Q}^{n+1}, and ara_r denotes its rr-th entry.✦

Let RR be a ring and c:ℚ→Rc\colon\mathbb{Q}\to R a ring homomorphism. The evaluation a(X)a(X) of aa at a point X=(X1,…,Xn)∈RnX=(X_1,\dots,X_n)\in R^n is the element a(X)=c(a0)+∑i=1nc(ai)Xia(X)=c(a_0)+\sum_{i=1}^{n}c(a_i)\,X_i(1)✦ of RR, and the homogeneous evaluation ah(Z)a^{\mathrm h}(Z) of aa at Z=(Z0,…,Zn)∈Rn+1Z=(Z_0,\dots,Z_n)\in R^{n+1} is the element ah(Z)=∑i=0nc(ai)Zia^{\mathrm h}(Z)=\sum_{i=0}^{n}c(a_i)\,Z_i(2)✦ of RR.

An affine pencil LL in nn variables is a square matrix (Ljk)(L_{jk}) of affine linear forms in nn variables, with rows and columns indexed by a finite set II; its order is the size qq of II. The coefficient matrices of a pencil LL of order qq over a ring KK receiving ℚ\mathbb{Q} are the matrices A0,…,An∈Matq(K)A_0,\dots,A_n\in\mathrm{Mat}_q(K) with entries (Ai)jk=(Ljk)i,(A_i)_{jk}=(L_{jk})_i ,(3)✦ the rational coefficients read in KK. The evaluation L(X)L(X) of LL at square matrices X1,…,XnX_1,\dots,X_n is the matrix of blocks (Ljk(X))(L_{jk}(X)), the rationals entering as scalar matrices; the homogeneous evaluation Lh(Z)L^{\mathrm h}(Z) is formed in the same way.

For finite sets II and JJ, the flattening flat⁡(M)\operatorname{flat}(M) of a matrix MM indexed by II whose entries are matrices indexed by JJ is the matrix indexed by I×JI\times J with entries flat⁡(M)(j,α),(k,β)=(Mjk)αβ.\operatorname{flat}(M)_{(j,\alpha),(k,\beta)}=(M_{jk})_{\alpha\beta}.(4) For a positive integer ww, matrices A0,…,Aw−1A_0,\dots,A_{w-1} of order qq and matrices Z0,…,Zw−1Z_0,\dots,Z_{w-1} of order ee over a ring, the Kronecker block matrix ℬ(A;Z)\mathcal{B}(A;Z) is the matrix of order qeqe, with rows and columns indexed by pairs (j,α)(j,\alpha), given by ℬ(A;Z)=∑i=0w−1Ai⊗Zi.\mathcal{B}(A;Z)=\sum_{i=0}^{w-1}A_i\otimes Z_i .(5)

The Claim

Theorem 1. Let RR be a ring with a ring homomorphism c:ℚ→Rc\colon\mathbb{Q}\to R, let aa be an affine linear form in nn variables, and let X∈RnX\in R^n. Then the homogeneous evaluation of aa at (1,X1,…,Xn)(1,X_1,\dots,X_n) is its evaluation at XX: ah(1,X1,…,Xn)=a(X).a^{\mathrm h}(1,X_1,\dots,X_n)=a(X).(6)✦ Let KK be a field of characteristic zero, LL a pencil in nn variables indexed by a finite set II, and Z0,…,ZnZ_0,\dots,Z_n matrices over KK indexed by a finite set JJ. Then for j,k∈Ij,k\in I and α,β∈J\alpha,\beta\in J, with the coefficients read in KK, flat⁡(Lh(Z))(j,α),(k,β)=∑r=0n(Ljk)r(Zr)αβ.\operatorname{flat}\bigl(L^{\mathrm h}(Z)\bigr)_{(j,\alpha),(k,\beta)} =\sum_{r=0}^{n}(L_{jk})_r\,(Z_r)_{\alpha\beta}.(7)✦ Let KK and EE be fields of characteristic zero, LL a pencil of order qq with coefficient matrices A0,…,AnA_0,\dots,A_n over KK, φ:K→E\varphi\colon K\to E a ring homomorphism, applied to matrices entrywise, and X1,…,XnX_1,\dots,X_n matrices of order dd over EE. Then the Kronecker block matrix of φ(A0),…,φ(An)\varphi(A_0),\dots,\varphi(A_n) and Id,X1,…,XnI_d,X_1,\dots,X_n is the flattened evaluation of LL at XX: φ(A0)⊗Id+∑i=1nφ(Ai)⊗Xi=flat⁡(L(X)).\varphi(A_0)\otimes I_d+\sum_{i=1}^{n}\varphi(A_i)\otimes X_i =\operatorname{flat}\bigl(L(X)\bigr).(8)✦

In the paper, the result reads: an affine pencil of order qq is L(x)=A0+∑i=1nAixiL(x)=A_0+\sum_{i=1}^{n}A_ix_i with Ai∈Matq(ℚ)A_i\in\mathrm{Mat}_q(\mathbb{Q}), its evaluation at X1,…,Xn∈Matd(E)X_1,\dots,X_n\in\mathrm{Mat}_d(E), for an extension field EE of ℚ\mathbb{Q}, is A0⊗Id+∑i=1nAi⊗XiA_0\otimes I_d+\sum_{i=1}^{n}A_i\otimes X_i, and LL is feasible if one such evaluation is invertible.

What Is Checked

The claim is stated over affine linear forms with rational coefficients, their evaluation (1) and homogeneous evaluation (2) in a ring receiving ℚ\mathbb{Q}, the coefficient matrices (3) of a pencil, flattening (4) and the Kronecker block matrix (5).

The library also proves that evaluation is additive in the form. For affine linear forms aa and bb in nn variables, the sum a+ba+b is the form whose coefficients are the sums of those of aa and bb, and the zero form is the form with all coefficients zero. For a ring RR receiving ℚ\mathbb{Q} and X∈RnX\in R^n, the zero form evaluates to 00 at XX and (a+b)(X)=a(X)+b(X)(a+b)(X)=a(X)+b(X).