{"entities":{"Q856850":{"pageid":858698,"ns":120,"title":"Item:Q856850","lastrevid":42727995,"modified":"2025-07-09T15:07:05Z","type":"item","id":"Q856850","labels":{"en":{"language":"en","value":"Algorithms for constructing \\((0,1)\\)-matrices with prescribed row and column sum vectors"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5080049"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q856850$3180FEE0-C776-4434-83E1-79086E19351E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5c8659e972d4026b45803596a648ac1f92cad47b","datavalue":{"value":{"text":"Algorithms for constructing \\((0,1)\\)-matrices with prescribed row and column sum vectors","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q856850$00648BEF-1C62-48CE-B8D8-B84B532A5B8F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5f8203820cc7b360d869a0a30c5ad6f7b364fde0","datavalue":{"value":"1110.05102","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q856850$6FE71C57-49BE-4C9D-952E-C7C87569AB80","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1d6aa4b6ea137743f1486f22cb13cc1976b208f6","datavalue":{"value":{"entity-type":"item","numeric-id":215010,"id":"Q215010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q856850$1BF31502-7CE2-4EDA-8DD9-DAB765ADB43F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q856850$9F392F06-7D6F-4CA9-872B-324BBEF2AF36","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0f104b4da63c9b7ec094905bf1c1c3559eeb80a1","datavalue":{"value":{"time":"+2006-12-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q856850$62B0A5E7-4B7E-4B1B-8EFB-55830F7B976D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0a667cc0bc040fd3964ea85e9f5e3f36a5032668","datavalue":{"value":"Let \\(R=(r_1\\geq r_2 \\geq r_3 \\geq \\cdots\\geq r_m)\\) and \\(S=(s_1\\geq s_2 \\geq s_3 \\geq \\cdots \\geq s_n)\\) be positive integer vectors satisfying \\(\\sum r_i=\\sum s_i,\\) and let \\({\\mathcal A}(R,S)\\) be the family of \\(m\\times n\\) \\((0,1)\\)-matrices with row sum vector \\(R\\) and column sum vector \\(S.\\) Let \\(\\preceq\\) be the majorization order and \\(R^*\\) the conjugate to \\(R.\\) The well-known Gale-Ryser theorem says that \\({\\mathcal A}(R,S)\\neq \\emptyset\\) if and only if \\(S\\preceq R^*.\\) The Ryser algorithm starts from the unique matrix in \\({\\mathcal A}(R,R^*)\\) to actually construct an element in \\({\\mathcal A}(R,S).\\)   A \\((0,1)\\)-matrix \\(A=(a_{ij})\\) defines a unique generalized permutation \\(\\{(i,j): a_{ij}=1\\}\\) which in turn stands via the Knuth-Schensted correspondence [see \\textit{C. Greene}, Adv. Math. 14, 254--265 (1974; Zbl 0303.05006) and \\textit{D. E. Knuth}, Pac. J. Math. 34, 709--727 (1970; Zbl 0199.31901)] in a bijective relation with a pair of Young tableaux. If \\(A\\in {\\mathcal A}(R,S),\\) one of these tableaux, the insertion tableau, has shape \\(\\lambda\\) satisfying \\(S\\preceq \\lambda \\preceq R^*.\\)   The author says that, given \\(\\lambda\\) with \\(S\\preceq \\lambda \\preceq R^*,\\) it may not be easy to construct in algorithmic manner a matrix whose associated insertion tableau has shape \\(\\lambda,\\) but he succeeds to give Ryser like algorithms for the cases \\(\\lambda=S\\) and \\(\\lambda=R^*.\\) In passing also given is the relation of \\(| {\\mathcal A}(R,S)| \\) with the Kostka numbers.","type":"string"},"datatype":"string"},"type":"statement","id":"Q856850$59316D4E-9F3C-4364-888B-0B0FCB1BF19F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4cb749bb0545117c5a39ee1b861da533345043d8","datavalue":{"value":{"entity-type":"item","numeric-id":587686,"id":"Q587686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q856850$7F8E734C-5287-4C23-AF25-3B1B57489528","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8cf2f692eb0d5c2fc2ce5b2154318999029c1c1b","datavalue":{"value":"05E10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q856850$923C751B-BB57-4FA0-AAC4-FA4A2FBF7129","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a8c253e9e91fee115e48a234366ae789b666cc0a","datavalue":{"value":"5080049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q856850$77305F98-EC3B-44F6-A9DF-D60EAFF06556","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89df31c5b4a7f10843b93b9bd1262f972be8c4d4","datavalue":{"value":"Young tableaux","type":"string"},"datatype":"string"},"type":"statement","id":"Q856850$E499DC4B-64D0-46A4-B788-36C42BD6AB0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"52b259a60f32b1743cf66b643d06a76fd54f561a","datavalue":{"value":"row and columns sum vectors","type":"string"},"datatype":"string"},"type":"statement","id":"Q856850$F2E2EE35-BE01-4AF5-85F2-42D57CB49F5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q856850$A7BC8206-9419-4CD8-BB00-88C161DBC8FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3943255ddfe2e3539d5b5d917627ded483754a7a","datavalue":{"value":"Gale-Ryser theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q856850$85CAF74F-B644-4F4E-AE05-AB255FACA604","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90b16d0ad3222d68e9d424a4937ea715a81016b2","datavalue":{"value":"Knuth-Schensted correspondence","type":"string"},"datatype":"string"},"type":"statement","id":"Q856850$0CC34E75-B2E1-41DD-B186-3FBF1305A8B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"61b0c3dc8fb2925fdefeef0e5a76208431656b0a","datavalue":{"value":"Kostka numbers","type":"string"},"datatype":"string"},"type":"statement","id":"Q856850$D26E1001-73F0-4486-81F3-F143DF9BF084","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff8d6e409b01cf2b93d813ce35a08f3f5a5767e2","datavalue":{"value":"Ryser algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q856850$65687CB4-A364-4C49-A23F-464FDF68394F","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q856850$1DDF8B85-A0F7-4EBD-95E2-459A166B16B6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d66a54d23e34511f2fffa6f33e33a8ac339c0da2","datavalue":{"value":"https://doi.org/10.1016/j.disc.2004.10.028","type":"string"},"datatype":"url"},"type":"statement","id":"Q856850$8C793ACD-33D1-4A07-9B14-030BE0DBFC49","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"853adc2e4606a044a1a4a21dbce82775f68dc3bc","datavalue":{"value":"W1995751254","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q856850$95DE46F3-F763-491D-8B54-77E108EEFEA1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d66b668d62d8680416f5ca30a5fcd0415362617","datavalue":{"value":{"entity-type":"item","numeric-id":1146695,"id":"Q1146695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q856850$2170280E-4F69-4182-BADE-375CCBEBF3B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abb228b8e0a9b8221782f1a1717638989a2d5dfc","datavalue":{"value":{"entity-type":"item","numeric-id":5484517,"id":"Q5484517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q856850$5C2B06D3-ABA5-4713-BDC1-B5317341E815","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"777fcd6eb2ed5ee098a1245269fff21b95cad4c5","datavalue":{"value":{"entity-type":"item","numeric-id":3129746,"id":"Q3129746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q856850$E742F25C-F6DA-490E-B817-81FC806D1BDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54d58eaa2ee4c9d4108497ce31420632b517c1ad","datavalue":{"value":{"entity-type":"item","numeric-id":1216397,"id":"Q1216397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q856850$065FA2D4-8C37-41B6-9CE5-AE17FE206EAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ffe11abc22e68ae906332024cf889b115d7224f","datavalue":{"value":{"entity-type":"item","numeric-id":2540557,"id":"Q2540557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q856850$B95A16A6-8FEC-4173-AD8B-87DA9186E6D2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"82b06f4878957513a2a24d06549e05df832e6732","datavalue":{"value":"10.1016/J.DISC.2004.10.028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q856850$3AF5279F-CE5D-42AB-B1EA-B4DB379BE524","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9465bfb536ec00d104364243eaaaf0d1d056ec3b","datavalue":{"value":{"entity-type":"item","numeric-id":1025513,"id":"Q1025513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c830f960b1b98932e0de6f08314391fc7f19aeea","datavalue":{"value":{"amount":"+0.8526069","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q856850$2AF75473-D63F-4AE2-AF40-57CDA8A05709","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c51b6fb0679b5a5a6157d50bab3d3534006d0497","datavalue":{"value":{"entity-type":"item","numeric-id":393474,"id":"Q393474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"636b13b4f4e3903eb31cc7ea8bc6d6a34aad1eac","datavalue":{"value":{"amount":"+0.84477484","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q856850$E8BB1194-CA53-4688-BE26-6BE045685047","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3002e00080bfac0d53577b95a1daf94f27b0a8eb","datavalue":{"value":{"entity-type":"item","numeric-id":2798229,"id":"Q2798229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab8ca1e5920e44ad4d3c3a6d03cee79e5302168e","datavalue":{"value":{"amount":"+0.791377","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q856850$6F623FFA-50C2-4B7C-AD5F-85813F215106","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45388d4c759939555ab5b5e43f721999682be6ba","datavalue":{"value":{"entity-type":"item","numeric-id":2540557,"id":"Q2540557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc1fc0c2fe93f6dd2e8064d08766480f3048ab7f","datavalue":{"value":{"amount":"+0.7859295","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q856850$5774A3C4-16BA-458D-9A0A-AD72E299BB7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97b52766317a43307eaaa2f732a0b8c8098b8807","datavalue":{"value":{"entity-type":"item","numeric-id":1001688,"id":"Q1001688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f94f6316e2457e33148af591da619e9aa3a2930d","datavalue":{"value":{"amount":"+0.77719223","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q856850$B23086BB-804D-4B00-A800-607951716906","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90f56c4b34c1131b8ee27ff4c7e21099c7430c6d","datavalue":{"value":{"entity-type":"item","numeric-id":1112824,"id":"Q1112824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89246d5119465063a6994e5095dd21ebe928fe18","datavalue":{"value":{"amount":"+0.7696382","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q856850$095C9743-2ECD-4DD6-AB68-912B16EC6107","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c5cd64367f0cbe365df71a2a25bfce97931ba0d","datavalue":{"value":{"entity-type":"item","numeric-id":1918489,"id":"Q1918489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d59cef2d041817e25f8c0ea4c942dc78067b823","datavalue":{"value":{"amount":"+0.7696101","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q856850$6300E897-1D35-48D8-A7AB-3796F9F0D933","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d2fe48e9d9f63e452da0938b3bd018b3963a0b1","datavalue":{"value":{"entity-type":"item","numeric-id":5502235,"id":"Q5502235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7aaa87f7be3d0839d93843389069ba6670be0d60","datavalue":{"value":{"amount":"+0.7667873","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q856850$EC0E390F-C4D7-4CC2-989A-77F453A63E83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47bd36ef6232a5e3e9e703adffed0aa21eb87995","datavalue":{"value":{"entity-type":"item","numeric-id":1186121,"id":"Q1186121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28bbb57f7c133f8de4a2668f40ceb76bed4ba3e0","datavalue":{"value":{"amount":"+0.7587121","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q856850$C5FD2C39-2418-4EB8-B87A-58136724D82F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1dd5242c4fca6639e1a26f949b1f8ca73f76863","datavalue":{"value":{"entity-type":"item","numeric-id":1317457,"id":"Q1317457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54d05764cb258f764fded04dafd5aba84768d948","datavalue":{"value":{"amount":"+0.7557156","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q856850$BB85D97B-AFCA-4D13-ADFE-D41AC06BE6F0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:856850","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:856850"}}}}}