ABSTRACT (original article): We use Gröbner bases to compute the Sinkhorn limit of a positive matrix , showing that the entries are algebraic numbers with degree at most 6. The polynomial equation satisfied by each entry is large, but we show that it has a natural representation in terms of linear combinations of products of minors of . We then use this representation to interpolate a polynomial equation satisfied by an entry of the Sinkhorn limit of a positive matrix. Finally, we use the PSLQ algorithm and 1.5 years of CPU time to formulate a conjecture, up to certain signs that we have not been able to identify, for a polynomial equation satisfied by an entry of the Sinkhorn limit of a positive matrix. In particular, we conjecture that the entries are algebraic numbers with degree at most . This degree has a combinatorial interpretation as the number of minors of an matrix, and the coefficients reflect new combinatorial structure on sets of minor specifications. CITATION (original article): Eric Rowland, Jason Wu, (2024), The entries of the Sinkhorn limit of an m×n matrix, arXiv:2409.02789. https://doi.org/10.48550/arXiv.2409.02789
3×3
A
A
4×4
m×n
m+n-2 |
m-1 |
(m−1)×(n−1)
In[]:=
ListScale[list_,total_:1]:=list
total
Total[list]
In[]:=
MatrixScale[matrix_,rowtotal_:1,columntotal_:1]:=Transpose[Map[ListScale[#,columntotal]&,Transpose[Map[ListScale[#,rowtotal]&,matrix]]]]
Iteratively scale the rows and columns of a matrix until a fixed point is reached:
With[{matrix={{3,9,1},{3,2,9},{5,3,4}},precision=},FixedPoint[MatrixScale,N[matrix,precision]]//MatrixForm]
4
2
Out[]//MatrixForm=
0.27667712 | 0.6480462 | 0.07527666 |
0.25194210 | 0.13113571 | 0.6169222 |
0.4713808 | 0.22081807 | 0.30780115 |
Increase the precision and guess a polynomial equation satisfied by the top left entry:
With{matrix={{3,9,1},{3,2,9},{5,3,4}},precision=},Module[{rowcount,columncount,degree},{rowcount,columncount}=Dimensions[matrix];degree=Binomial[rowcount-1+columncount-1,rowcount-1];MinimalPolynomial[RootApproximant[FixedPoint[MatrixScale,N[matrix,precision]]〚1,1〛,degree],x]]
8
2
Out[]=
-12312+14346x+210897-125796-844359-220388+374752
2
x
3
x
4
x
5
x
6
x
Check that one of the roots is the top left entry:
In[]:=
NSolve[-12312+14346x+210897-125796-844359-220388+374752==0,x]
2
x
3
x
4
x
5
x
6
x
Out[]=
{{x-0.785974},{x-0.776536},{x-0.303887},{x0.276677},{x0.350329},{x1.82748}}
Compute the polynomial equation satisfied by the top left entry of the Sinkhorn limit of a general positive matrix:
3×3
Module{rowcount=3,columncount=3,sinkhornlimit,matrix,d1,d2,rowsums,columnsums,polynomials,eliminationvariables},sinkhornlimit=Table[Symbol["s"<>ToString[i]<>ToString[j]],{i,1,rowcount},{j,1,columncount}];matrix=Table[Symbol["a"<>ToString[i]<>ToString[j]],{i,1,rowcount},{j,1,columncount}];d1=DiagonalMatrix[Table[Symbol["d1"<>ToString[i]],{i,1,rowcount}]];d2=DiagonalMatrix[Table[Symbol["d2"<>ToString[i]],{i,1,columncount}]];rowsums=ConstantArray[1,rowcount];columnsums=ConstantArray,columncount;polynomials=Join[Join@@(sinkhornlimit-d1.matrix.d2),Total/@sinkhornlimit-rowsums,Total/@Transpose[sinkhornlimit]-columnsums];eliminationvariables=Join[Variables[d1],Variables[d2],Rest[Variables[sinkhornlimit]]];Collect[First[GroebnerBasis[polynomials,Variables[polynomials],eliminationvariables,Method"Buchberger",MonomialOrderEliminationOrder,SortTrue]]/.s11x,x,Factor]
rowcount
columncount
Out[]=
The package SinkhornPolynomials uses this formula and others to compute Sinkhorn limits.
It is available as an ancillary file from https://arxiv.org/abs/2409.02789.
Its documentation is below.
It is available as an ancillary file from https://arxiv.org/abs/2409.02789.
Its documentation is below.
SinkhornPolynomials 1.00
SinkhornPolynomials 1.00
Documentation Notebook
Introduction
Introduction
SinkhornPolynomials is a package for computing the polynomial equation satisfied by an entry of the Sinkhorn limit of a matrix.
This introduction gets you started with a few features of the package; the next section provides a complete list of package symbols along with their usage messages and further examples.
This introduction gets you started with a few features of the package; the next section provides a complete list of package symbols along with their usage messages and further examples.
To use SinkhornPolynomials, first you will need to load the package by evaluating the following cell. (If you need help, see loading a package.)
In[]:=
<<SinkhornPolynomials`
Square matrices
Square matrices
Row and column scaling
Row and column scaling
Rectangular matrices
Rectangular matrices
Package symbols
Package symbols
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
The entries of the Sinkhorn limit of an m×n matrix
by Eric Rowland, Jason Wu
Wolfram Community, STAFF PICKS, October 21, 2024
https://community.wolfram.com/groups/-/m/t/3304287
by Eric Rowland, Jason Wu
Wolfram Community, STAFF PICKS, October 21, 2024
https://community.wolfram.com/groups/-/m/t/3304287