{"entities":{"Q1094338":{"pageid":1105090,"ns":120,"title":"Item:Q1094338","lastrevid":69624906,"modified":"2026-04-13T08:17:18Z","type":"item","id":"Q1094338","labels":{"en":{"language":"en","value":"Strong linear independence in bottleneck algebra"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4025192"}},"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":"Q1094338$37974A31-14B3-43A9-9809-90221D066D39","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ca664bc4999e1cf64bdfc728bb2beb5d092ed8b7","datavalue":{"value":{"text":"Strong linear independence in bottleneck algebra","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1094338$407DE967-5717-4E08-AC02-3CA9CE5F3512","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d34e418338320be0869b22e0f2737a73107a4ce9","datavalue":{"value":"0629.90093","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094338$8CA13A71-4F83-4BF8-A59A-10DFE54405AD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3c11559aa85633b98a81e56a43fc7c41e44042f1","datavalue":{"value":"10.1016/0024-3795(87)90085-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094338$4045F420-01F0-487D-8F73-4A89C6EFEDDF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9a4d670917cd098f1e5c4668a00fca60ad0cf3a1","datavalue":{"value":{"entity-type":"item","numeric-id":628323,"id":"Q628323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094338$ED0A286C-3D2A-4BBF-9624-62E800197BFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ef7f9b00e70cc9184062d1b22183cdd374cca76e","datavalue":{"value":{"entity-type":"item","numeric-id":217085,"id":"Q217085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094338$41FDF519-5A7E-4D7C-8C1B-9DAF80C06F32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4d52c2c2b43c52164f3a6097277c563ef44e1032","datavalue":{"value":{"entity-type":"item","numeric-id":187116,"id":"Q187116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094338$CB7F309B-1B93-4A53-AF67-EBA1F94C0168","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":"Q1094338$13A4B2B9-C602-4A34-A988-42C13F8F4B70","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1094338$E7873267-656D-4BAC-96C3-D8C3BAF09F07","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"67b6d1e0df535bfdd5f4d1da6863b47c2c36c61a","datavalue":{"value":"Linear systems of the form  \\[  \\max_{1\\leq j\\leq n}\\min (a_{ij},x_ j)=b_ i\\quad (1\\leq i\\leq m)  \\]  have been treated in the literature for a long time [e.g. cf. \\textit{K. Zimmermann} [Extremalni algebra, Praha: Vyzkumn\u00e1 publicace Ekonomicko-matematick\u00e9 Laboratorie pri Ekonomick\u00e9m \u00fastava CSAV 46, 127 p. (1976)] or the reviewer [Linear and combinatorial optimization in ordered algebraic structures (1981; Zbl 0466.90045)]. Here, all coefficients \\(a_{ij}\\), \\(b_ i\\) are chosen from a dense, linearly ordered set (B,\\(\\leq)\\). If the linear system is uniquely solvable for some \\(b\\in B^ m\\) the columns in the matrix \\(A=(a_{ij})\\) are called strongly linearly independent. Square matrices with strongly independent columns are called strongly regular. An \\(m\\times n\\) matrix A has SLI-columns if and only if it contains a strongly regular matrix of size n. The matrix A is called trapezoidal, if \\(a_{kk}>\\max \\{a_{j}| \\quad 1\\leq i\\leq k,\\quad i<j\\leq n\\}\\) for all \\(1\\leq k\\leq m\\). It is proved that every strongly regular matrix A can be transformed into a trapezoidal matrix by suitable row- and column- permutations. Vice versa, every trapezoidal matrix is strongly regular. For the latter result, density of B is a necessary assumption. An O(m\\(\\cdot n\\cdot \\log (n))\\)-algorithm is developed which constructs the row- and column-permutations revealing a hidden trapezoidal matrix. It is well-known that the linear bottleneck assignment problem \\(\\max_{\\pi \\in S}\\min \\{a_{i\\pi (i)}| \\quad 1\\leq i\\leq n\\},\\) where S denotes the set of all permutations of \\(\\{\\) 1,2,...,n\\(\\}\\), can be solved in \\(O(n^{5/2}\\cdot \\log (n))\\) using binary search techniques. If A is trapezoidal, then the identity is optimal. If the linear bottleneck assignment problem has a unique optimal solution then A is proved to be strongly regular and, therefore, by revealing its hidden trapezoidal form, the linear bottleneck problem can be solved in \\(O(n^ 2\\cdot \\log (n))\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094338$2D2353EE-79DF-488B-965D-5D8BC45A9FEA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"029224feaa23c10bf0a20e7c543fe64f3de45a0f","datavalue":{"value":"90C48","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094338$F540B83A-B797-4515-B0C0-B750CEEC2E5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094338$538897F4-9E49-46EC-8D38-D4B6FF2BB128","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094338$EFD8A483-7A0D-4CD3-9DF8-66AF22641939","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ba5f7486cfb64f062d1b1d8e48f356198d5bc8e7","datavalue":{"value":"15A03","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094338$42993B95-57EC-4885-ADB6-CF1130B36D13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"72309745094959b676ca20810c7af21a33fe24b5","datavalue":{"value":"65F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094338$384C5CDD-72A3-4CC0-955F-836CA49AB26D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9e7be0cfcacd32464742957e3e818847a694f77f","datavalue":{"value":"06F15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094338$EC011302-5064-4489-A6C2-BD8D2093A4C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5f35883713e23ca3f0ced48b60a92f4891f4d526","datavalue":{"value":"15A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094338$4BBD82FA-4477-4161-B374-63A7B1358408","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094338$AA6537F6-1F5C-465E-973E-F8B307E81B2F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e8be0605c3db0bb4fc64d1f86e2655a52286c858","datavalue":{"value":"4025192","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094338$1FBB06BA-B56B-463E-9950-AF058541569C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1277c3701ab5fb4dbed3383eae37e4bebe932263","datavalue":{"value":"strong permanent","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094338$31543F71-DDEA-42F9-B4F6-5501E1833DBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9ab97e7d6643762319288955df85dd9aaf6ceb90","datavalue":{"value":"bottleneck algebra","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094338$B622064F-1400-4515-BE44-8A35E76D7135","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9025a2771adef255992e6e63e3f8d6378235f560","datavalue":{"value":"linear independence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094338$885C5B95-3292-4014-9ADD-62D7C2EA27F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"520d68cec4867838cf8496728bde00722e0e5c60","datavalue":{"value":"algebraic linear system","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094338$0D26C20E-7D79-4383-8F94-A162D3113BA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"680910986e1d1f2b7e698903fba7a57604992bfc","datavalue":{"value":"strongly independent columns","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094338$916B39FA-D6AE-4C63-BC5D-2C0D8EABFDAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f0887ea1d1900b802ab330a2af94079b440e0098","datavalue":{"value":"strongly regular matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094338$2AFBA341-08AE-437A-BD43-724E69387A94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc1165d7415a7a9d0db9f1307ed3aebfbbb5a71c","datavalue":{"value":"trapezoidal matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094338$C602479B-BAA0-4A10-9C68-F8575C7DC2F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0c2214bc66114d86cd8b5a6c0b0ca39c83aabb0","datavalue":{"value":"linear bottleneck assignment problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094338$40DE92AB-1904-4288-B8B3-2657FE421D71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"676288ca062a6644918e60d152d4abbdf19a9c2d","datavalue":{"value":"binary search techniques","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094338$C9F914D4-0163-4BD2-AA5C-9904D59CA912","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5500d0e3ae3870dfabd55c7acf03571be7dc260a","datavalue":{"value":{"entity-type":"item","numeric-id":1018087,"id":"Q1018087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094338$FEE40558-59C0-43F3-841B-8C94B8F5A341","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":"Q1094338$2653F764-4AB0-4D08-A9D8-B5D8221BFFC0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"827cc4dc511e7bfc546c4e83d8f7451ab5450d0b","datavalue":{"value":"https://doi.org/10.1016/0024-3795(87)90085-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1094338$E924D6DE-466B-4010-ABE7-38FA937FAD59","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"67c7d01cddba51cc179e6fb49b5cd7ab10c11589","datavalue":{"value":"W2128160792","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094338$071CB1D2-F10B-4192-8020-2456861A0346","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"86c1c81e24830603ae5e965c65ced070293a05b7","datavalue":{"value":{"entity-type":"item","numeric-id":3875737,"id":"Q3875737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094338$E77C3503-574E-4A98-9869-49BA3A8D76B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20ce1b78a9a65a9e5aa5d1107722dc82109408fa","datavalue":{"value":{"entity-type":"item","numeric-id":1082274,"id":"Q1082274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094338$896D057E-B944-4BE9-A86E-C1C58B6BE9BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af754bc1e3f2269411486b26cc21f89fea9178de","datavalue":{"value":{"entity-type":"item","numeric-id":3748087,"id":"Q3748087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094338$54873458-7C8B-452F-978F-36539943FB6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e4bd04b587c0758390f2e0ced121ecf83881a76","datavalue":{"value":{"entity-type":"item","numeric-id":3323698,"id":"Q3323698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094338$D24BB4A6-5457-4068-B034-253307D26A55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a339108f845f381ae162edfeda7b58a976de693","datavalue":{"value":{"entity-type":"item","numeric-id":1254944,"id":"Q1254944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094338$68D327C9-09F3-4366-B8F1-C11B4DBCEBA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff81489e80366438468bf6dfe10c7a159bc3ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4057549,"id":"Q4057549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094338$2751B8DB-FEEF-4858-B519-87E70E72A629","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094338$17350529-E70E-4F14-852B-B4434B02437F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f3d72d6f067eeebf02882fdf0a5f1edb3452f80","datavalue":{"value":{"entity-type":"item","numeric-id":1155513,"id":"Q1155513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094338$09F66E65-E7C2-4EC3-AC7B-18D45255D94F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50d34897c93a7dff0e4e8ca8e8e99d8e8e46ac93","datavalue":{"value":{"entity-type":"item","numeric-id":1314327,"id":"Q1314327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2c8fba94c763d1ab5e9c13ac06b767e7b81ee13","datavalue":{"value":{"amount":"+0.8633652925491333","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1094338$746B15A3-E82C-4A0B-A76D-37854FAE3A84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88a43131db1864e8198b37e003f2792b84bc6da9","datavalue":{"value":{"entity-type":"item","numeric-id":1200788,"id":"Q1200788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d30f8684be3707400ce22f7cf5acd0aa7f3cfa34","datavalue":{"value":{"amount":"+0.8576563596725464","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1094338$96CD59D9-E820-4A51-8D35-116E19D655A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79f748450a103740be4bc469a55f6046ad7a8c06","datavalue":{"value":{"entity-type":"item","numeric-id":916746,"id":"Q916746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17a46454285b700fe0fcfbaba7cd8f7e6382edec","datavalue":{"value":{"amount":"+0.8515800833702087","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1094338$C8849F1C-9762-4B5A-9B7D-229D365B4BDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4e7ab31556e67acdc0dd1d9f2685a11b1470d96","datavalue":{"value":{"entity-type":"item","numeric-id":4882913,"id":"Q4882913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b91d679465b3ee4ad7e17513cbef4fce2200eedb","datavalue":{"value":{"amount":"+0.8189898133277893","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1094338$7DD5CD29-EEBA-4607-AEB8-32FD73997347","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9761f7ab4563d59745a0f6d63df25c2bb414122","datavalue":{"value":{"entity-type":"item","numeric-id":1082274,"id":"Q1082274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6cef121e6522de58f818e657ecc91b16aee1784","datavalue":{"value":{"amount":"+0.8111533522605896","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1094338$EDF71843-73A1-462C-B72E-6FE92A074A2F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Strong linear independence in bottleneck algebra","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Strong_linear_independence_in_bottleneck_algebra"}}}}}