{"entities":{"Q2132515":{"pageid":2143258,"ns":120,"title":"Item:Q2132515","lastrevid":57730398,"modified":"2026-04-01T03:42:02Z","type":"item","id":"Q2132515","labels":{"en":{"language":"en","value":"Maximum determinant and permanent of sparse 0-1 matrices"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7515375"}},"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":"Q2132515$D3006BAC-53CE-433C-A772-A01A9052434A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fbef0a0cbcf8f0d785e1dd3eceb2aaee54a356c2","datavalue":{"value":{"text":"Maximum determinant and permanent of sparse 0-1 matrices","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2132515$D99B8F67-2122-4A7F-B0B2-5F03B919C517","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"43778ce939fca7af6c44c764eb5972f8bee55b16","datavalue":{"value":"1489.15013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2132515$E5374205-7BFA-4B50-8600-35479A6D0AD5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"713efce2d6d9d12aa7d933b6828fdf26bceb320e","datavalue":{"value":{"entity-type":"item","numeric-id":2121718,"id":"Q2121718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2132515$5040D099-313A-478C-A1C9-C6DF7480F2CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f9158385d8dfa25fd1cbf34c726849285f5355cf","datavalue":{"value":{"entity-type":"item","numeric-id":189372,"id":"Q189372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2132515$22580646-3AF4-4DE4-8F2D-0368AC66A246","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6699c6b60afb4b00b64a14d57aa0a532527ed2d9","datavalue":{"value":{"entity-type":"item","numeric-id":2132514,"id":"Q2132514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2132515$D33379BA-DDCA-4DE8-9950-75D19C8DC89D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8de031de05325b44570d0c47c3ec8813873d565c","datavalue":{"value":{"entity-type":"item","numeric-id":92813,"id":"Q92813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2132515$EBEDFFAC-DAD2-48A9-934B-01AF329E2D4E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b12c1a812c4fa27842d74adaabce2cfd08888a52","datavalue":{"value":{"time":"+2022-04-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2132515$839B7C63-941B-4613-95A5-BCCEAD140AAF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"81817a1930e6d50f072c3941a3a32f27a26aa7b9","datavalue":{"value":"https://arxiv.org/abs/2011.01892","type":"string"},"datatype":"url"},"type":"statement","id":"Q2132515$0C7F0835-122B-49E0-8D35-700A232CCE03","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c18e0c9f81a665ceb8961c90c3b1d0b9cd5396f9","datavalue":{"value":"This paper considers the maximum determinant of an \\(n \\times n\\) matrix, with entries in \\(\\{0,1\\}\\). Many upper bounds on determinants have been given in the literature, in particular for matrices with all entries \\(0\\) or \\(1\\).  For example, the classical Hadamard inequality together with arithmetic and geometric mean inequalities imply \\[ \\det(A) \\leq \\prod_{i=1}^n \\left( \\sum_{i=1}^n a_{i,j}^2 \\right) \\leq 2^{n/2} \\,. \\]  This bound was improved by \\textit{H. J. Ryser} [Can. J. Math. 8, 245--249 (1956; Zbl 0071.35903)], but still these bounds are not the best possible for sparse matrices.  \\textit{H. Bruhn} and \\textit{D. Rautenbach} [Linear Algebra Appl. 553, 37--57 (2018; Zbl 1393.15025)] proved that if \\(A \\in \\{0,1\\}^{n \\times n}\\) has at most \\(2n\\) non-zero entries, then \\[ |\\det(A)| \\leq 2^{n/6} \\cdot 3^{n/6}. \\]  They also conjectured that the determinant of \\(A\\) is at most \\(2^{n/3}\\) in this case.  The main result of the paper solves this conjecture. It is proved that if \\(A \\in \\{0,1\\}^{n \\times n}\\) has at most \\(n+k\\) non-zero entries, then \\[ |\\det(A)| \\leq 2^{k/3}. \\]  The authors also obtain an upper bound on the number of perfect matchings in \\(C_4\\)-free bipartite graphs based on the number of edges, which, in the sparse case, improves the classical Bregman inequality for permanents.  Finally, they offer three conjectures which may be studied in the future.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2132515$53F49A5E-6E15-41D9-9012-A5EE949C4BA8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"05d3577a372ecb34aff9afa8f1bfdd3af0594b9d","datavalue":{"value":{"entity-type":"item","numeric-id":273406,"id":"Q273406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2132515$FC366DDF-D48F-43CC-8EA4-4C05DC566251","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5f35883713e23ca3f0ced48b60a92f4891f4d526","datavalue":{"value":"15A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2132515$A7046C2C-2522-4DF5-9C31-08DE74B32D94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4a6c6840ed6ccc38a95b421c87c1ec55f8094382","datavalue":{"value":"15A45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2132515$4E4098F5-203D-488A-9BF0-80EC22BB4D0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2a3b3e6e451112ae88a925a4babad921e127a616","datavalue":{"value":"15B34","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2132515$8421BF76-2164-4133-8AB0-0C642336A95B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"772466e23f65811e4792a58a12ff09d79c338e5f","datavalue":{"value":"05B20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2132515$2B06BE24-75B5-4F86-AB26-058E865AA569","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"deba18672e3ca685f593c43448530031567311a7","datavalue":{"value":"7515375","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2132515$50C7889E-2265-46BD-80EE-C900BC10FF42","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ebd3c4883c35fb46a1089afc6bf027d559cd3cf8","datavalue":{"value":"0,1 matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q2132515$D7910F06-95E1-4BFE-9D1C-6AB87463C0BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d470915ad5f8b20e8e1116c88f9a812167267df5","datavalue":{"value":"sparse matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q2132515$E5C91EC9-98ED-451C-A5BE-A41582A693EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"574f1053a5d0cb138eeb1d178cfc4915c70a8532","datavalue":{"value":"determinant","type":"string"},"datatype":"string"},"type":"statement","id":"Q2132515$8D6E513A-7E83-4F51-B400-0E7313EB2E15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ecde75e20fea1230a086243cffda8342cc569a15","datavalue":{"value":"permanent","type":"string"},"datatype":"string"},"type":"statement","id":"Q2132515$DFE5D6B6-E503-4E82-84B3-48959355404B","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"a07ada4ac7f09fd14eeb70ac8b6ff7f9567c84be","datavalue":{"value":"Q114151699","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2132515$0F8E89DE-CE8B-40B8-8327-CCDB9C025B5C","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":"Q2132515$4B1765CA-3A29-4178-8BBD-E6D6B6D11FC7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"659e1d44b9b86fcbcc0b331ff6505450ea87c6a8","datavalue":{"value":"W4221007402","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2132515$47A17AC0-D8F7-49E4-9302-0667FD5D38E1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"35ef32aaa573f409337eb0d613a3bc6f6c7fca49","datavalue":{"value":{"entity-type":"item","numeric-id":5526640,"id":"Q5526640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2132515$5D74E982-E75C-46FE-BE4D-480D2FE6E2BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8f05da711df37d5bfdc34748759af3eaa55b69a","datavalue":{"value":{"entity-type":"item","numeric-id":4044717,"id":"Q4044717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2132515$50D4B2F8-7297-4975-9AF1-CA7A99A0E295","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"770a14f69d7d278cbeb8337c429870ce66218fcd","datavalue":{"value":{"entity-type":"item","numeric-id":1641998,"id":"Q1641998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2132515$D45848BA-2CCC-44BB-82C2-DEF0DA1EB4A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4d3ac834802d8f4afbbd2642f2c0a045609ea7f","datavalue":{"value":{"entity-type":"item","numeric-id":3234513,"id":"Q3234513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2132515$A4160A87-360D-40E2-9D4D-165BAEAA04EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ece8c5958034e2aa029af094f9e4d46a4a93a8d","datavalue":{"value":{"entity-type":"item","numeric-id":725504,"id":"Q725504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2132515$031E72D1-37DC-46D9-8D1C-E6203F5B77DE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ad0932ba4b1671af6a3a2427bbae761755f29ca6","datavalue":{"value":"10.1016/J.LAA.2022.03.020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2132515$C3F42B49-8583-46A3-863D-89AC2BF4B3D0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e1cb24c35f1c1daca1d985c2abbb605e5b15fc3","datavalue":{"value":{"entity-type":"item","numeric-id":1641998,"id":"Q1641998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69570ae0ac07a1f49c31e2f03ca79f8b4fc561a6","datavalue":{"value":{"amount":"+0.7541736","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":"Q2132515$D65164A9-E2CD-4689-A8FB-BC1C804A49F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5676c7d73a10e3c1d7f4d17fca537003af0bfcef","datavalue":{"value":{"entity-type":"item","numeric-id":3622685,"id":"Q3622685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0ed02718e9ac04874f0a420bbe5296d5e104016","datavalue":{"value":{"amount":"+0.73400027","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":"Q2132515$CCEB338B-8667-43E5-A546-1DAC156C5F93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c45531cb60422d99d2c977b3267b57784160975","datavalue":{"value":{"entity-type":"item","numeric-id":3094871,"id":"Q3094871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0deb217cf1ee9673a2c26990f3e863746d00c08d","datavalue":{"value":{"amount":"+0.7216907","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":"Q2132515$97868CF1-65E9-4EB6-8869-572F18553DAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56f61663066625c04d20641e9e36e9da7de3fa61","datavalue":{"value":{"entity-type":"item","numeric-id":1414159,"id":"Q1414159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc681aa909698c3e1d66a1a7847964829ff9a55a","datavalue":{"value":{"amount":"+0.71154404","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":"Q2132515$ECBA904F-997C-46BC-B21C-9C3BB623E4D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5e376615b34f25a36ce04fcdb38d39cbd135e72","datavalue":{"value":{"entity-type":"item","numeric-id":5203037,"id":"Q5203037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46a840ea421f90487c1dac4c61a0f784acf1b367","datavalue":{"value":{"amount":"+0.71079165","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":"Q2132515$3977FE89-F350-4846-B22B-099590D92DFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b91b9c9fa6fc5b560878c5ecb984da0ab41d81df","datavalue":{"value":{"entity-type":"item","numeric-id":1107536,"id":"Q1107536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c3290e23456ace0ee87a96d03cdfe17dd390c25","datavalue":{"value":{"amount":"+0.7104677","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":"Q2132515$CEBBF5BB-0480-47B1-9EF7-7B0357C0E0FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6bf90574450bfd421c733729385ed42c20367436","datavalue":{"value":{"entity-type":"item","numeric-id":678856,"id":"Q678856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"896c1a23984374e54d11d8c3730264d29217fb2d","datavalue":{"value":{"amount":"+0.7048992","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":"Q2132515$7D06C288-4C13-4524-BAAB-0FA9A40994A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68a5d4e0f2e8c7eff7c75908e2cfb120739cb76d","datavalue":{"value":{"entity-type":"item","numeric-id":1923516,"id":"Q1923516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b0325a6c0e00ce7e8697244f912976e7162eefe","datavalue":{"value":{"amount":"+0.70398426","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":"Q2132515$B61162BD-2956-43BB-8F3B-D9A380F4C6B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e801e401988ce0c36db0ade4d1a28e178f41e0dd","datavalue":{"value":{"entity-type":"item","numeric-id":1940312,"id":"Q1940312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd2f74b211fc90270c523c24503da39ee2239b1e","datavalue":{"value":{"amount":"+0.70314074","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":"Q2132515$EF62264A-ECF9-48B9-BBF1-DBC6C913B076","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d1db8d97ad3592d4fcd43de2d80c79fb9651ae7","datavalue":{"value":{"entity-type":"item","numeric-id":1444642,"id":"Q1444642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc5c0f91ed75ecdb4f447c1233bf615dc7d1b67a","datavalue":{"value":{"amount":"+0.7009697","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":"Q2132515$2535BC09-2E51-4329-B8B9-1D263BC1F4A0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2132515","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2132515"}}}}}