betaFeedback

WorksMathematics

An explicit determinantal formula for Sinkhorn limits of matrices and tensors

Abstract

We give an explicit formula, as a single determinant, for the polynomial satisfied by any entry of the limit obtained by scaling a positive tensor of format n1×⋯×nrn_1\times\dots\times n_r to arbitrary prescribed one-dimensional margins (Sinkhorn–Knopp scaling, Kruithof's method, iterative proportional fitting). The polynomial is the multilinear resultant, on the Segre variety \PP^{n_1-1}\times\dots\times\PP^{n_r-1}, of the linear forms expressing the margin conditions. Its degree is the multinomial coefficient N=(dn1−1,…,nr−1)N=\binom{d}{n_1-1,\dots,n_r-1} with d=∑k(nk−1)d=\sum_k(n_k-1), and for generic tensors its roots are the corresponding entries of all complex solutions of the scaling equations. A Sylvester matrix turns it into an explicit N×NN\times N generalized eigenvalue problem, whose null vector recovers the whole limit. The leading coefficient is the principal AA-determinant of the product of simplices, that is, the product of the hyperdeterminants of all faces of the tensor. The constant term is likewise a product of face hyperdeterminants, and the faces avoiding the chosen entry split off as a factor independent of that entry. For matrices we also give a short proof, in Plücker coordinates, of a diagonal form of the eliminant. For every positive tensor, the limit is the unique root for which the Sylvester matrix has a positive null vector of monomials. Generically, the other roots are the corner entries of the solutions of the same scaling equations with complex scaling factors.

Introduction

Let TT be a positive tensor of format n1×⋯×nrn_1 \times\cdots\times n_r, and for each mode kk let μ(k)∈R>0nk\mu^{(k)} \in\mathbb{R}^{n_k}_{>0} be target margins with a common total τ\tau. Repeatedly rescaling the slices of TT so that its mode-kk margins equal μ(k)\mu^{(k)} converges to a tensor

P=T∘(u(1)⊗⋯⊗u(r)),∑c:ck=iPc=μi(k)(1≤k≤r, 1≤i≤nk),P = T \circ\left(u^{(1)} \otimes\cdots\otimes u^{(r)}\right), \qquad\sum_{c:c_k=i} P_c = \mu_i^{(k)} \quad(1 \leq k \leq r,\ 1 \leq i \leq n_k),

which is the unique tensor of this form with these margins [9, 12, 7]. For r=2r=2 this is matrix scaling, known as the Sinkhorn–Knopp algorithm, as Kruithof’s double-factor method, and, in statistics, as iterative proportional fitting; it also arises in entropically regularized optimal transport, where the marginals are arbitrary. Everything below allows arbitrary positive margins; the special targets μ(1)=1\mu^{(1)} = 1, μ(2)=mn1\mu^{(2)} = \frac{m}{n}1 give what Rowland and Wu call the Sinkhorn limit.

The entries of PP are algebraic over the entries of TT and the margins. For 2×22 \times2 matrices they involve square roots [10, 5]. Rowland and Wu [11] conjectured, on the basis of extensive computation, that the top-left entry of the limit of an m×nm \times n matrix is a root of an explicit polynomial of degree (m+n−2m−1)\binom{m+n-2}{m-1}; Fang [5] proved the degree bound by viewing the scaling factors as a point of a Segre variety, and later proved the full conjecture [6].

We extend this to tensors of any order with arbitrary margins. Write y=u(1)⊗⋯⊗u(r)y = u^{(1)} \otimes\cdots\otimes u^{(r)}. The margin conditions are linear in yy, and yy ranges over the cone over the Segre variety Σ=Pn1−1×⋯×Pnr−1\Sigma= \mathbb{P}^{n_1-1} \times\cdots\times\mathbb{P}^{n_r-1}, of dimension d=∑k(nk−1)d = \sum_k(n_k-1). After normalization the conditions are dd multilinear forms ℓ1,…,ℓd\ell_1,\ldots,\ell_d; adding the form ℓx\ell_x that fixes the corner entry to xx gives d+1d+1 forms on a dd-dimensional variety. For generic TT they have a common zero exactly when xx is the corner entry of a solution. The number of complex solutions, deg⁡Σ\deg\Sigma, is known: it is the maximum likelihood degree of the scaled Segre variety [1]. Our main result (Theorem 3.2) is that the multilinear resultant Res⁡Σ(ℓ1,…,ℓd,ℓx)\operatorname{Res}_{\Sigma}(\ell_1,\ldots,\ell_d,\ell_x) is, up to a factor independent of xx, the product of x−xix-x_i over all complex solutions; by a theorem of Sturmfels and Zelevinsky [13] it is a single Sylvester determinant, of size (d+1)N(d+1)N with xx in exactly N=(dn1−1,…,nr−1)=deg⁡ΣN=\binom{d}{n_1-1,\ldots,n_r-1}=\deg\Sigma columns, so that the corner entry is an eigenvalue of an explicit N×NN\times N pencil (Corollary 3.3). § 4 identifies the leading coefficient with the principal AA-determinant (a product of hyperdeterminants of faces), shows that the constant term is also such a product, and determines the content. § 5 treats matrices, where the pencil has a diagonal form; this form was conjectured by Rowland and Wu [11] and proved by Fang [6], and we give a short proof in Plücker coordinates. Theorem 3.4 characterizes the limit among the roots for every positive TT: it is the only root for which Φ\Phi has a left null vector of monomials at a positive point. § 6 accounts for the other roots, which come from the same scaling equations with complex factors (equivalently, from the other critical points of the dual potential); the real ones are positive scalings of sign-twisted copies of TT. Appendix A gives numerical examples, including cases in which several roots lie in the range of possible values of the corner entry and a degenerate tensor of reduced degree.

The Segre formulation

Fix the format n=(n1,…,nr)\mathbf{n}=(n_1,\ldots,n_r) with all nj≥2n_j\ge2, write kj=nj−1k_j=n_j-1, d=k1+⋯+krd=k_1+\cdots+k_r, and

N=(dk1,…,kr)=deg⁡Σ.N=\binom{d}{k_1,\ldots,k_r}=\deg\Sigma.

Index cells by c=(c1,…,cr)c=(c_1,\ldots,c_r), write 1=(1,…,1)\mathbf{1}=(1,\ldots,1) for the corner, tct_c for the entries of TT, and yc=uc1(1)⋯ucr(r)y_c=u_{c_1}^{(1)}\cdots u_{c_r}^{(r)} for the Segre coordinates. Let σ(y)=∑ctcyc\sigma(y)=\sum_c t_cy_c and define the multilinear forms

ℓk,i(y)=∑c(δck,i−μi(k)τ)tcyc(1≤k≤r, 2≤i≤nk),ℓx(y)=t1y1−xτσ(y).\ell_{k,i}(y)=\sum_c\left(\delta_{c_k,i}-\frac{\mu_i^{(k)}}{\tau}\right)t_cy_c\quad(1\le k\le r,\ 2\le i\le n_k),\qquad\ell_x(y)=t_{\mathbf{1}}y_{\mathbf{1}}-\frac{x}{\tau}\sigma(y).

There are dd forms ℓk,i\ell_{k,i}; we list them as ℓ1,…,ℓd\ell_1,\ldots,\ell_d.

Lemma 2.1. A point y∈Σy\in\Sigma with σ(y)≠0\sigma(y)\ne0 is a common zero of ℓ1,…,ℓd\ell_1,\ldots,\ell_d if and only if P=τσ(y)T∘yP=\frac{\tau}{\sigma(y)}T\mathbin{\circ}y has margins μ(1),…,μ(r)\mu^{(1)},\ldots,\mu^{(r)}. In that case ℓx(y)=0\ell_x(y)=0 exactly when x=P1x=P_{\mathbf{1}}.

Proof. The mode-kk margin of PP at ii is τσ(y)∑ck=itcyc\frac{\tau}{\sigma(y)}\sum_{c_k=i}t_cy_c, and ℓk,i(y)=σ(y)τ(margin−μi(k))\ell_{k,i}(y)=\frac{\sigma(y)}{\tau}\left(\text{margin}-\mu_i^{(k)}\right). The forms with i=1i=1 are omitted because the margins in each mode sum to τ\tau automatically. Finally, ℓx(y)=σ(y)τ(P1−x)\ell_x(y)=\frac{\sigma(y)}{\tau}(P_{\mathbf{1}}-x).

Thus the complex solutions of the scaling problem are the points of Z=Σ∩{ℓ1=⋯=ℓd=0}Z=\Sigma\cap\{\ell_1=\cdots=\ell_d=0\} with σ≠0\sigma\ne0, and the scaling limit is the unique positive one.

Lemma 2.2. Fix margins with τ≠0\tau\ne0 and all μi(k)≠0\mu_i^{(k)}\ne0 (for instance positive). For TT outside a proper Zariski-closed subset, ZZ lies in the dense torus Σ∘\Sigma^\circ of Σ\Sigma and consists of NN simple points, at each of which σ≠0\sigma\ne0.

Proof. Each y∈Σy\in\Sigma lies in the torus orbit OFO_F of a unique face F=F1×⋯×FrF=F_1\times\cdots\times F_r (∅≠Fj⊆[nj]\varnothing\ne F_j\subseteq[n_j]), and yc≠0y_c\ne0 exactly for c∈Fc\in F. For fixed y∈OFy\in O_F the ℓk,i(y)\ell_{k,i}(y) are linear forms in (tc)c∈F(t_c)_{c\in F} with coefficient vectors yc(χk,i−μi(k)τ1)∣Fy_c(\chi_{k,i}-\frac{\mu_i^{(k)}}{\tau}\mathbf{1})|_F, where χk,i\chi_{k,i} is the indicator of the slice ck=ic_k=i. The vectors χk,i∣F\chi_{k,i}|_F (i∈Fki \in F_k, all kk) span a space of dimension dim⁡F+1\dim F+1 containing 1F1_F. If F≠[n1]×⋯×[nr]F \ne[n_1]\times\cdots\times[n_r], choose kk with Fk≠[nk]F_k \ne[n_k]: either some i≥2i \ge2 is not in FkF_k, and then the (k,i)(k,i) vector is −μi(k)τ1F≠0-\frac{\mu_i^{(k)}}{\tau}1_F \ne0, or Fk={2,…,nk}F_k = \{2,\ldots,n_k\}, and then the (k,i)(k,i) vectors for i≥2i \ge2 sum to μ1(k)τ1F≠0\frac{\mu_1^{(k)}}{\tau}1_F \ne0. In both cases 1F1_F, and hence every χk,i∣F\chi_{k,i}|_F, lies in the span of our vectors, so the forms impose dim⁡F+1\dim F+1 conditions on TT. The incidence variety {(T,y):y∈OF, ℓ1(y)=⋯=ℓd(y)=0}\{(T,y): y \in O_F,\ \ell_1(y)=\cdots=\ell_d(y)=0\} therefore has dimension less than the number of cells, and for generic TT we get Z∩OF=∅Z \cap O_F = \varnothing. For FF the whole box the same computation gives dd independent conditions, so I={(T,y):y∈Σ∘, ℓ1=⋯=ℓd=0}I=\{(T,y): y \in\Sigma^\circ,\ \ell_1=\cdots=\ell_d=0\} is a vector bundle over Σ∘\Sigma^\circ, smooth and irreducible, of dimension equal to the number of cells. Its projection to TT is dominant, since for the rank-one tensor Tc=τ1−r∏kμc(k)T_c=\tau^{1-r}\prod_k\mu_c^{(k)} the point y=1y=1 lies in ZZ and is a simple zero (for positive μ\mu, every positive TT has a positive solution), so it is generically finite and, by generic smoothness, has reduced generic fibers. With no zeros on the boundary of Σ\Sigma, Bernstein’s theorem [2] counts the torus zeros, with multiplicity, as the normalized volume of Δn1−1×⋯×Δnr−1\Delta_{n_1-1}\times\cdots\times\Delta_{n_r-1}, which is deg⁡Σ=N\deg\Sigma=N. Finally, a point of Z∩Σ∘Z\cap\Sigma^\circ with σ=0\sigma=0 annihilates f=∑ctc∏jucj(j)f=\sum_c t_c\prod_j u_{c_j}^{(j)} and all of its logarithmic derivatives ui(k)∂f/∂ui(k)u_i^{(k)}\partial f/\partial u_i^{(k)}, so it is a singular point of {f=0}\{f=0\} in the torus; that happens only for TT in a proper closed subset (the closure of this set is the dual variety). □

The main theorem

For a multidegree a=(a1,…,ar)a=(a_1,\ldots,a_r) let S(a)S(a) be the space of polynomials of multidegree aa in the variables u(1),…,u(r)u^{(1)},\ldots,u^{(r)}, so dim⁡S(a)=∏j(aj+kjkj)\dim S(a)=\prod_j\binom{a_j+k_j}{k_j}. Put K0=0K_0=0, Kj=k1+⋯+kjK_j=k_1+\cdots+k_j (j≥1j\ge1), and

m=(m1,…,mr),mj=1+Kj−1.m=(m_1,\ldots,m_r),\qquad m_j=1+K_{j-1}.

Each ℓs\ell_s has multidegree 11. The Sylvester map is

Φ(x):S(m−1)⊕(d+1)⟶S(m),(g1,…,gd,gx)⟼∑s=1dgsℓs+gxℓx.\Phi(x):S(m-1)^{\oplus(d+1)}\longrightarrow S(m),\qquad(g_1,\ldots,g_d,g_x)\longmapsto\sum_{s=1}^{d}g_s\ell_s+g_x\ell_x.

Explicitly, in monomial bases (rows indexed by monomials uau^a of multidegree mm, columns by pairs (s,ub)(s,u^b) with ubu^b of multidegree $m-1), the entry in row uau^a and column (s,ub)(s,u^b) is the coefficient of ycy_c in ℓs\ell_s if ua=ubycu^a=u^b y_c for a cell cc, and $0$ otherwise. Thus every entry is 00, (δck,i−μi(k)/τ)tc(\delta_{c k,i}-\mu_i^{(k)}/\tau)t_c, or δc,1t1−(x/τ)tc\delta_{c,1}t_1-(x/\tau)t_c.

Lemma 3.1. Φ(x)\Phi(x) is square, of size (d+1)N(d+1)N, and xx enters only the N=dim⁡S(m−1)N=\dim S(m-1) columns of the last summand, linearly.

Proof. dim⁡S(m−1)=∏j(Kjkj)=N\dim S(m-1)=\prod_j\binom{K_j}{k_j}=N. Since (1+Kjkj)=(Kjkj)1+Kj1+Kj−1\binom{1+K_j}{k_j}=\binom{K_j}{k_j}\frac{1+K_j}{1+K_{j-1}}, the product telescopes:

dim⁡S(m)=N∏j1+Kj1+Kj−1=(d+1)N.\dim S(m)=N\prod_j\frac{1+K_j}{1+K_{j-1}}=(d+1)N.

□

Theorem 3.2. For every TT and μ\mu, det⁡Φ(x)=±Res⁡Σ(ℓ1,…,ℓd,ℓx)\det\Phi(x)=\pm\operatorname{Res}_{\Sigma}(\ell_1,\ldots,\ell_d,\ell_x), and when TT and μ\mu are positive this vanishes at x=P1x=P_1. Suppose moreover that ZZ is contained in the dense torus of Σ\Sigma (by Lemma 2.2 this holds for generic TT). Then

det⁡Φ(x)=±Res⁡Σ(ℓ1,…,ℓd,ℓx)=C∏ξ∈Zℓx(ξ)mult⁡ξ=C′∏ξ∈Z, σ(ξ)≠0(x−xξ)mult⁡ξ,\det\Phi(x)=\pm\operatorname{Res}_{\Sigma}(\ell_1,\ldots,\ell_d,\ell_x)=C\prod_{\xi\in Z}\ell_x(\xi)^{\operatorname{mult}_{\xi}}=C'\prod_{\substack{\xi\in Z,\ \sigma(\xi)\ne0}}(x-x_{\xi})^{\operatorname{mult}_{\xi}},

where mult⁡ξ\operatorname{mult}_{\xi} is the intersection multiplicity, ∑ξmult⁡ξ=N\sum_{\xi}\operatorname{mult}_{\xi}=N, xξ=τt1ξ1/σ(ξ)x_{\xi}=\tau t_1\xi_1/\sigma(\xi) is the corner entry of the solution ξ\xi, and C≠0C\ne0 and C′C' do not depend on xx. For generic TT the polynomial det⁡Φ(x)\det\Phi(x) has degree exactly NN, with the corner entries of the NN complex solutions as its roots.

Proof. Res⁡Σ\operatorname{Res}_{\Sigma} is the resultant of type (k1,…,kr;1,…,1)(k_1,\ldots,k_r;1,\ldots,1): an irreducible polynomial in the coefficients of d+1d+1 multilinear forms that vanishes exactly when they have a common zero on Σ\Sigma [8 Ch. 13, §2A]. Since min⁡(kj,1)=1\min(k_j,1)=1 for all jj, by Sturmfels and Zelevinsky [13] (see [8 Ch. 13, Prop. 2.2 and (2.3)]) the resultant equals the determinant of the Sylvester map S(mπ−1)⊗Cd+1→S(mπ)S(m^\pi-1)\otimes\mathbb{C}^{d+1}\to S(m^\pi) for each of the r!r! vectors mjπ=1+∑π(i)<π(j)kim^\pi_j=1+\sum_{\pi(i)<\pi(j)}k_i, one for each permutation π\pi of the factors. For the identity permutation this is our mm, and det⁡Φ=±Res⁡Σ\det\Phi=\pm\operatorname{Res}_{\Sigma} identically in the coefficients of the forms; being a polynomial identity, it holds for our specialized coefficients. At x=P1x=P_1 the forms have the common zero y∗y^* given by the limit, so the resultant vanishes.

When ZZ lies in the torus (it is then finite, being closed in Σ\Sigma), the Poisson formula for sparse resultants [4 Thm. 1.1] gives Res⁡Σ(ℓ1,…,ℓd,f)=C∏ξ∈Zf(ξ)mult⁡ξ\operatorname{Res}_{\Sigma}(\ell_1,\ldots,\ell_d,f)=C\prod_{\xi\in Z}f(\xi)^{\operatorname{mult}_{\xi}} for every ff of multidegree 11. Here CC is a product of powers of directional resultants of ℓ1,…,ℓd\ell_1,\ldots,\ell_d; these are nonzero because ZZ meets no boundary orbit, and CC does not depend on ff. By Bernstein’s theorem [2] the total multiplicity is the normalized volume of Δn1−1×⋯×Δnr−1\Delta_{n_1-1}\times\cdots\times\Delta_{n_r-1}, that is, deg⁡Σ=N\deg\Sigma=N. For f=ℓxf=\ell_x each factor is ℓx(ξ)=t1ξ1−σ(ξ)τ(x)\ell_x(\xi)=t_1\xi_1-\frac{\sigma(\xi)}{\tau(x)}, which is −σ(ξ)τ(x−xξ)-\frac{\sigma(\xi)}{\tau}(x-x_\xi) if σ(ξ)≠0\sigma(\xi)\ne0 and independent of xx otherwise. By Lemma 2.1 the xξx_\xi are the corner entries of the complex solutions. The last sentence follows from Lemma 2.2.

Corollary 3.3 (Eigenvalue form). Write Φ(x)=[M0∣K−xJ]\Phi(x)=[M_0\mid K-xJ], where M0M_0 collects the first dNdN columns and K−xJK-xJ the last NN. Whenever det⁡Φ≢0\det\Phi\not\equiv0 (in particular for generic TT), M0M_0 has full column rank; let the columns of Z0Z_0, with entries in Q(T,μ)\mathbb{Q}(T,\mu), span its left kernel. Then

det⁡Φ(x)=cdet⁡(Z0TK−xZ0TJ).\det\Phi(x)=c\det(Z_0^{\mathsf T}K-xZ_0^{\mathsf T}J).

so P1P_1 is a generalized eigenvalue of an explicit N×NN\times N pencil. More generally, let ξ∈Z\xi\in Z with σ(ξ)≠0\sigma(\xi)\ne0, and suppose xξx_\xi is a simple root of det⁡Φ\det\Phi. Then the left null vector of Φ(xξ)\Phi(x_\xi) is, up to scale, the evaluation h↦h(ξ)h\mapsto h(\xi) on S(m)S(m). So it determines every ratio ui(k)/ui′(k)u_i^{(k)}/u_i^{\prime(k)} of ξ\xi, and hence the whole solution Pξ=τ(ξ)σ(ξ)T∘ξP_\xi=\frac{\tau(\xi)}{\sigma(\xi)}T\circ\xi, with entries in Q(T,μ)(xξ)\mathbb{Q}(T,\mu)(x_\xi). For ξ=y∗\xi=y^* this recovers the limit from P1P_1.

Proof. Multiply Φ\Phi on the left by an invertible matrix whose last NN rows are Z0TZ_0^{\mathsf T}; the result is block triangular. The functional h↦h(ξ)h\mapsto h(\xi) is nonzero, and it kills every ∑gsℓs+gxℓxξ\sum g_s\ell_s+g_x\ell_{x_\xi} because ℓ1,…,ℓd\ell_1,\ldots,\ell_d and ℓxξ\ell_{x_\xi} all vanish at ξ\xi. When the root is simple the left kernel is one-dimensional. Since mk≥1m_k\ge1 for every kk, the monomials of S(m)S(m) include pairs differing by one variable of each mode, and the corresponding ratios of coordinates of the null vector are the ratios ui(k)/ui′(k)u_i^{(k)}/u_i^{\prime(k)}.

Theorem 3.4 (The root of the limit). Let TT and the margins be positive, let P∗P^* be the limit, and let y∗∈Σy^*\in\Sigma be its Segre point. For y∈Σy\in\Sigma write ev⁡y=(ya)a\operatorname{ev}_y=(y^a)_a for the vector of monomials of multidegree mm evaluated at yy, a row vector indexed like the rows of Φ\Phi.

(1) P∗P^* is the only solution with all entries positive, and y∗y^* is a simple point of ZZ.

(2) For x∈Cx\in\mathbb{C}, the left kernel of Φ(x)\Phi(x) contains ev⁡y\operatorname{ev}_y for some y∈Σy\in\Sigma with all coordinates positive if and only if x=P1∗x=P_1^*, and then y=y∗y=y^*. In particular det⁡Φ(P1∗)=0\det\Phi(P_1^*)=0.

(3) If P1∗P_1^* is a simple root of det⁡Φ\det\Phi, its left null vector is, up to scale, positive, which has all entries positive. If moreover ZZ lies in the torus and all roots are simple, then P1∗P_1^* is the only root of det⁡Φ\det\Phi whose left null vector can be scaled to have all entries positive.

Proof. (1) Existence and uniqueness of the positive scaling are classical [12, 7]. To show that y∗y^* is a simple zero, scale y∗y^* so that T∘y∗=P∗T\circ y^*=P^*, and use the coordinates a=log⁡ua=\log u, writing tangent vectors as α=(α(1),…,α(r))\alpha=(\alpha^{(1)},\ldots,\alpha^{(r)}). The directions with α(k)=λk1\alpha^{(k)}=\lambda_k\mathbf{1} for every kk are tangent to the fibers of the cone over Σ\Sigma, so Ty∗ΣT_{y^*}\Sigma is the quotient by them. The derivative of the map a↦a\mapsto (all margins of T∘eaT\circ e^a) at y∗y^* is the symmetric matrix AA of the form q(α)=∑cPc∗(∑kαc(k))2q(\alpha)=\sum_cP_c^*\left(\sum_k\alpha_c^{(k)}\right)^2. Since P∗>0P^{\ast} > 0, AA is positive semidefinite, and Aα=0A\alpha= 0 exactly when ∑kαck(k)=0\sum_k \alpha_{c_k}^{(k)} = 0 for all cc, that is, when α(k)=λk1\alpha^{(k)} = \lambda_k 1 with ∑kλk=0\sum_k \lambda_k = 0.

Now let α\alpha satisfy dℓk,i(α)=0d\ell_{k,i}(\alpha) = 0 for i≥2i \ge2. Summing over ii gives ∑iℓk,i=0\sum_i \ell_{k,i} = 0 identically when ℓk,1\ell_{k,1} is defined by the same formula, so also dℓk,1(α)=0d\ell_{k,1}(\alpha) = 0. As ℓk,i=Mk,i−μi(k)τσ\ell_{k,i} = M_{k,i} - \frac{\mu_i^{(k)}}{\tau}\sigma with Mk,i=∑ck=itcycM_{k,i} = \sum_{c_k=i} t_c y_c, this reads (Aα)i(k)=μi(k)τdσ(α)(A\alpha)_i^{(k)} = \frac{\mu_i^{(k)}}{\tau}d\sigma(\alpha) for all k,ik,i. Let ee be the vector with e(1)=1e^{(1)} = 1 and e(k)=0e^{(k)} = 0 for k≥2k \ge2, so that Ae=(μ(1),…,μ(r))Ae = (\mu^{(1)},\ldots,\mu^{(r)}). Then A(α−dσ(α)τe)=0A\left(\alpha-\frac{d\sigma(\alpha)}{\tau}e\right)=0, so every α(k)\alpha^{(k)} is a multiple of 11, and α\alpha is zero in Ty∗ΣT_{y^\ast}\Sigma. Thus ℓ1,…,ℓd\ell_1,\ldots,\ell_d have independent differentials at y∗y^\ast, and y∗y^\ast is a simple zero.

(2) The entry of ev⁡yΦ(x)\operatorname{ev}_y\Phi(x) in the column (s,ub)(s,u^b) is ybℓs(y)y^b\ell_s(y), with ℓd+1=ℓx\ell_{d+1}=\ell_x. If yy is positive then yb>0y^b>0, so ev⁡y\operatorname{ev}_y lies in the left kernel exactly when ℓ1(y)=⋯=ℓd(y)=ℓx(y)=0\ell_1(y)=\cdots=\ell_d(y)=\ell_x(y)=0. Since σ(y)>0\sigma(y)>0, Lemma 2.1 shows that this means τσ(y)T∘y\frac{\tau}{\sigma(y)}T\circ y is a positive solution with corner entry xx, hence equals P∗P^\ast by (1).

(3) A simple root has a one-dimensional left kernel, which by (2) is spanned by ev⁡y∗\operatorname{ev}_{y^\ast}. For another simple root xξx_\xi, the left null vector is ev⁡ξ\operatorname{ev}_\xi by Corollary 3.3. If it can be scaled to be positive, then all ratios of monomials at ξ\xi are positive. These include all ratios ui(k)/ui′(k)u_i^{(k)}/u_{i'}^{(k)}, so ξ\xi is positive and ξ=y∗\xi=y^\ast.

Thus the limit is distinguished from the other roots by positivity of the whole solution, read off from the null vector of Φ\Phi. When ZZ lies in the torus, (1) shows that the factor x−P1∗x-P_1^\ast occurs in det⁡Φ\det\Phi with multiplicity one unless another complex solution has the same corner entry. Since Theorem 3.2 applies to any entry after permuting the indices, every entry of the limit is a root of a determinant of this kind; when P1∗P_1^\ast is a simple root of det⁡Φ\det\Phi, a single corner determinant and its left null vector already recover all entries of P∗P^\ast via Corollary 3.3.

Remark 3.5. Theorem 3.2 needs no genericity beyond the assumption on ZZ; there are r!r! admissible multidegrees, one for each ordering of the factors, and all give the same determinant up to sign.

Leading and constant coefficients

Write R(x)=det⁡Φ(x)R(x)=\det\Phi(x). We treat the entries tct_c as indeterminates and the margins as coordinates on the linear space of margin vectors with a common total τ\tau, so the coefficients of RR lie in Q[T,μ][τ±1]\mathbb{Q}[T,\mu][\tau^{\pm1}]; “up to a unit” means up to a factor qτeq\tau^e with q∈Q×q\in\mathbb{Q}^{\times}, e∈Ze\in\mathbb{Z}. Let A={ec}⊂Zn1⊕⋯⊕ZnrA=\{e_c\}\subset\mathbb{Z}^{n_1}\oplus\cdots\oplus\mathbb{Z}^{n_r} be the vertex set of Δn1−1×⋯×Δnr−1\Delta_{n_1-1}\times\cdots\times\Delta_{n_r-1}. For a face F=F1×⋯×FrF=F_1\times\cdots\times F_r (∅≠Fj⊆[nj])(\varnothing\ne F_j\subseteq[n_j]) let TFT_F be the corresponding subtensor and Disc⁡F(T)\operatorname{Disc}_F(T) its AA-discriminant ΔA∩F\Delta_{A\cap F}: tct_c for a cell, the k×kk\times k minor for a square face of a matrix, Cayley’s hyperdeterminant for a 2×2×22\times2\times2 face, and in general the hyperdeterminant of TFT_F when it is nontrivial (and 11 otherwise) [8]. The principal AA-determinant is EA(T)=∏FDisc⁡F(T)E_A(T)=\prod_F\operatorname{Disc}_F(T), with all multiplicities equal to one because the toric variety XA=ΣX_A=\Sigma is smooth [8 Ch. 10, Thm. 1.2].

Theorem 4.1. Up to a unit, the leading coefficient of R(x)R(x) is EA(T)E_A(T); in particular it does not depend on the margins except through a power of τ\tau.

Proof. The coefficient of xNx^N is (−1/τ)NRes⁡(ℓ1,…,ℓd,σ)(-1/\tau)^N\operatorname{Res}(\ell_1,\ldots,\ell_d,\sigma). A resultant is unchanged by adding to one form a multiple of another of the same multidegree, so we may replace ℓk,i\ell_{k,i} by Mk,i(y)=∑ck=itcycM_{k,i}(y)=\sum_{c_k=i}t_cy_c, which removes μ\mu. Write f(u)=∑ctc∏jucj(j)f(u)=\sum_ct_c\prod_j u_{c_j}^{(j)}, the polynomial with support AA and coefficients TT. Then σ=f\sigma=f and Mk,i=ui(k)∂f/∂ui(k)M_{k,i}=u_i^{(k)}\partial f/\partial u_i^{(k)}, and together these span the space of all logarithmic derivatives of ff and ff itself (the omitted i=1i=1 derivatives are determined by the Euler relations ∑iui(k)∂f/∂ui(k)=f\sum_i u_i^{(k)} \partial f/\partial u_i^{(k)}=f. The AA-resultant is the resultant on the toric variety XA=ΣX_A=\Sigma, so Res⁡Σ(M,σ)\operatorname{Res}_{\Sigma}(M,\sigma) is, up to a nonzero constant, the principal AA-determinant EA(f)=RA(u ∂f/∂u,f)E_A(f)=R_A\left(u\,\partial f/\partial u,f\right) as defined in [8 Ch. 10, (1.1)]. By [8 Ch. 10, Thm. 1.2], since XA=ΣX_A=\Sigma is smooth, it is the product of the discriminants of all faces, each to the first power. □

Corollary 4.2. The degree of RR is less than NN exactly on the hypersurface EA(T)=0E_A(T)=0, that is, when some face of TT has vanishing hyperdeterminant (or minor, or entry).

The faces through the corner and the others play different roles.

Proposition 4.3. *If FF does not contain the corner, then Disc⁡F(T)\operatorname{Disc}_F(T) divides every coefficient of R(x)R(x). *

Proof. For generic TT with Disc⁡F(T)=0\operatorname{Disc}_F(T)=0, the restriction of ff to the face FF has a singular point in its torus, since by definition {Disc⁡F=0}\{\operatorname{Disc}_F=0\} is the closure of the set of such coefficient vectors [8 Ch. 9, (1.1) and Def. 1.2]. This gives a point ξ∈Σ\xi\in\Sigma in the torus orbit of FF at which ff and all its logarithmic derivatives vanish, that is, all margins of T∘ξT\circ\xi are zero. So σ(ξ)=0\sigma(\xi)=0 and every ℓk,i(ξ)=0\ell_{k,i}(\xi)=0. Since 1∉F1\notin F, also ξ1=0\xi_1=0, hence ℓx(ξ)=0\ell_x(\xi)=0 for every xx, and R≡0R\equiv0. As this holds on a dense subset of the hypersurface Disc⁡F=0\operatorname{Disc}_F=0, the irreducible polynomial Disc⁡F\operatorname{Disc}_F divides RR as a polynomial in TT and xx, and being free of xx it divides each coefficient. □

Proposition 4.4. For 1≤k≤r1\leq k\leq r let T(k)T^{(k)} be the slab {tc:ck≥2}\{t_c:c_k\geq2\}, of format n1×⋯×(nk−1)×⋯×nrn_1\times\cdots\times(n_k-1)\times\cdots\times n_r, let AkA_k be its vertex configuration, and let Nk=(k1,…,kk−1,kk+1,…,kr)N_k=\left(k_1,\ldots,k_{k-1},k_{k+1},\ldots,k_r\right) be the degree of Σk=Σ∩{u1(k)=0}\Sigma_k=\Sigma\cap\{u_1^{(k)}=0\}. Up to a unit,

R(0)=t1N∏k=1r(μ1(k))NkEAk(T(k)).R(0)=t_1^N\prod_{k=1}^{r}\left(\mu_1^{(k)}\right)^{N_k}E_{A_k}\left(T^{(k)}\right).

Proof. At x=0x=0, ℓx=t1u1(1)⋯u1(r)\ell_x=t_1u_1^{(1)}\cdots u_1^{(r)}. The resultant is multiplicative in its last argument, and Res⁡Σ(ℓ1,…,ℓd,u1(k))=±Res⁡Σk(ℓ1∣Σk,…,ℓd∣Σk)\operatorname{Res}_{\Sigma}(\ell_1,\ldots,\ell_d,u_1^{(k)})=\pm\operatorname{Res}_{\Sigma_k}(\ell_1|_{\Sigma_k},\ldots,\ell_d|_{\Sigma_k}), so R(0)=±t1N∏kRkR(0)=\pm t_1^N\prod_kR_k with RkR_k the latter resultant. On Σk\Sigma_k only cells of T(k)T^{(k)} survive. Write σk\sigma_k and Mj,i(k)=∑c∈T(k), cj=itcycM_{j,i}^{(k)}=\sum_{c\in T^{(k)},\,c_j=i}t_cy_c for the restricted total and margin forms. For mode kk the restricted forms ℓk,i∣Σk=Mk,i(k)−μi(k)τσk\ell_{k,i}|_{\Sigma_k}=M_{k,i}^{(k)}-\frac{\mu_i^{(k)}}{\tau}\sigma_k (2≤i≤nk2\leq i\leq n_k) sum to μ1(k)τσk\frac{\mu_1^{(k)}}{\tau}\sigma_k, and the matrix taking (Mk,i(k))i≥2(M_{k,i}^{(k)})_{i\geq2} to them has determinant μ1(k)/τ\mu_1^{(k)}/\tau. So, after a triangular change of basis of determinant μ1(k)/τ\mu_1^{(k)}/\tau, the dd restricted forms become σk\sigma_k, Mk,i(k)M_{k,i}^{(k)} (i≥3i\geq3) and Mj,i(k)M_{j,i}^{(k)} (j≠kj\neq k, i≥2i\geq2); the other modes are handled by subtracting multiples of σk\sigma_k. Since Res⁡Σk\operatorname{Res}_{\Sigma_k} has degree NkN_k in each argument, Rk=±(μ1(k)/τ)NkRes⁡Σk(M(k),σk)R_k=\pm(\mu_1^{(k)}/\tau)^{N_k}\operatorname{Res}_{\Sigma_k}(M^{(k)},\sigma_k), and the last resultant is, up to a nonzero constant, EAk(T(k))E_{A_k}(T^{(k)}), exactly as in the proof of Theorem 4.1. □

Thus both extreme coefficients of RR are products of face discriminants. In particular R(0)≠0R(0)\neq0 for generic TT and any margins with μ1(k)≠0\mu_1^{(k)}\neq0.

Theorem 4.5. Fix margins with τ≠0\tau\neq0 and all μi(k)≠0\mu_i^{(k)}\neq0. As a polynomial in xx, R(x)R(x) has content, up to a unit,

c(T)=t1∏F∌1Disc⁡F(T),c(T)=t_1\prod_{F\not\ni1}\operatorname{Disc}_F(T),

the product over all faces not containing the corner (including the vertices tct_c, c≠1c\neq1). Consequently R=c(T)E~T(x)R=c(T)\widetilde E_T(x), where E~T\widetilde E_T is primitive of degree NN; up to a unit, its leading coefficient

and constant term are

∏F∋1,F≠{1}Disc⁡F(T)andt1N−1∏k(μ1(k))Nk∏F∌1Disc⁡F(T)eF−1.\prod_{\substack{F \ni1,\\ F \ne\{1\}}} \operatorname{Disc}_{F}(T) \qquad\text{and}\qquad t_{1}^{N-1}\prod_k \left(\mu_1^{(k)}\right)^{N_k}\prod_{F \not\ni1}\operatorname{Disc}_{F}(T)^{e_F-1}.

where eF=#{k:1∉Fk}e_F=\#\{k:1\notin F_k\}. Moreover E~T\widetilde{E}_T is a power of an irreducible polynomial in C[T,x]\mathbb{C}[T,x].

Proof. The content divides the leading coefficient EA(T)E_A(T) (Theorem 4.1). This is squarefree and free of μ\mu, and it is a product of irreducible face discriminants that are pairwise non-associate, since each Disc⁡F\operatorname{Disc}_F involves exactly the variables tct_c, c∈Fc\in F (see below). So c=∏F∈SDisc⁡Fc=\prod_{F\in S}\operatorname{Disc}_F for some set SS of faces. Proposition 4.3 gives F∈SF\in S for every F∌1F\not\ni1. At t1=0t_1=0 we have ℓx=−xτ\ell_x=-\frac{x}{\tau}, so R=(−xτ)NEA(T)∣t1=0=0R=\left(-\frac{x}{\tau}\right)^N E_A(T)|_{t_1=0}=0, since t1t_1 is a factor of EAE_A; hence {1}∈S\{1\}\in S. Now let F∋1F\ni1 be a face of positive dimension with nontrivial discriminant. Disc⁡F\operatorname{Disc}_F is irreducible [8 Ch. 9, Def. 1.2] and invariant up to sign under permutations of the indices within each mode of FF. These permutations act transitively on the cells of FF, so the nonconstant polynomial Disc⁡F\operatorname{Disc}_F involves every tct_c with c∈Fc\in F, in particular t1t_1. By Proposition 4.4, R(0)R(0) is a nonzero polynomial whose only dependence on t1t_1 is the factor t1N−1t_1^{N-1}, since the slabs do not contain the corner. An irreducible polynomial involving t1t_1 and not associate to t1t_1 cannot divide it. Hence F∉SF\notin S.

The formula for E~T(0)=R(0)/c(T)\widetilde{E}_T(0)=R(0)/c(T) follows from Proposition 4.4. Every face F∌1F\not\ni1 lies in exactly the eF≥1e_F\ge1 slabs T(k)T^{(k)} with 1∉Fk1\notin F_k, and EAk(T(k))E_{A_k}(T^{(k)}) is the product of the discriminants of the faces of T(k)T^{(k)}.

For the last claim, let II be the incidence variety of Lemma 2.2. It is irreducible, and its projection to TT has degree NN with reduced generic fibers. By Theorem 3.2, E~T\widetilde{E}_T is, up to its leading coefficient, the norm of X−xX-x from the function field of II to C(T)\mathbb{C}(T), which is a power of the minimal polynomial of xx. □

Remark 4.6 (Degenerate tensors). For special positive TT the full determinant RR can vanish identically. For instance, by Proposition 4.3 this happens for a 3×33\times3 matrix with a vanishing 2×22\times2 minor away from the (1,1)(1,1) entry. The right object is therefore E~T\widetilde{E}_T. Since the limit depends continuously on TT, the identity E~T(P1)=0\widetilde{E}_T(P_1)=0, valid for generic TT, holds for every positive TT. The coefficients of E~T\widetilde{E}_T have no common factor, so E~T≢0\widetilde{E}_T\not\equiv0 outside a subset of codimension at least two.

Matrices

For r=2r=2, Theorem 3.2 gives an N×NN\times N pencil with N=(m+n−2m−1)N=\binom{m+n-2}{m-1} whose determinant is the eliminant of the top-left entry. The faces with nontrivial discriminant are then exactly the square submatrices, so the coefficients in § 4 are products of minors: the leading coefficient of E~T\widetilde{E}_T is the product of the minors of size at least two that contain t11t_{11}, and the minors avoiding both the first row and the first column enter its constant term. Rowland and Wu [11] found, and Fang [6] proved, a diagonal form of this eliminant, in which the matrix enters only through minors on a diagonal and the margins only through an integer-coefficient matrix. Two regular pencils with the same simple eigenvalues are equivalent, so for generic TT the two forms differ by a change of basis; we give a short proof of this formula.

Plücker coordinates and derivations. Let e1,…,eMe_1,\ldots,e_M be the standard basis of CM\mathbb{C}^M, totally ordered. For a kk-subset J={j1<⋯<jk}J=\{j_1<\cdots<j_k\} write eJ=ej1∧⋯∧ejke_J=e_{j_1}\wedge\cdots\wedge e_{j_k}. The Plücker vector of the row space VV of a full-rank k×Mk\times M matrix WW is ω=∑JωJeJ\omega=\sum_J\omega_J e_J, with ωJ\omega_J the maximal minor of WW on the columns JJ. A matrix LL acts on ⋀kCM\bigwedge^k\mathbb{C}^M as the derivation DL(v1∧⋯∧vk)=∑iv1∧⋯∧Lvi∧⋯∧vkD_L(v_1\wedge\cdots\wedge v_k)=\sum_i v_1\wedge\cdots\wedge Lv_i\wedge\cdots\wedge v_k.

Lemma 5.1. In the basis (eJ)(e_J), (DL)J,J=∑a∈JLaa(D_L)_{J,J} = \sum_{a\in J} L_{aa}; if J′=J∖{b}∪{a}J' = J \setminus\{b\} \cup\{a\} with b∈Jb \in J, a∉Ja \notin J, then (DL)J,J′=sgn⁡(J,J′)Lba(D_L)_{J,J'} = \operatorname{sgn}(J,J')L_{ba} with sgn⁡(J,J′)=(−1)#{z∈J∩J′:min⁡(a,b)<z<max⁡(a,b)}\operatorname{sgn}(J,J') = (-1)^{\#\{z\in J\cap J':\min(a,b)<z<\max(a,b)\}}; all other entries vanish.

Proof. The term of DLeJ′D_L e_{J'} contributing to eJe_J replaces eae_a by ebe_b; sorting moves ebe_b past exactly the elements of J∩J′J\cap J' strictly between aa and bb. □

Lemma 5.2. If g∈Vg \in V then Dgq⊤ω=(q⋅g)ωD_g q^\top\omega= (q\cdot g)\omega; if q⊥Vq \perp V then Dgq⊤ω=0D_g q^\top\omega= 0.

Proof. With ω=v1∧⋯∧vk\omega= v_1 \wedge\cdots\wedge v_k, Dgq⊤ω=∑i(q⋅vi)v1∧⋯∧g∧⋯∧vkD_g q^\top\omega= \sum_i(q\cdot v_i)v_1\wedge\cdots\wedge g\wedge\cdots\wedge v_k. If q⊥Vq\perp V every term vanishes; if g∈Vg\in V take v1=gv_1=g. □

Let T∈R>0m×nT\in\mathbb{R}^{m\times n}_{>0} with row targets ρ=μ(1)\rho=\mu^{(1)} and column targets κ=μ(2)\kappa=\mu^{(2)}. Index Cm+n\mathbb{C}^{m+n} by 1<⋯<m<1′<⋯<n′1<\cdots<m<1'<\cdots<n', let ωJ(B)\omega_J(B) be the maximal minor of [Im∣B][I_m\mid B] on the columns JJ, and put

α=(1m,κ),β=(−ρ,1n),L=αβ⊤+ρ1αe1⊤−κ1e1β⊤.\alpha=(\mathbf{1}_m,\kappa),\qquad\beta=(-\rho,\mathbf{1}_n),\qquad L=\alpha\beta^\top+\rho_1\alpha e_1^\top-\kappa_1e_1\beta^\top.

The link L\mathcal{L} is the set of mm-subsets JJ with 1′∈J1'\in J, 1∉J1\notin J; it corresponds to pairs I={2,…,m}∖JI=\{2,\ldots,m\}\setminus J and K={k∈{2,…,n}:k′∈J}K=\{k\in\{2,\ldots,n\}:k'\in J\} with ∣I∣=∣K∣|I|=|K|, so ∣L∣=N|\mathcal{L}|=N. For J∈LJ\in\mathcal{L} let J∗=J∖{1′}∪{1}J^*=J\setminus\{1'\}\cup\{1\}, Q=(DL−ρ1)L×LQ=(D_L-\rho_1)_{\mathcal{L}\times\mathcal{L}}, and sJ=(DL)J,J∗s_J=(D_L)_{J,J^*}. By Lemma 5.1, QJ,J=∑k∈Kκk−∑i∈[m]∩Jρi−ρ1Q_{J,J}=\sum_{k\in K}\kappa_k-\sum_{i\in[m]\cap J}\rho_i-\rho_1, QJ,J′=sgn⁡(J,J′)αbβaQ_{J,J'}=\operatorname{sgn}(J,J')\alpha_b\beta_a for exchanges avoiding 1,1′1,1', and sJ=(−1)m−1−∣I∣ρ1κ1s_J=(-1)^{m-1-|I|}\rho_1\kappa_1.

Theorem 5.3 ([6]). With Δ^J=ωJ(T)\widehat{\Delta}_J=\omega_J(T) and Γ^J=sJt11ωJ∗(T)\widehat{\Gamma}_J=s_Jt_{11}\omega_{J^*}(T), the top-left entry x=p11x=p_{11} of the limit is a root of

F(x)=det⁡(diag⁡(Γ^)+xdiag⁡(Δ^)Q).F(x)=\det\left(\operatorname{diag}(\widehat{\Gamma})+x\operatorname{diag}(\widehat{\Delta})Q\right).

Proof. Let VV be the row space of [I∣P][I\mid P] with Plücker vector ω\omega. The margins say α∈V\alpha\in V and β⊥V\beta\perp V, so Lemma 5.2 gives DLω=(β⋅α+ρ1)ω=ρ1ωD_L\omega=(\beta\cdot\alpha+\rho_1)\omega=\rho_1\omega. For J∈LJ\in\mathcal{L} the coordinates J′∉LJ'\notin\mathcal{L} that can occur in (DLω)J(D_L\omega)_J come from b=1′b=1' or a=1a=1, where L1′,a=0L_{1',a}=0 (a≠1a\ne1) and Lb,1=0L_{b,1}=0 (b≠1′b\ne1'); hence ∑J′∈LQJ,J′ωJ′(P)+sJωJ∗(P)=0\sum_{J'\in\mathcal{L}}Q_{J,J'}\omega_{J'}(P)+s_J\omega_{J^*}(P)=0. Since [I∣P]=diag⁡(λ)[I∣T]diag⁡(λ−1,ν)[I\mid P]=\operatorname{diag}(\lambda)[I\mid T]\operatorname{diag}(\lambda^{-1},\nu), each ωJ(P)\omega_J(P) is ωJ(T)\omega_J(T) times a torus character, and ωJ∗(P)ωJ(T)=t11xωJ∗(T)ωJ(P)\omega_{J^*}(P)\omega_J(T)=\frac{t_{11}}{x}\omega_{J^*}(T)\omega_J(P). Multiplying the row by xωJ(T)x\omega_J(T) shows that w=(ωJ(P))J∈L≠0w=(\omega_J(P))_{J\in\mathcal{L}}\ne0 lies in the kernel. □

Proposition 5.4. Let E={2,…,m}∪{2′,…,n′}E=\{2,\ldots,m\}\cup\{2',\ldots,n'\} and Θ=diag⁡((−1)#(J∩[m]))\Theta=\operatorname{diag}((-1)^{\#(J\cap[m])}). Under J↦J∖{1′}J\mapsto J\setminus\{1'\}, ΘQΘ=ε(αE)ι(βE)−ρ1\Theta Q\Theta=\varepsilon(\alpha_E)\iota(\beta_E)-\rho_1 on ⋀m−1CE\bigwedge^{m-1}\mathbb{C}^E, where ε(v)=v∧⋅\varepsilon(v)=v\wedge\cdot and ι(β)\iota(\beta) is contraction with β\beta, and (ει)2=(βE⋅αE)ει(\varepsilon\iota)^2=(\beta_E\cdot\alpha_E)\varepsilon\iota with βE⋅αE=ρ1−κ1\beta_E\cdot\alpha_E=\rho_1-\kappa_1. Hence QQ has eigenvalues −κ1-\kappa_1 and −ρ1-\rho_1 with multiplicities (m+n−3m−2)\binom{m+n-3}{m-2} and (m+n−3m−1)\binom{m+n-3}{m-1} (understood as a single eigenvalue of multiplicity NN when ρ1=κ1\rho_1=\kappa_1).

Proof. Away from 1,1′1,1', L=αβ⊤L=\alpha\beta^\top, and the sign difference caused by 1′1' is corrected by Θ\Theta; Dαβ⊤=ε(α)ι(β)D_{\alpha\beta^\top}=\varepsilon(\alpha)\iota(\beta). From ιε+ει=β⋅α\iota\varepsilon+\varepsilon\iota=\beta\cdot\alpha and ε2=0\varepsilon^2=0 we get (ει)2=(β⋅α)ει(\varepsilon\iota)^2=(\beta\cdot\alpha)\varepsilon\iota, and the trace of ει\varepsilon\iota on ⋀m−1Cm+n−2\bigwedge^{m-1}\mathbb{C}^{m+n-2} is (β⋅α)(m+n−3m−2)(\beta\cdot\alpha)\binom{m+n-3}{m-2}. □

In particular QQ is invertible, so the leading coefficient of FF is det⁡Q∏J∈LωJ(T)\det Q\prod_{J\in\mathcal{L}}\omega_J(T), with det⁡Q=±κ1(m+n−3m−2)ρ1(m+n−3m−1)\det Q=\pm\kappa_1^{\binom{m+n-3}{m-2}}\rho_1^{\binom{m+n-3}{m-1}}. Up to sign, ωJ(T)\omega_J(T) is the minor of TT on the rows [m]∖J[m]\setminus J and the columns J∩{1′,…,n′}J\cap\{1',\ldots,n'\}. As JJ runs over L\mathcal{L}, these are exactly the NN square submatrices containing the entry t11t_{11}, including t11t_{11} itself. Since FF and E^T\widehat{E}_T have the same degree NN and the same roots for generic TT, comparing leading coefficients shows that F(x)F(x) equals t11(det⁡Q)E^T(x)t_{11}(\det Q)\widehat{E}_T(x) up to a unit, leaving the product of the minors of size at least two through the corner as the leading coefficient of E^T\widehat{E}_T, in agreement with Theorem 4.5.

The other roots

Kruithof’s method and Sinkhorn’s algorithm look for positive factors u(1),…,u(r)u^{(1)},\ldots,u^{(r)} such that P(u)=T∘(u(1)⊗⋯⊗u(r))P(u)=T\circ\left(u^{(1)}\otimes\cdots\otimes u^{(r)}\right) has the prescribed margins. The other roots of det⁡Φ\det\Phi arise in the same way once the factors are allowed to be arbitrary nonzero complex numbers. Write G={(λ1,…,λr):∏kλk=1}G=\{(\lambda_1,\ldots,\lambda_r):\prod_k\lambda_k=1\} for the torus of rescalings that do not change P(u)P(u), and consider the dual potential

f(u)=∑k=1r∑i=1nkμi(k)log⁡ui(k)−∑cP(u)cf(u)=\sum_{k=1}^{r}\sum_{i=1}^{n_k}\mu_i^{(k)}\log u_i^{(k)}-\sum_cP(u)_c

on (C×)n1+⋯+nr(\mathbb{C}^{\times})^{n_1+\cdots+n_r}. The logarithms are multivalued, but dfdf is not: ui(k)∂f/∂ui(k)=μi(k)−∑ck=iP(u)cu_i^{(k)}\partial f/\partial u_i^{(k)}=\mu_i^{(k)}-\sum_{c_k=i}P(u)_c.

Proposition 6.1.

(1) For every TT, if u(k)∈(C×)nku^{(k)}\in(\mathbb{C}^{\times})^{n_k} are such that P(u)P(u) has the prescribed margins, then P(u)1P(u)_1 is a root of det⁡Φ\det\Phi, and the left kernel of Φ(P(u)1)\Phi(P(u)_1) contains the evaluation at u(1)⊗⋯⊗u(r)u^{(1)}\otimes\cdots\otimes u^{(r)}.

(2) For generic TT there are exactly NN such complex solutions modulo GG, all simple, and their corner entries are the roots of det⁡Φ\det\Phi, counted with multiplicity. When E~T\widetilde{E}_T is irreducible these roots are the Galois conjugates of P1∗P_1^* over Q(T,μ)\mathbb{Q}(T,\mu).

(3) The complex solutions are exactly the critical points of ff, modulo GG.

(4) If TT and μ\mu are positive and a solution PP is real, there are signs s(k)∈{±1}nks^{(k)}\in\{\pm1\}^{n_k} with sign⁡(Pc)=∏ksck(k)\operatorname{sign}(P_c)=\prod_k s_{c_k}^{(k)} for all cc. Then PP is a positive scaling, with the prescribed margins, of the sign-twisted tensor Ts=T∘(s(1)⊗⋯⊗s(r))T^s=T\circ\left(s^{(1)}\otimes\cdots\otimes s^{(r)}\right), and a critical point of

fs(a)=∑k,iμi(k)ai(k)−∑cTcseac1(1)+⋯+acr(r),a∈Rn1+⋯+nr.f_s(a)=\sum_{k,i}\mu_i^{(k)}a_i^{(k)}-\sum_cT_c^s e^{a_{c_1}^{(1)}+\cdots+a_{c_r}^{(r)}},\qquad a\in\mathbb{R}^{n_1+\cdots+n_r}.

For trivial ss, fsf_s is strictly concave modulo GG and its unique critical point is the limit. The twisted tensors TsT^s have the same complex solutions as TT, and hence the same roots.

Proof. (1) The point ξ=u(1)⊗⋯⊗u(r)\xi=u^{(1)}\otimes\cdots\otimes u^{(r)} lies in the torus of Σ\Sigma, and ℓ1,…,ℓd\ell_1,\ldots,\ell_d and ℓx\ell_x with x=P(u)1x=P(u)_1 vanish at ξ\xi by Lemma 2.1. So ev⁡ξ≠0\operatorname{ev}_{\xi}\ne0 lies in the left kernel of Φ(x)\Phi(x), as in the proof of Theorem 3.4(2). (2) This is Theorem 3.2 together with Lemma 2.2; the roots of an irreducible polynomial are conjugate. (3) This follows from the formula for dfdf. (4) If PP is real then so is the rank-one tensor P/T=u(1)⊗⋯⊗u(r)P/T=u^{(1)}\otimes\cdots\otimes u^{(r)}, so after a rescaling in GG every u(k)u^{(k)} is real. Write u(k)=s(k)ea(k)u^{(k)}=s^{(k)}e^{a^{(k)}} coordinatewise. For trivial ss, fsf_s is linear minus a positive combination of exponentials of the linear forms ac1(1)+⋯+acr(r)a_{c_1}^{(1)}+\cdots+a_{c_r}^{(r)}, which vanish simultaneously only in the directions of GG. Finally, Ts∘(u(1)⊗⋯⊗u(r))=T∘((s(1)u(1))⊗⋯⊗(s(r)u(r)))T^s\circ\left(u^{(1)}\otimes\cdots\otimes u^{(r)}\right)=T\circ\left((s^{(1)}u^{(1)})\otimes\cdots\otimes(s^{(r)}u^{(r)})\right). □

Algebraically, the limit is on the same footing as the other complex solutions; only positivity selects it (Theorem 3.4). The number NN of complex solutions is the maximum likelihood degree of the scaled Segre variety [1].

Remarks

Remark 7.1 (Higher marginals). Iterative proportional fitting with prescribed marginals of higher order (a hierarchical log-linear model with configuration A′A') has the same structure: the margin conditions are linear in yy, and yy ranges over the toric variety XA′X_{A'}. The corner entry of the limit is then a root of the A′A'-resultant of the margin forms and ℓx\ell_x, which is the Chow form of XA′X_{A'} evaluated at the margin space and has degree at most deg⁡XA′\deg X_{A'} in xx. In the Segre case, Sturmfels and Zelevinsky [13] make this a single determinant. In general one needs Macaulay-type quotient formulas for sparse resultants [3].

Remark 7.2 (Open questions). For matrices, the diagonal form of Theorem 5.3 separates the dependence on TT (Plücker coordinates) from the dependence on the margins (the operator QQ). It would be interesting to find a basis with the same property for tensors. The irreducibility of E~T\widetilde{E}_T in every format (equivalently, by Theorem 4.5, whether the corner entries xξx_{\xi} of the NN generic complex solutions are distinct), the Galois group of E~T\widetilde{E}_T over Q(T,μ)\mathbb{Q}(T,\mu), and the behavior for tensors with prescribed zero patterns are also open.

Appendix A. Examples

We illustrate Theorem 3.4 and Proposition 6.1. The corner entry of every positive tensor with margins μ(k)\mu^{(k)} lies in I=(0,min⁡kμ(k))I=(0,\min_k\mu^{(k)}) (since the entries are positive and the slice sums through the corner equal μ(1)\mu^{(1)}). In Examples A.1–A.3, E~T\widetilde{E}_T has several roots in II. For each real root xx we list the sign vectors s(1),…,s(r)s^{(1)},\ldots,s^{(r)} of the real solution with corner entry xx (Proposition 6.1(4)), normalized by s1(k)=+s_1^{(k)}=+ for k≥2k\ge2. By Theorem 3.4, the corner entry of the limit is the unique root whose sign vectors are all positive. Polynomials printed in full are normalized as in Theorem 4.5. Numerical values are rounded to the digits shown.

Example A.1. Let

T=(391329534),ρ=κ=(1,1,1),T=\begin{pmatrix}3&9&1\\3&2&9\\5&3&4\end{pmatrix},\qquad\rho=\kappa=(1,1,1),

as in [11 Example 1]. Then N=6N=6, I=(0,1)I=(0,1), and

E~T(x)=30354912x6−17851428x5−68393079x4−10189476x3+17082657x2+1162026x−997272,\widetilde{E}_T(x)=30354912x^6-17851428x^5-68393079x^4-10189476x^3\\ {}+17082657x^2+1162026x-997272,

which is the polynomial given by [11 Theorem 3] for this TT. The leading coefficient is (−21)⋅24⋅(−36)⋅7⋅239(-21)\cdot24\cdot(-36)\cdot7\cdot239, the product of the four 2×22\times2 minors containing t11t_{11} and det⁡T\det T. The constant term is t11ρ15κ13⋅t22t23t32t33⋅(t22t33−t23t32)=35⋅216⋅(−19)t_{11}\rho_1^5\kappa_1^3\cdot t_{22}t_{23}t_{32}t_{33}\cdot(t_{22}t_{33}-t_{23}t_{32})=3^5\cdot216\cdot(-19). The polynomial is irreducible over Q\mathbb{Q}, and its roots are

xxs(1)s^{(1)}s(2)s^{(2)}
−0.7859741748-0.7859741748(−,+,+)(-,+,+)(+,−,+)(+,-,+)
−0.7765360630-0.7765360630(−,−,+)(-,-,+)(+,−,−)(+,-,-)
−0.3038869398-0.3038869398(−,−,+)(-,-,+)(+,−,−)(+,-,-)
0.27667711620.2766771162(+,+,+)(+,+,+)(+,+,+)(+,+,+)
0.35032942910.3503294291(+,−,+)(+,-,+)(+,+,−)(+,+,-)
1.8274808891.827480889(+,−,−)(+,-,-)(+,+,−)(+,+,-)

Table 1.

Two roots lie in II, and only one has all sign vectors positive. By Theorem 3.4, P11∗=0.2766771162P_{11}^*=0.2766771162, as computed in [11], and the left null vector of Φ(P11∗)\Phi(P_{11}^*) gives the whole limit (Corollary 3.3):

P∗=(0.276680.648050.075280.251940.131140.616920.471380.220820.30780).P^*=\begin{pmatrix}0.27668&0.64805&0.07528\\0.25194&0.13114&0.61692\\0.47138&0.22082&0.30780\end{pmatrix}.

Example A.2. Let TT be the 2×2×32 \times2 \times3 tensor with slices

(t1jk)=(438164),(t2jk)=(796954),(t_{1jk}) = \begin{pmatrix} 4 & 3 & 8 \\ 1 & 6 & 4 \end{pmatrix}, \qquad(t_{2jk}) = \begin{pmatrix} 7 & 9 & 6 \\ 9 & 5 & 4 \end{pmatrix},

and let μ(1)=(9,15)\mu^{(1)} = (9,15), μ(2)=(7,17)\mu^{(2)} = (7,17), μ(3)=(7,7,10)\mu^{(3)} = (7,7,10). Then N=12N = 12 and I=(0,7)I = (0,7). The four nonreal roots of E~T\widetilde{E}_T are

−10.41457216±12.96393243i,2.276903026±9.430689749i;-10.41457216 \pm12.96393243i,\qquad2.276903026 \pm9.430689749i;

by Proposition 6.1 they are the corner entries of solutions with nonreal scaling factors. The real roots are

xxs(1)s^{(1)}s(2)s^{(2)}s(3)s^{(3)}
−14.79904486-14.79904486(−,−)(-,-)(+,−)(+,-)(+,+,−)(+,+,-)
0.28857087060.2885708706(+,−)(+,-)(+,−)(+,-)(+,−,+)(+,-,+)
0.55543055970.5554305597(+,−)(+,-)(+,−)(+,-)(+,−,+)(+,-,+)
0.57151811340.5715181134(+,+)(+,+)(+,+)(+,+)(+,+,+)(+,+,+)
1.0585046521.058504652(+,−)(+,-)(+,−)(+,-)(+,−,+)(+,-,+)
1.7512820051.751282005(+,−)(+,-)(+,−)(+,-)(+,−,+)(+,-,+)
10.2063354010.20633540(+,−)(+,-)(+,−)(+,-)(+,−,+)(+,-,+)
13.9832169313.98321693(+,−)(+,-)(+,−)(+,-)(+,−,−)(+,-,-)

Five roots lie in II, and only one has all sign vectors positive. Hence P111∗=0.5715181134P^*_{111} = 0.5715181134.

Example A.3. Let

T=(8297914237452699),ρ=(2,12,4,6),κ=(1,15,2,6).T = \begin{pmatrix} 8 & 2 & 9 & 7 \\ 9 & 1 & 4 & 2 \\ 3 & 7 & 4 & 5 \\ 2 & 6 & 9 & 9 \end{pmatrix}, \qquad\rho= (2,12,4,6), \qquad\kappa= (1,15,2,6).

Then N=(63)=20N = \binom{6}{3} = 20 and I=(0,1)I = (0,1). The polynomial E~T\widetilde{E}_T is irreducible over Q\mathbb{Q}; we omit its coefficients. Two of its roots are not real, namely −0.7139207340±0.2868301405i-0.7139207340 \pm0.2868301405i. Of the eighteen real roots, seven are negative, four are greater than 1, and seven lie in II, of which only one has all sign vectors positive:

xxs(1)s^{(1)}s(2)s^{(2)}
0.017313041450.01731304145(+,+,−,−)(+,+,-,-)(+,−,+,+)(+,-,+,+)
0.044139401350.04413940135(+,+,−,+)(+,+,-,+)(+,−,+,+)(+,-,+,+)
0.057023002750.05702300275(+,+,+,+)(+,+,+,+)(+,+,+,+)(+,+,+,+)
0.095350846450.09535084645(+,+,−,−)(+,+,-,-)(+,−,+,−)(+,-,+,-)
0.20148012250.2014801225(+,+,−,+)(+,+,-,+)(+,−,+,−)(+,-,+,-)
0.27435805970.2743580597(+,+,+,−)(+,+,+,-)(+,+,+,−)(+,+,+,-)
0.74844093560.7484409356(+,+,−,+)(+,+,-,+)(+,−,+,−)(+,-,+,-)

Hence P11∗=0.05702300275P^*_{11} = 0.05702300275.

Example A.4. Let TT be the 2×2×22 \times2 \times2 tensor with tijk=4(i−1)+2(j−1)+kt_{ijk} = 4(i-1) + 2(j-1) + k, that is, with slices

(t1jk)=(1234),(t2jk)=(5678),(t_{1jk}) = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}, \qquad(t_{2jk}) = \begin{pmatrix} 5 & 6 \\ 7 & 8 \end{pmatrix},

and let μ(1)=(1,3)\mu^{(1)} = (1,3), μ(2)=(2,2)\mu^{(2)} = (2,2), μ(3)=(3,1)\mu^{(3)} = (3,1). The 2×22 \times2 minors of TT are nonzero, but its hyperdeterminant vanishes, as it does for every 2×2×22 \times2 \times2 tensor whose entries are affine

functions of the indices. Hence the xNx^N coefficient in Theorem 4.5 vanishes, so deg⁡E~T\deg\widetilde{E}_T drops from 6 to 5:

E~T(x)=−8192x5−142272x4−780288x3−1686368x2−1085952x+387072,\widetilde{E}_T(x)=-8192x^5-142272x^4-780288x^3-1686368x^2-1085952x+387072,

which is irreducible over Q\mathbb{Q}. Its constant term is t111(1⋅2⋅3)2⋅t122t212t221⋅t222=1⋅36⋅168⋅64t_{111}(1\cdot2\cdot3)^2\cdot t_{122}t_{212}t_{221}\cdot t_{222}=1\cdot36\cdot168\cdot64, as in Theorem 4.5. Its roots are real and simple:

xxs(1)s^{(1)}s(2)s^{(2)}s(3)s^{(3)}
−9.395305470-9.395305470(−,+)(-,+)(+,−)(+,-)(+,−)(+,-)
−3.082353684-3.082353684(−,+)(-,+)(+,−)(+,-)(+,+)(+,+)
−2.773617481-2.773617481(−,+)(-,+)(+,+)(+,+)(+,−)(+,-)
−2.364676371-2.364676371(−,−)(-,-)(+,−)(+,-)(+,−)(+,-)
0.24876550580.2487655058(+,+)(+,+)(+,+)(+,+)(+,+)(+,+)

Table 1 (PDF p. 12).

Hence P111∗=0.2487655058P^*_{111}=0.2487655058.

References

  1. [1]C. Améndola, N. Bliss, I. Burke, C. Gibbons, M. Helmer, S. Hoşten, E. Nash, J. Rodriguez, D. Smolkin, The maximum likelihood degree of toric varieties, J. Symbolic Comput. 92 (2019) 222–242, doi:10.1016/j.jsc.2018.04.016.DOI
  2. [2]D. N. Bernshtein, The number of roots of a system of equations, Funct. Anal. Appl. 9 (1975) 183–185, doi:10.1007/BF01075595.DOI
  3. [3]C. D’Andrea, Macaulay style formulas for sparse resultants, Trans. Amer. Math. Soc. 354 (2002) 2595–2629, doi:10.1090/S0002-9947-02-02910-0.DOI
  4. [4]C. D’Andrea, M. Sombra, A Poisson formula for the sparse resultant, Proc. Lond. Math. Soc. (3) 110 (2015) 932–964, doi:10.1112/plms/pdu069.DOI
  5. [5]M. C. Fang, Closed form of a generalized Sinkhorn limit, arXiv:2506.06338 (2025).arxiv.org/abs/2506.06338
  6. [6]M. C. Fang, The eliminant of the generalized Sinkhorn limit: a resolution of the Rowland–Wu conjectures, preprint, Zenodo, doi:10.5281/zenodo.22864938 (2026).DOI
  7. [7]J. Franklin, J. Lorenz, On the scaling of multidimensional matrices, Linear Algebra Appl. 114/115 (1989) 717–735, doi:10.1016/0024-3795(89)90490-4.DOI
  8. [8]I. M. Gelfand, M. M. Kapranov, A. V. Zelevinsky, Discriminants, Resultants, and Multidimensional Determinants, Birkhäuser, Boston, 1994.DOI
  9. [9]J. Kruithof, Telefoonverkeersrekening, De Ingenieur 52 (1937) E15–E25.
  10. [10]M. B. Nathanson, Integer-valued minimization and doubly stochastic matrices, Integers 20A (2020), #A10, doi:10.5281/zenodo.10657507.
  11. [11]E. Rowland, J. Wu, The entries of the Sinkhorn limit of an m × n matrix, arXiv:2409.02789 (2024).arxiv.org/abs/2409.02789
  12. [12]R. Sinkhorn, Diagonal equivalence to matrices with prescribed row and column sums, Amer. Math. Monthly 74 (1967) 402–405.DOI
  13. [13]B. Sturmfels, A. Zelevinsky, Multigraded resultants of Sylvester type, J. Algebra 163 (1994) 115–127, doi:10.1006/jabr.1994.1007.DOI

Paper details

vlnc:W_dr7pcdbn
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents