Examples of Matrices for which the Sinkhorn algorithm terminates after EXACTLY, 2, steps By Shalosh B. Ekhad The Sinkorhn algorithm terminates after exactly, 2, steps for the following matrix [411 411 239 ] [---- ---- --- ] [1300 1300 650 ] [ ] [411 411 67 ] [--- ---- ----] [650 1300 1300] [ ] [411 411 -151] [--- ---- ----] [325 1300 260 ] and in floating point [0.31615384615384615385 , 0.31615384615384615385 , 0.36769230769230769231] [0.63230769230769230769 , 0.31615384615384615385 , 0.051538461538461538462] [1.2646153846153846154 , 0.31615384615384615385 , -0.58076923076923076923] Alas it has negative entries. Its Sinkhorn limit is [ -5 -5 239] [ -- -- ---] [ 63 27 189] [ ] [ 20 -67] [ -- 10/9 ---] [ 21 63 ] [ ] [ 151] [8/63 2/27 ---] [ 189] and in floating point [-0.079365079365079365079 , -0.18518518518518518519 , 1.2645502645502645503 ] [0.95238095238095238095 , 1.1111111111111111111 , -1.0634920634920634921] [0.12698412698412698413 , 0.074074074074074074074 , 0.79894179894179894180] The Sinkorhn algorithm terminates after exactly, 2, steps for the following matrix [3 %1 3 %1 1 - 6 %1 ] [ ] [6 %1 3 %1 1 - 9 %1 ] [ ] [12 %1 3 %1 1 - 15 %1] 4 3 2 %1 := RootOf(2948383 _Z - 1141186 _Z + 181971 _Z - 14087 _Z + 434) and in floating point [0.28256290165033023971 , 0.28256290165033023971 , 0.43487419669933952057] [0.56512580330066047943 , 0.28256290165033023971 , 0.15231129504900928086] [1.1302516066013209589 , 0.28256290165033023971 , -0.4128145082516511986] Alas it has negative entries. Its Sinkhorn limit is [ 21747113795318 3 5824182186094 2 645504843922 3837027455 [- -------------- %1 + ------------- %1 - ------------ %1 + ---------- , [ 1390344669 1390344669 1390344669 198620667 212003479615 3 56099415398 2 6145218893 34202746 ------------ %1 - ----------- %1 + ---------- %1 - -------- , 18086733 18086733 18086733 2583819 168956235732313 3 46864740875480 2 5366593539563 31285466710] --------------- %1 - -------------- %1 + ------------- %1 - -----------] 43100684739 43100684739 43100684739 6157240677 ] [13796454075007 3 3905207228138 2 446543878439 2789921269 [-------------- %1 - ------------- %1 + ------------ %1 - ---------- , [ 463448223 463448223 463448223 66206889 171592942217 3 48775708525 2 5590811851 35680544 - ------------ %1 + ----------- %1 - ---------- %1 + -------- , 6028911 6028911 6028911 861273 18784095022106 3 4828910657203 2 519955590676 3513236546] - -------------- %1 + ------------- %1 - ------------ %1 + ----------] 14366894913 14366894913 14366894913 2052413559] [ 19642248429703 3 5891439498320 2 694126791395 4731357019 [- -------------- %1 + ------------- %1 - ------------ %1 + ---------- , [ 1390344669 1390344669 1390344669 198620667 302775347036 3 90227710177 2 10627216660 70255067 ------------ %1 - ----------- %1 + ----------- %1 - -------- , 18086733 18086733 18086733 2583819 112603950665995 3 32378008903871 2 3806726767535 26902997749 - --------------- %1 + -------------- %1 - ------------- %1 + ----------- 43100684739 43100684739 43100684739 6157240677 ] ] ] 4 3 2 %1 := RootOf(2948383 _Z - 1141186 _Z + 181971 _Z - 14087 _Z + 434) and in floating point [-0.318223576244966555 , 1.042330105208626631 , 0.2758934710363399252] [ ] [-1.266530020067315179 , 2.074237214986250950 , 0.1922928050810642305] [ ] [2.584753596312281736 , -2.116567320194877580 , 0.5318137238825958440] Examples of Matrices for which the Sinkhorn algorithm terminates after EXACTLY, 3, steps By Shalosh B. Ekhad The Sinkorhn algorithm terminates after exactly, 3, steps for the following matrix [3 %1 3 %1 1 - 6 %1 ] [ ] [6 %1 3 %1 1 - 9 %1 ] [ ] [12 %1 3 %1 1 - 15 %1] 6 5 4 %1 := RootOf(370254308195869 _Z - 233461679574266 _Z + 61169658442832 _Z 3 2 - 8524816639944 _Z + 666492118408 _Z - 27716994988 _Z + 478991912) and in floating point [0.26126614919173276229 , 0.26126614919173276229 , 0.47746770161653447542] [0.52253229838346552458 , 0.26126614919173276229 , 0.21620155242480171313] [1.0450645967669310492 , 0.26126614919173276229 , -0.3063307459586638115] Alas it has negative entries. Its Sinkhorn limit is [ 4861296699189120905134282085 5 96570827469262496388137749 4 [- ---------------------------- %1 + -------------------------- %1 [ 919885904587226178 34069848318045414 278681048784465816810044915 3 29675113681555970083898318 2 - --------------------------- %1 + -------------------------- %1 459942952293613089 459942952293613089 524659709536191795541684 4751904740057457642007 - ------------------------ %1 + ---------------------- , 153314317431204363 65706136041944727 2873657560952913722273771 5 29669130406266358717823 4 ------------------------- %1 - ----------------------- %1 1465300797770124 27135199958706 177802033924169027606705 3 9818531535965468178406 2 + ------------------------ %1 - ---------------------- %1 732650398885062 366325199442531 179841822137419340771 1685508233758002194 + --------------------- %1 - ------------------- , 122108399814177 52332171348933 568652813629387611746235049453 5 2758355802246454127846386208 4 ------------------------------ %1 - ---------------------------- %1 171098778253224069108 1584247946789111751 31073264978687197080116231455 3 1613305100524625395014610172 2 + ----------------------------- %1 - ---------------------------- %1 85549389126612034554 42774694563306017277 27793762941345792821569255 245109290223471017660242] + -------------------------- %1 - ------------------------] 14258231521102005759 6110670651900859611 ] [11755440459784503840133241747 5 114670098252419378614345733 4 [----------------------------- %1 - --------------------------- %1 [ 1839771809174452356 34069848318045414 325098361704629699674542781 3 34025452983477833135833840 2 + --------------------------- %1 - -------------------------- %1 459942952293613089 459942952293613089 591603007104144948556286 5272610096882577302393 + ------------------------ %1 - ---------------------- , 153314317431204363 65706136041944727 5236761354686253172553615 5 204794793724947246645509 4 - ------------------------- %1 + ------------------------ %1 732650398885062 54270399917412 290977598183084550677696 3 61055115933526268935957 2 - ------------------------ %1 + ----------------------- %1 366325199442531 732650398885062 532130635399528813453 4755508143225226750 - --------------------- %1 + ------------------- , 122108399814177 52332171348933 129705863445340591266744442939 5 2584635403930910726787843065 4 ------------------------------ %1 - ---------------------------- %1 171098778253224069108 6336991787156447004 3742433568513671659250050199 3 800488467283184881579796779 2 + ---------------------------- %1 - --------------------------- %1 42774694563306017277 85549389126612034554 7116218243011300744731853 64927569679248461935090] + ------------------------- %1 - -----------------------] 14258231521102005759 6110670651900859611 ] [ 2032847061406262029864677577 5 9049635391578441113103992 4 [- ---------------------------- %1 + ------------------------- %1 [ 1839771809174452356 17034924159022707 46417312920163882864497866 3 4350339301921863051935522 2 - -------------------------- %1 + ------------------------- %1 459942952293613089 459942952293613089 66943297567953153014602 520771062961161605113 - ----------------------- %1 + --------------------- , 153314317431204363 65706136041944727 7599865148419592622833459 5 145456532912414529209863 4 ------------------------- %1 - ------------------------ %1 1465300797770124 54270399917412 404153162442000073748687 3 41418052861595332579145 2 + ------------------------ %1 - ----------------------- %1 732650398885062 732650398885062 352288813262109472682 3069947577295875623 + --------------------- %1 - ------------------- , 122108399814177 52332171348933 174589669268682050753244873098 5 13618058612916727238173387897 4 - ------------------------------ %1 + ----------------------------- %1 42774694563306017277 6336991787156447004 38558132115714540398616331853 3 4027098668332435671609017123 2 - ----------------------------- %1 + ---------------------------- %1 85549389126612034554 85549389126612034554 34909981184357093566301108 310042970573371380454943] - -------------------------- %1 + ------------------------] 14258231521102005759 6110670651900859611 ] 6 5 4 %1 := RootOf(370254308195869 _Z - 233461679574266 _Z + 61169658442832 _Z 3 2 - 8524816639944 _Z + 666492118408 _Z - 27716994988 _Z + 478991912) and in floating point [-0.297667982797482 -1.089999905726340 2.387667888523812 ] [ ] [0.985363612769232 1.804101057377300 -1.789464670146531] [ ] [0.3123043700282581 0.285898848349040 0.401796781622701 ] The Sinkorhn algorithm terminates after exactly, 3, steps for the following matrix [3 %1 3 %1 1 - 6 %1 ] [ ] [6 %1 3 %1 1 - 9 %1 ] [ ] [12 %1 3 %1 1 - 15 %1] 14 %1 := RootOf(238346776940777617152385502431 _Z 13 - 347562957579327277947459937139 _Z 12 11 + 236315474538236282034412929561 _Z - 99311073707759612202634994398 _Z 10 9 + 28818970760588432211898457720 _Z - 6108195889790240368679539500 _Z 8 7 + 974929955049780824590323912 _Z - 119005645611486432713231448 _Z 6 5 + 11159545261696424372970864 _Z - 799661680228729455158624 _Z 4 3 + 43082759006975478338416 _Z - 1691464848116012063664 _Z 2 + 45724493942195442080 _Z - 761430149702123776 _Z + 5890478467707456) and in floating point [0.24902463833949237256 , 0.24902463833949237256 , 0.50195072332101525488] [0.49804927667898474512 , 0.24902463833949237256 , 0.25292608498152288232] [0.99609855335796949024 , 0.24902463833949237256 , -0.2451231916974618628] Alas it has negative entries. Its Sinkhorn limit is [ %3 %7 %3 %7 (-1 + 6 %1) %3 %7 ] [1/7 ----- 1/9 ----- 1/3 ----------------- ] [ %6 %5 %2 ] [ ] [ %4 %7 %4 %7 (-1 + 9 %1) %4 %7 ] [2/7 ----- 1/9 ----- 1/3 ----------------- ] [ %6 %5 %2 ] [ ] [ %4 %3 %4 %3 (-1 + 15 %1) %4 %3] [4/7 ----- 1/9 ----- 1/3 ------------------] [ %6 %5 %2 ] 14 %1 := RootOf(238346776940777617152385502431 _Z 13 - 347562957579327277947459937139 _Z 12 11 + 236315474538236282034412929561 _Z - 99311073707759612202634994398 _Z 10 9 + 28818970760588432211898457720 _Z - 6108195889790240368679539500 _Z 8 7 + 974929955049780824590323912 _Z - 119005645611486432713231448 _Z 6 5 + 11159545261696424372970864 _Z - 799661680228729455158624 _Z 4 3 + 43082759006975478338416 _Z - 1691464848116012063664 _Z 2 + 45724493942195442080 _Z - 761430149702123776 _Z + 5890478467707456) 11 10 %2 := 814760185568780525848570 %1 - 952084202443644097428087 %1 9 8 + 504247665913454592199696 %1 - 159780592674420373656322 %1 7 6 + 33657822412345706109808 %1 - 4949144467498617131704 %1 5 4 + 518369667424837395832 %1 - 38674261614193947856 %1 3 2 + 2014232887519457632 %1 - 69745770516544704 %1 + 1445081413321504 %1 - 13572531031584 5 4 3 2 %3 := 284141399497 %1 - 149806920672 %1 + 31439149544 %1 - 3283093364 %1 + 170603112 %1 - 3529288 5 4 3 2 %4 := 205006049518 %1 - 111771123453 %1 + 24211669424 %1 - 2605673348 %1 + 139362924 %1 - 2964220 10 9 %5 := 30517272853019947119919 %1 - 32075924396081891056418 %1 8 7 + 15135920431230341452654 %1 - 4222623237675365029472 %1 6 5 + 771287535232989909120 %1 - 96380197863966496648 %1 4 3 2 + 8344377447633773840 %1 - 494245625445725280 %1 + 19167379401485824 %1 - 439483303698880 %1 + 4524177010528 10 9 %6 := 77157818555943000252757 %1 - 81692723474263890937224 %1 8 7 + 38828086977733692279508 %1 - 10909888891664437719016 %1 6 5 + 2006909268888957405616 %1 - 252551440146278419216 %1 4 3 + 22018525257747705904 %1 - 1313274091754442688 %1 2 + 51284228081272768 %1 - 1184040368399616 %1 + 12273415590016 5 4 3 2 %7 := 442412099455 %1 - 225878515110 %1 + 45894109784 %1 - 4637933396 %1 + 233083488 %1 - 4659424 and in floating point [-0.33383007323089120806 , 0.99872610807504626902 , 0.33510396412726095680] [-1.3355332976054872318 , 1.9977708413340360256 , 0.33776245267160053576] [2.6693633726982737231 , -1.9964969501183404204 , 0.32713358410035674647]