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 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 with , 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 generalized eigenvalue problem, whose null vector recovers the whole limit. The leading coefficient is the principal -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 be a positive tensor of format , and for each mode let be target margins with a common total . Repeatedly rescaling the slices of so that its mode- margins equal converges to a tensor
which is the unique tensor of this form with these margins [9, 12, 7]. For 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 , give what Rowland and Wu call the Sinkhorn limit.
The entries of are algebraic over the entries of and the margins. For 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 matrix is a root of an explicit polynomial of degree ; 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 . The margin conditions are linear in , and ranges over the cone over the Segre variety , of dimension . After normalization the conditions are multilinear forms ; adding the form that fixes the corner entry to gives forms on a -dimensional variety. For generic they have a common zero exactly when is the corner entry of a solution. The number of complex solutions, , 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 is, up to a factor independent of , the product of over all complex solutions; by a theorem of Sturmfels and Zelevinsky [13] it is a single Sylvester determinant, of size with in exactly columns, so that the corner entry is an eigenvalue of an explicit pencil (Corollary 3.3). § 4 identifies the leading coefficient with the principal -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 : it is the only root for which 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 . 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 with all , write , , and
Index cells by , write for the corner, for the entries of , and for the Segre coordinates. Let and define the multilinear forms
There are forms ; we list them as .
Lemma 2.1. A point with is a common zero of if and only if has margins . In that case exactly when .
Proof. The mode- margin of at is , and . The forms with are omitted because the margins in each mode sum to automatically. Finally, .
Thus the complex solutions of the scaling problem are the points of with , and the scaling limit is the unique positive one.
Lemma 2.2. Fix margins with and all (for instance positive). For outside a proper Zariski-closed subset, lies in the dense torus of and consists of simple points, at each of which .
Proof. Each lies in the torus orbit of a unique face (), and exactly for . For fixed the are linear forms in with coefficient vectors , where is the indicator of the slice . The vectors (, all ) span a space of dimension containing . If , choose with : either some is not in , and then the vector is , or , and then the vectors for sum to . In both cases , and hence every , lies in the span of our vectors, so the forms impose conditions on . The incidence variety therefore has dimension less than the number of cells, and for generic we get . For the whole box the same computation gives independent conditions, so is a vector bundle over , smooth and irreducible, of dimension equal to the number of cells. Its projection to is dominant, since for the rank-one tensor the point lies in and is a simple zero (for positive , every positive has a positive solution), so it is generically finite and, by generic smoothness, has reduced generic fibers. With no zeros on the boundary of , Bernstein’s theorem [2] counts the torus zeros, with multiplicity, as the normalized volume of , which is . Finally, a point of with annihilates and all of its logarithmic derivatives , so it is a singular point of in the torus; that happens only for in a proper closed subset (the closure of this set is the dual variety). □
The main theorem
For a multidegree let be the space of polynomials of multidegree in the variables , so . Put , (), and
Each has multidegree . The Sylvester map is
Explicitly, in monomial bases (rows indexed by monomials of multidegree , columns by pairs with of multidegree $m-1), the entry in row and column is the coefficient of in if for a cell , and $0$ otherwise. Thus every entry is , , or .
Lemma 3.1. is square, of size , and enters only the columns of the last summand, linearly.
Proof. . Since , the product telescopes:
□
Theorem 3.2. For every and , , and when and are positive this vanishes at . Suppose moreover that is contained in the dense torus of (by Lemma 2.2 this holds for generic ). Then
where is the intersection multiplicity, , is the corner entry of the solution , and and do not depend on . For generic the polynomial has degree exactly , with the corner entries of the complex solutions as its roots.
Proof. is the resultant of type : an irreducible polynomial in the coefficients of multilinear forms that vanishes exactly when they have a common zero on [8 Ch. 13, §2A]. Since for all , by Sturmfels and Zelevinsky [13] (see [8 Ch. 13, Prop. 2.2 and (2.3)]) the resultant equals the determinant of the Sylvester map for each of the vectors , one for each permutation of the factors. For the identity permutation this is our , and identically in the coefficients of the forms; being a polynomial identity, it holds for our specialized coefficients. At the forms have the common zero given by the limit, so the resultant vanishes.
When lies in the torus (it is then finite, being closed in ), the Poisson formula for sparse resultants [4 Thm. 1.1] gives for every of multidegree . Here is a product of powers of directional resultants of ; these are nonzero because meets no boundary orbit, and does not depend on . By Bernstein’s theorem [2] the total multiplicity is the normalized volume of , that is, . For each factor is , which is if and independent of otherwise. By Lemma 2.1 the are the corner entries of the complex solutions. The last sentence follows from Lemma 2.2.
Corollary 3.3 (Eigenvalue form). Write , where collects the first columns and the last . Whenever (in particular for generic ), has full column rank; let the columns of , with entries in , span its left kernel. Then
so is a generalized eigenvalue of an explicit pencil. More generally, let with , and suppose is a simple root of . Then the left null vector of is, up to scale, the evaluation on . So it determines every ratio of , and hence the whole solution , with entries in . For this recovers the limit from .
Proof. Multiply on the left by an invertible matrix whose last rows are ; the result is block triangular. The functional is nonzero, and it kills every because and all vanish at . When the root is simple the left kernel is one-dimensional. Since for every , the monomials of include pairs differing by one variable of each mode, and the corresponding ratios of coordinates of the null vector are the ratios .
Theorem 3.4 (The root of the limit). Let and the margins be positive, let be the limit, and let be its Segre point. For write for the vector of monomials of multidegree evaluated at , a row vector indexed like the rows of .
(1) is the only solution with all entries positive, and is a simple point of .
(2) For , the left kernel of contains for some with all coordinates positive if and only if , and then . In particular .
(3) If is a simple root of , its left null vector is, up to scale, positive, which has all entries positive. If moreover lies in the torus and all roots are simple, then is the only root of 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 is a simple zero, scale so that , and use the coordinates , writing tangent vectors as . The directions with for every are tangent to the fibers of the cone over , so is the quotient by them. The derivative of the map (all margins of ) at is the symmetric matrix of the form . Since , is positive semidefinite, and exactly when for all , that is, when with .
Now let satisfy for . Summing over gives identically when is defined by the same formula, so also . As with , this reads for all . Let be the vector with and for , so that . Then , so every is a multiple of , and is zero in . Thus have independent differentials at , and is a simple zero.
(2) The entry of in the column is , with . If is positive then , so lies in the left kernel exactly when . Since , Lemma 2.1 shows that this means is a positive solution with corner entry , hence equals by (1).
(3) A simple root has a one-dimensional left kernel, which by (2) is spanned by . For another simple root , the left null vector is by Corollary 3.3. If it can be scaled to be positive, then all ratios of monomials at are positive. These include all ratios , so is positive and .
Thus the limit is distinguished from the other roots by positivity of the whole solution, read off from the null vector of . When lies in the torus, (1) shows that the factor occurs in 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 is a simple root of , a single corner determinant and its left null vector already recover all entries of via Corollary 3.3.
Remark 3.5. Theorem 3.2 needs no genericity beyond the assumption on ; there are admissible multidegrees, one for each ordering of the factors, and all give the same determinant up to sign.
Leading and constant coefficients
Write . We treat the entries as indeterminates and the margins as coordinates on the linear space of margin vectors with a common total , so the coefficients of lie in ; “up to a unit” means up to a factor with , . Let be the vertex set of . For a face let be the corresponding subtensor and its -discriminant : for a cell, the minor for a square face of a matrix, Cayley’s hyperdeterminant for a face, and in general the hyperdeterminant of when it is nontrivial (and otherwise) [8]. The principal -determinant is , with all multiplicities equal to one because the toric variety is smooth [8 Ch. 10, Thm. 1.2].
Theorem 4.1. Up to a unit, the leading coefficient of is ; in particular it does not depend on the margins except through a power of .
Proof. The coefficient of is . A resultant is unchanged by adding to one form a multiple of another of the same multidegree, so we may replace by , which removes . Write , the polynomial with support and coefficients . Then and , and together these span the space of all logarithmic derivatives of and itself (the omitted derivatives are determined by the Euler relations . The -resultant is the resultant on the toric variety , so is, up to a nonzero constant, the principal -determinant as defined in [8 Ch. 10, (1.1)]. By [8 Ch. 10, Thm. 1.2], since is smooth, it is the product of the discriminants of all faces, each to the first power. □
Corollary 4.2. The degree of is less than exactly on the hypersurface , that is, when some face of has vanishing hyperdeterminant (or minor, or entry).
The faces through the corner and the others play different roles.
Proposition 4.3. *If does not contain the corner, then divides every coefficient of . *
Proof. For generic with , the restriction of to the face has a singular point in its torus, since by definition is the closure of the set of such coefficient vectors [8 Ch. 9, (1.1) and Def. 1.2]. This gives a point in the torus orbit of at which and all its logarithmic derivatives vanish, that is, all margins of are zero. So and every . Since , also , hence for every , and . As this holds on a dense subset of the hypersurface , the irreducible polynomial divides as a polynomial in and , and being free of it divides each coefficient. □
Proposition 4.4. For let be the slab , of format , let be its vertex configuration, and let be the degree of . Up to a unit,
Proof. At , . The resultant is multiplicative in its last argument, and , so with the latter resultant. On only cells of survive. Write and for the restricted total and margin forms. For mode the restricted forms () sum to , and the matrix taking to them has determinant . So, after a triangular change of basis of determinant , the restricted forms become , () and (, ); the other modes are handled by subtracting multiples of . Since has degree in each argument, , and the last resultant is, up to a nonzero constant, , exactly as in the proof of Theorem 4.1. □
Thus both extreme coefficients of are products of face discriminants. In particular for generic and any margins with .
Theorem 4.5. Fix margins with and all . As a polynomial in , has content, up to a unit,
the product over all faces not containing the corner (including the vertices , ). Consequently , where is primitive of degree ; up to a unit, its leading coefficient
and constant term are
where . Moreover is a power of an irreducible polynomial in .
Proof. The content divides the leading coefficient (Theorem 4.1). This is squarefree and free of , and it is a product of irreducible face discriminants that are pairwise non-associate, since each involves exactly the variables , (see below). So for some set of faces. Proposition 4.3 gives for every . At we have , so , since is a factor of ; hence . Now let be a face of positive dimension with nontrivial discriminant. is irreducible [8 Ch. 9, Def. 1.2] and invariant up to sign under permutations of the indices within each mode of . These permutations act transitively on the cells of , so the nonconstant polynomial involves every with , in particular . By Proposition 4.4, is a nonzero polynomial whose only dependence on is the factor , since the slabs do not contain the corner. An irreducible polynomial involving and not associate to cannot divide it. Hence .
The formula for follows from Proposition 4.4. Every face lies in exactly the slabs with , and is the product of the discriminants of the faces of .
For the last claim, let be the incidence variety of Lemma 2.2. It is irreducible, and its projection to has degree with reduced generic fibers. By Theorem 3.2, is, up to its leading coefficient, the norm of from the function field of to , which is a power of the minimal polynomial of . □
Remark 4.6 (Degenerate tensors). For special positive the full determinant can vanish identically. For instance, by Proposition 4.3 this happens for a matrix with a vanishing minor away from the entry. The right object is therefore . Since the limit depends continuously on , the identity , valid for generic , holds for every positive . The coefficients of have no common factor, so outside a subset of codimension at least two.
Matrices
For , Theorem 3.2 gives an pencil with 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 is the product of the minors of size at least two that contain , 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 the two forms differ by a change of basis; we give a short proof of this formula.
Plücker coordinates and derivations. Let be the standard basis of , totally ordered. For a -subset write . The Plücker vector of the row space of a full-rank matrix is , with the maximal minor of on the columns . A matrix acts on as the derivation .
Lemma 5.1. In the basis , ; if with , , then with ; all other entries vanish.
Proof. The term of contributing to replaces by ; sorting moves past exactly the elements of strictly between and . □
Lemma 5.2. If then ; if then .
Proof. With , . If every term vanishes; if take . □
Let with row targets and column targets . Index by , let be the maximal minor of on the columns , and put
The link is the set of -subsets with , ; it corresponds to pairs and with , so . For let , , and . By Lemma 5.1, , for exchanges avoiding , and .
Theorem 5.3 ([6]). With and , the top-left entry of the limit is a root of
Proof. Let be the row space of with Plücker vector . The margins say and , so Lemma 5.2 gives . For the coordinates that can occur in come from or , where () and (); hence . Since , each is times a torus character, and . Multiplying the row by shows that lies in the kernel. □
Proposition 5.4. Let and . Under , on , where and is contraction with , and with . Hence has eigenvalues and with multiplicities and (understood as a single eigenvalue of multiplicity when ).
Proof. Away from , , and the sign difference caused by is corrected by ; . From and we get , and the trace of on is . □
In particular is invertible, so the leading coefficient of is , with . Up to sign, is the minor of on the rows and the columns . As runs over , these are exactly the square submatrices containing the entry , including itself. Since and have the same degree and the same roots for generic , comparing leading coefficients shows that equals up to a unit, leaving the product of the minors of size at least two through the corner as the leading coefficient of , in agreement with Theorem 4.5.
The other roots
Kruithof’s method and Sinkhorn’s algorithm look for positive factors such that has the prescribed margins. The other roots of arise in the same way once the factors are allowed to be arbitrary nonzero complex numbers. Write for the torus of rescalings that do not change , and consider the dual potential
on . The logarithms are multivalued, but is not: .
Proposition 6.1.
(1) For every , if are such that has the prescribed margins, then is a root of , and the left kernel of contains the evaluation at .
(2) For generic there are exactly such complex solutions modulo , all simple, and their corner entries are the roots of , counted with multiplicity. When is irreducible these roots are the Galois conjugates of over .
(3) The complex solutions are exactly the critical points of , modulo .
(4) If and are positive and a solution is real, there are signs with for all . Then is a positive scaling, with the prescribed margins, of the sign-twisted tensor , and a critical point of
For trivial , is strictly concave modulo and its unique critical point is the limit. The twisted tensors have the same complex solutions as , and hence the same roots.
Proof. (1) The point lies in the torus of , and and with vanish at by Lemma 2.1. So lies in the left kernel of , 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 . (4) If is real then so is the rank-one tensor , so after a rescaling in every is real. Write coordinatewise. For trivial , is linear minus a positive combination of exponentials of the linear forms , which vanish simultaneously only in the directions of . Finally, . □
Algebraically, the limit is on the same footing as the other complex solutions; only positivity selects it (Theorem 3.4). The number 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 ) has the same structure: the margin conditions are linear in , and ranges over the toric variety . The corner entry of the limit is then a root of the -resultant of the margin forms and , which is the Chow form of evaluated at the margin space and has degree at most in . 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 (Plücker coordinates) from the dependence on the margins (the operator ). It would be interesting to find a basis with the same property for tensors. The irreducibility of in every format (equivalently, by Theorem 4.5, whether the corner entries of the generic complex solutions are distinct), the Galois group of over , 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 lies in (since the entries are positive and the slice sums through the corner equal ). In Examples A.1–A.3, has several roots in . For each real root we list the sign vectors of the real solution with corner entry (Proposition 6.1(4)), normalized by for . 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
as in [11 Example 1]. Then , , and
which is the polynomial given by [11 Theorem 3] for this . The leading coefficient is , the product of the four minors containing and . The constant term is . The polynomial is irreducible over , and its roots are
Table 1.
Two roots lie in , and only one has all sign vectors positive. By Theorem 3.4, , as computed in [11], and the left null vector of gives the whole limit (Corollary 3.3):
Example A.2. Let be the tensor with slices
and let , , . Then and . The four nonreal roots of are
by Proposition 6.1 they are the corner entries of solutions with nonreal scaling factors. The real roots are
Five roots lie in , and only one has all sign vectors positive. Hence .
Example A.3. Let
Then and . The polynomial is irreducible over ; we omit its coefficients. Two of its roots are not real, namely . Of the eighteen real roots, seven are negative, four are greater than 1, and seven lie in , of which only one has all sign vectors positive:
Hence .
Example A.4. Let be the tensor with , that is, with slices
and let , , . The minors of are nonzero, but its hyperdeterminant vanishes, as it does for every tensor whose entries are affine
functions of the indices. Hence the coefficient in Theorem 4.5 vanishes, so drops from 6 to 5:
which is irreducible over . Its constant term is , as in Theorem 4.5. Its roots are real and simple:
Table 1 (PDF p. 12).
Hence .
References
- [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]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]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]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]M. C. Fang, Closed form of a generalized Sinkhorn limit, arXiv:2506.06338 (2025).arxiv.org/abs/2506.06338
- [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]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]I. M. Gelfand, M. M. Kapranov, A. V. Zelevinsky, Discriminants, Resultants, and Multidimensional Determinants, Birkhäuser, Boston, 1994.DOI
- [9]J. Kruithof, Telefoonverkeersrekening, De Ingenieur 52 (1937) E15–E25.
- [10]M. B. Nathanson, Integer-valued minimization and doubly stochastic matrices, Integers 20A (2020), #A10, doi:10.5281/zenodo.10657507.
- [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]R. Sinkhorn, Diagonal equivalence to matrices with prescribed row and column sums, Amer. Math. Monthly 74 (1967) 402–405.DOI
- [13]B. Sturmfels, A. Zelevinsky, Multigraded resultants of Sylvester type, J. Algebra 163 (1994) 115–127, doi:10.1006/jabr.1994.1007.DOI