{"entities":{"Q1082773":{"pageid":1093525,"ns":120,"title":"Item:Q1082773","lastrevid":66098136,"modified":"2026-04-12T07:32:00Z","type":"item","id":"Q1082773","labels":{"en":{"language":"en","value":"Solving systems of linear equations over polynomials"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3974173"}},"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":"Q1082773$80C653B5-3EA6-4614-8CDB-F8DD7B5CBB21","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6ede86f0d030c4b62d534e8db27a2175d6e6771d","datavalue":{"value":{"text":"Solving systems of linear equations over polynomials","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1082773$33439EB2-F866-4618-BE0B-11EA855F660D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"52e0de92c5f3c4552397938f6c5b77330e1b72c7","datavalue":{"value":"0603.65024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082773$782B6E87-0CAD-4CEC-86D0-314D7C5FBCC7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"de699a20006c767093845ca73a48015fcb0b995c","datavalue":{"value":"10.1016/0304-3975(85)90131-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082773$389BB30B-5545-4F22-A101-2BB453442B1F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082773$29FB5AA4-3032-4C64-AA22-024F0649FF8C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1082773$1B0ADCDB-10CF-44AA-B421-714F078987BF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9e4e663c9e0718ec554821b73800badc19e34293","datavalue":{"value":"This is a generalization of an earlier work of the author and \\textit{A. Bachem} [SIAM J. Comput. 8, 499-507 (1979; Zbl 0446.65015)]. In this article a polynomial-time algorithm to derive the Hermite normal form of an \\(n\\times n\\) matrix A(x) of polynomials is given. The algorithm hinges on constructing and postmultiplying by a small multiplier matrix \\(K^{(i)}\\) for the ith stage of the algorithm then showing that at every stage of the algorithm the transformed matrix \\(A^{(i)}\\) satisfies: \\(| A^{(i)}| =length\\) of \\(A^{(i)}\\) viewed as an \\(n^ 2\\) vector, den (A\\({}^{(i)})=\\ell cm\\{den (a_{11}),...,den (a_{nn})\\}<(4nad)^{400n^{11}d^ 4}\\), and deg (A)\\(=\\max \\{\\deg a_{ij}(x)\\}\\leq 2n^ 3d\\) where n is the dimension of the original matrix A, a is its length, den is the denominator, \\(\\ell em\\) is the least common multiple, and d is its degree. This algorithm is then generalized to accommodate rectangular matrices and to obtain the Smith normal form based on the algorithm given by the author and A. Bachem [loc. cit.].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082773$D047FC3D-A3ED-411F-9620-862F9A75A793","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"72309745094959b676ca20810c7af21a33fe24b5","datavalue":{"value":"65F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082773$29451B96-EADA-4A5E-8C86-DC09DBCA80BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9d105b80ed6a98c28f7c2120246154d24eaf80df","datavalue":{"value":"15A54","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082773$A8A5EC07-69D7-4A1A-BC70-9780D75A4518","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"18fdfaf4061ac2b1a63276e0e14ee74dc6be4591","datavalue":{"value":"3974173","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082773$1BFFFACF-5F2D-4D97-A8F7-72AE7DF872A4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"21cd4c54751ae0cceacc6630af4ce9b7a739d4da","datavalue":{"value":"polynomial matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082773$7818892B-5C71-4087-9678-A86E997B54AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b950b00052cc385eaa0fb1baac8677736e6dc56","datavalue":{"value":"unimodular column operations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082773$FAC838CD-1675-4515-AABC-F7B7AF9B8576","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2363d166b5b9fc791a0d6228cc5a474e45585fdd","datavalue":{"value":"polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082773$09650176-941C-4EE1-8813-ADDF49941CA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d37f52485aed20b3a80c12d133c34b354959045","datavalue":{"value":"Hermite normal form","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082773$D9259A14-214C-424E-8A9C-81A66E48AD6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6d6fc08148042d73152ce88dd3c3f693c432b21","datavalue":{"value":"rectangular matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082773$3E0B8ECE-0E38-44E0-898F-55D308312DBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac114b5d8a78098b8aa8fc44237f76764506d509","datavalue":{"value":"Smith normal form","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082773$527CDC00-47F2-4C83-8517-966498D06342","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"17fd1dfe1d91df455619b1246ffef8f41c1d7bde","datavalue":{"value":{"entity-type":"item","numeric-id":1356891,"id":"Q1356891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082773$FACEC26E-70D9-418E-89BC-87F93C82B640","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":"Q1082773$9A0B0D55-79A0-457C-A5DD-4F0E1D3FA056","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e7770e28ee99e6a4208f57f4af00fe6ea2575d44","datavalue":{"value":"https://doi.org/10.1016/0304-3975(85)90131-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1082773$96E3D883-4A4E-4EAD-ACDD-1427D8339399","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"aa2c4dac16b86bdc5db57027cebbf29826aea425","datavalue":{"value":"W2027413053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082773$5D8C5FBA-C99B-40A9-A2CF-0E6BAEDC4ACB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"84812108f3045d1a7d33c4afc32d7a747dff1fb7","datavalue":{"value":{"entity-type":"item","numeric-id":4775731,"id":"Q4775731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082773$BA110904-98D6-450B-9689-4322EF48123D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2955bf641247cb3940efa557a127adca1fb7c4f2","datavalue":{"value":{"entity-type":"item","numeric-id":5641964,"id":"Q5641964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082773$599F3616-5F7C-4678-AB54-1A51B46C91B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2474ba10df186f41753af2a60b363dd32a238373","datavalue":{"value":{"entity-type":"item","numeric-id":5633583,"id":"Q5633583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082773$6C96FFEE-0EDD-489B-945D-AA6F7FC77FDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58ddf6c15587cc8d775178ac7830ee9b5995c206","datavalue":{"value":{"entity-type":"item","numeric-id":5532045,"id":"Q5532045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082773$B5E5CA93-C596-4022-A50B-A87B478B8FB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2dd40fa73f1db45e31030e77c0a76effcadcc130","datavalue":{"value":{"entity-type":"item","numeric-id":3963952,"id":"Q3963952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082773$904B84C6-59C9-4A0F-81C7-2C98FD174181","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a2ccaa8b67605d1442f748d22b53e4b3e37cf3a","datavalue":{"value":{"entity-type":"item","numeric-id":5564386,"id":"Q5564386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082773$8B5C669C-6859-4374-B05D-DB54C46F3B40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5fc4edc2cf68b37acd0562b2316804814e5e729","datavalue":{"value":{"entity-type":"item","numeric-id":4143385,"id":"Q4143385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082773$9D2C6A78-EC8C-4C97-8193-8868F18A60D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18596458fc7dece86871f7b993158f3e4166bf0c","datavalue":{"value":{"entity-type":"item","numeric-id":5613964,"id":"Q5613964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082773$94215649-BC0C-4DDE-9DAD-0FAB1578CF0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15112fb3f4baa3f1d7f3fa04f75aecf7f599ac96","datavalue":{"value":{"entity-type":"item","numeric-id":5591072,"id":"Q5591072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082773$3B1901C8-28E1-4862-B7C6-D7575E1D2FCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86be3b3bbd09bddbccf4c5b13560cf796d6ec8fc","datavalue":{"value":{"entity-type":"item","numeric-id":4045512,"id":"Q4045512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082773$2FA56086-BE07-4F4E-9327-0FE8A88B9944","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"530619720f5a922424645cd415ab45aabe5a5c4f","datavalue":{"value":{"entity-type":"item","numeric-id":5599374,"id":"Q5599374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082773$BC94FE04-68BE-4D5C-9C54-56BF155A4FC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20538ab31dbe4c0509fd81e10316a37d5a89639d","datavalue":{"value":{"entity-type":"item","numeric-id":5553606,"id":"Q5553606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082773$90BBC144-499E-49AA-BEEB-F1ED43D1C72F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3165438c92aed158e9ee66d8a5de489a8ab851f8","datavalue":{"value":{"entity-type":"item","numeric-id":1151859,"id":"Q1151859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082773$583F8B3A-B83A-4541-9941-E9E7DCFFE0DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08c816340aec0a02ceb2cbe6730ce93a4daa6f25","datavalue":{"value":{"entity-type":"item","numeric-id":5545677,"id":"Q5545677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082773$F03DDB18-67A8-440C-9F1A-E82F31C9D775","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3dcafb238e6ba98f691c336bb9a0d0dc6d0f213d","datavalue":{"value":{"entity-type":"item","numeric-id":3891677,"id":"Q3891677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082773$FD86BBE4-7BE8-45E7-B503-F557344F82D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa0540fd78fb7a7ac36ecb95287d9deaac0fb1e2","datavalue":{"value":{"entity-type":"item","numeric-id":5585021,"id":"Q5585021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082773$5A050078-DED7-445F-A669-B9B214641E42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b7ce81eaa2ce20370085e9653ef661dd2d1a706","datavalue":{"value":{"entity-type":"item","numeric-id":5533700,"id":"Q5533700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082773$79AB6649-EE54-4F51-AA11-E0069E3A5FB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cb3bf468e3a728f4d3f9b6ae888b16b3311e6e7","datavalue":{"value":{"entity-type":"item","numeric-id":5180761,"id":"Q5180761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082773$7F7C4662-35F9-4A1A-A104-53EE5D2796F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3e841a2718df2f0c15920defa773b7a7538ca33","datavalue":{"value":{"entity-type":"item","numeric-id":5668937,"id":"Q5668937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082773$0DF11414-E6C0-4C19-B46A-AEA94454D06B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e31f7d86208409a1f587a2f3e79ff111e4d23b2a","datavalue":{"value":{"entity-type":"item","numeric-id":5659396,"id":"Q5659396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082773$8A4FFAF9-A09A-4A7D-A236-929602CCE8E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b61ff41cba099dcf37e49b4b315b738fd1d4bf62","datavalue":{"value":{"entity-type":"item","numeric-id":5789039,"id":"Q5789039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082773$0C5BE252-A6E6-498C-84C1-06A2AC0CA68D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f81b72238928971a107ac0a51a003b566509d31a","datavalue":{"value":{"entity-type":"item","numeric-id":4109684,"id":"Q4109684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082773$AB3BF5DA-60DC-44E3-8B56-7B548D50F232","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54e5ba1bab8f949edecc62854c105232615327cf","datavalue":{"value":{"entity-type":"item","numeric-id":3223803,"id":"Q3223803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b62957ab922954c804d34fa38e9a06ac34e8ca3","datavalue":{"value":{"amount":"+0.8535694479942322","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":"Q1082773$3CA3EBE0-833F-44DF-BB28-C65771CD48DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b86ff9e164ec8877beb1d68ee9d399fc61fa1e1a","datavalue":{"value":{"entity-type":"item","numeric-id":1725693,"id":"Q1725693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5345eb1c30cab09e7192a10eef12742acfdae29","datavalue":{"value":{"amount":"+0.8429049849510193","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":"Q1082773$C3AC6CA0-CE81-44B5-B988-F84F4265551D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31afacbacc38dd43ba7acdc8835a773e75154b91","datavalue":{"value":{"entity-type":"item","numeric-id":4251976,"id":"Q4251976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fcf68e58b5984f0be4081a100b0023ff6e5c78b8","datavalue":{"value":{"amount":"+0.829616367816925","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":"Q1082773$0A9C9E20-4A1A-4CF2-9DAA-EFEB3BC49960","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4efdc747e6aa408fe9066e6e25e777c5c186df2b","datavalue":{"value":{"entity-type":"item","numeric-id":4227351,"id":"Q4227351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6abca0492d1166cc7151c5121400692e49ca5b8","datavalue":{"value":{"amount":"+0.8223164081573486","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":"Q1082773$6E7A506A-CE4E-4757-9C79-EE9297812949","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d0bfd26bd549f2d1c22e6086a8fccf7e57986d7","datavalue":{"value":{"entity-type":"item","numeric-id":2402419,"id":"Q2402419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c750d5abcf649baada3bd8a5d8089ae9abe5e00f","datavalue":{"value":{"amount":"+0.8223162889480591","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":"Q1082773$25423E2D-DAE7-4FE7-A682-F575E70E6778","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Solving systems of linear equations over polynomials","badges":[]}}}}}