{"entities":{"Q916672":{"pageid":918520,"ns":120,"title":"Item:Q916672","lastrevid":65358435,"modified":"2026-04-12T02:03:00Z","type":"item","id":"Q916672","labels":{"en":{"language":"en","value":"Coherent algebras and the graph isomorphism problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4154472"}},"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":"Q916672$B2953055-EB7C-4F75-8CB2-033BA9F21B43","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0b09ea68c6686ad1d1cc91ae5e5641f2e5090a18","datavalue":{"value":{"text":"Coherent algebras and the graph isomorphism problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q916672$6B399531-EBC6-402A-A7F2-6DD77C557DFC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3f84a0f28f4e4e538b5d53b8188b83270f1c2c4d","datavalue":{"value":"0704.05023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916672$DD1D0E74-264B-4C4E-9ADF-47669BD2B674","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ec5549c27a24e716da0683e04e483cc5a4bbc3da","datavalue":{"value":"10.1016/0166-218X(89)90047-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916672$A460BFF9-3E56-49F5-AA30-152168A70429","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fb8d03a1cb641c5e672713d8a741c39c10de5a0c","datavalue":{"value":{"entity-type":"item","numeric-id":586373,"id":"Q586373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916672$9437C7C0-F362-415F-AA76-405B69984E31","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916672$8C428C26-4071-4CAF-97DA-669664FA34CD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q916672$377021E0-8D41-4407-9773-03D837652F78","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"05a1d61726946b5cf754e8e07d5b87a84d7dabd1","datavalue":{"value":"Let \\(M_ n\\) be the algebra of \\(n\\times n\\) complex-valued matrices, o denote the Hadamard (element-wise) product of two matrices in \\(M_ n\\), * denote complex conjugate and I be the identity matrix and J the all-one matrix in \\(M_ n\\). A subalgebra \\({\\mathcal A}\\) of \\(M_ n\\) is called a coherent algebra if it is closed under o and * and I and J belong to it. By definition it is semisimple. If \\({\\mathcal A}\\) contains I as a basis element, then it is called homogeneous. A matrix \\(A\\in {\\mathcal A}\\) is called generic if its eigenvalues have smallest multiplicity. \\({\\mathcal A}\\) is said to have a simple spectrum if it has a generic matrix A with simple eigenvalues. \\({\\mathcal A}\\) is said to have multiplicity at most k if it has a generic matrix A, every eigenvalue of which has multiplicity at most k.    An isomorphism of coherent algebras \\({\\mathcal A}\\), \\({\\mathcal B}\\) is an algebra isomorphism i which preserves o, commutes with * and preserves the matrix J. Such an isomorphism i is said to be strong if for every \\(A\\in {\\mathcal A}\\) there is an \\(n\\times n\\) permutation matrix P such that \\(i(A)=PAP^*.\\)    After reviewing the basic properties of coherent algebras, the author proves that the strong isomorphism problem for two isomorphic coherent algebras is equivalent to the isomorphism problem for two regular multigraphs having the same degrees, thus bringing out the importance of the former. The main contribution of the author to the solution of the former is the proof that every isomorphism between two coherent algebras with simple spectra is a strong isomorphism. The homogeneous algebras are used as an important reduction tool. The nonsimple case has been studied by embedding the given algebras in bigger ones (of higher dimension) but less multiplicity. The investigation is inconclusive and a plausible conjecture is proposed.    The author makes contact with earlier works by \\textit{D. G. Higman} [Linear Algebra Appl. 93, 209-239 (1987; Zbl 0618.05014)] and \\textit{B. Weisfeiler} [On construction and identification of graphs (1976; Zbl 0336.05019)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q916672$5B14E5C4-E61B-4A7B-93C5-8798A3DCB548","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916672$0AFEEE99-B03C-429F-A232-758B0A9146B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916672$0C7F3AAF-CAD8-4DFD-943C-5C3946D90C73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916672$F551F089-2C71-4047-A2FB-463036EC3539","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1d74c5d3539ef56f7fa2d6d1e9aadc163746a9d6","datavalue":{"value":"4154472","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916672$D7724750-AE77-49F4-8241-8E3A603E24EC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9e9d59860cf0ab2ff157be6ed540e70a5a2a53ea","datavalue":{"value":"coherent algebra","type":"string"},"datatype":"string"},"type":"statement","id":"Q916672$59FAF054-6776-4F8F-88A1-AD29399CDF2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ae1326bf30e01c4822a8e26ef94ba62669ebc879","datavalue":{"value":"simple spectrum","type":"string"},"datatype":"string"},"type":"statement","id":"Q916672$0B502AB6-C866-4390-B8FA-85E915A9B5CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec3505d4a1a47ba6779c1bc97acbae985df00be0","datavalue":{"value":"isomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q916672$00E87DAC-4E5F-4E6D-A4CC-0F40349B7CDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"67dea5f72dad352eec3c7330d77a366b95431927","datavalue":{"value":"strong isomorphism problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q916672$6B633197-FB11-42F4-91C0-54CD407DAEE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8123f14b8420b58c5f83acca22c617d824a511fd","datavalue":{"value":"homogeneous algebras","type":"string"},"datatype":"string"},"type":"statement","id":"Q916672$3DCFEC19-C89E-4DDF-82B2-D18A57E5D5C2","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":"Q916672$3970BDBF-9ABD-4FB8-9168-61AECD84C5BB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ed1e3868cfed1b6749cf6e45a29b73a0b33c3dc","datavalue":{"value":{"entity-type":"item","numeric-id":3218140,"id":"Q3218140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916672$CAB1E387-3876-4EB9-BCF7-B5DDD2DEAD87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa8e498d188a6a4fedf19be5e45f4e73ce52c271","datavalue":{"value":{"entity-type":"item","numeric-id":5707657,"id":"Q5707657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916672$9777EF8B-F0F0-4D8F-A5F5-4E4394E123EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbc77efa9189fad2ea756d9326a71afa072c9191","datavalue":{"value":{"entity-type":"item","numeric-id":1063120,"id":"Q1063120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916672$1D8B8722-C94F-45BE-8D1F-EE4DB728C5A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c824cb0b8ddceceb6b011c19f22c7bccde38e3b4","datavalue":{"value":{"entity-type":"item","numeric-id":3883024,"id":"Q3883024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916672$C659F8D1-1A1F-49FD-B8DC-4EA4C9594767","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fef41b8219dc56731e310b6ea0b4eb5ce87e45c9","datavalue":{"value":{"entity-type":"item","numeric-id":4198777,"id":"Q4198777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916672$18A34827-B1BA-4FAB-BBAB-35136922DDC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b106181fd9af062c083ce4ba3ab4b939f8b3dc75","datavalue":{"value":{"entity-type":"item","numeric-id":1228617,"id":"Q1228617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916672$5A726436-5052-4035-A56D-CEFDA9BA60C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd40c4a3cc5b2bc125ef875854ec9e6148ee3ff1","datavalue":{"value":{"entity-type":"item","numeric-id":1088992,"id":"Q1088992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916672$F469CEA1-CF9C-4F9F-959F-BF21ABAEC964","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"655cd01a9e2d62745e2c635f6258f44bf326d652","datavalue":{"value":{"entity-type":"item","numeric-id":3955947,"id":"Q3955947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916672$7C3126B0-1AC3-4EB6-97F5-8743D22F7EC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae3f853a816c990699349ba249f035d7e17ab4ec","datavalue":{"value":{"entity-type":"item","numeric-id":2515174,"id":"Q2515174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916672$59F38458-30D2-486B-80FE-9E452508DC25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"141794a00237295986f00275c27aee9706b73f5b","datavalue":{"value":{"entity-type":"item","numeric-id":1241450,"id":"Q1241450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916672$88380A99-1AF7-47A1-BEA4-1D16226F920A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"795e4678d341f9f755f5982ad54550ca4f0e4423","datavalue":{"value":{"entity-type":"item","numeric-id":1328437,"id":"Q1328437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4368b14d80cf8c06ffa26866cb78cf47244a7fd","datavalue":{"value":{"amount":"+0.93767184","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q916672$BD034C28-36A4-4761-8B27-BB2238437B69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5925c0407ee86bb065c898b88c948bb320df077","datavalue":{"value":{"entity-type":"item","numeric-id":5693404,"id":"Q5693404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7178f6d7de9d4471454063515b2a90221ca58377","datavalue":{"value":{"amount":"+0.91422015","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q916672$4B0270FB-90B3-4790-B93A-1F7C2581DFFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ed1a55f9e6ce115f08b89afa1dff68d4adc4b0a","datavalue":{"value":{"entity-type":"item","numeric-id":5097418,"id":"Q5097418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7eb895cfe3eb92d417c69bee2dae16dd7708e07","datavalue":{"value":{"amount":"+0.91052675","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q916672$67DBD8AB-DB0C-49E6-B42E-18EAEF92045A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d24a12be9336a409773d07bd8c0c4a315b198a54","datavalue":{"value":{"entity-type":"item","numeric-id":4312231,"id":"Q4312231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c3babaa7cf34d9f6f57c5bf4fa6a1f48fc0aa63","datavalue":{"value":{"amount":"+0.9000953","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q916672$2E21297F-58F8-4912-A96F-D4FC841D91DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15528528eeb10fbe684b7729953228c574f13365","datavalue":{"value":{"entity-type":"item","numeric-id":707433,"id":"Q707433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03f1623a5daf5df0d80a3e63d8aa0b8af4124399","datavalue":{"value":{"amount":"+0.89247614","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q916672$E9564B76-4FF8-4E13-A5ED-4EBA07CB9E5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e010dbea31db982d9bd0ffebe503ee5f8ecf2c9f","datavalue":{"value":{"entity-type":"item","numeric-id":5200206,"id":"Q5200206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b7b647a7562ed3e0964ff894edd8daf5b2b7c394","datavalue":{"value":{"amount":"+0.8909246","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q916672$5C5547B7-B9F4-4F1A-BB12-C6AD5F7D1450","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"709afde81a8a9757ee5cb08d14a663877f375af7","datavalue":{"value":{"entity-type":"item","numeric-id":1088992,"id":"Q1088992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5198568dcb6f7590ccb2eb0d4abf29e8c9b91494","datavalue":{"value":{"amount":"+0.89061344","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q916672$D495E860-1D26-476F-804A-806872FBA3FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8de89042bad7ab5d4ca58e620ade5706f31fb7a3","datavalue":{"value":{"entity-type":"item","numeric-id":5701017,"id":"Q5701017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63f7cf27d8487151520c6b05e1d202620d9e4b9e","datavalue":{"value":{"amount":"+0.8898629","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q916672$CC1F5F9A-0D47-4C58-B98A-54519F6CF50C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad39b86bb3ec1037a14c988a18ef0be5dc4806b7","datavalue":{"value":{"entity-type":"item","numeric-id":2949666,"id":"Q2949666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9f6b4b247b5f58c2dc40c79c80ec2a6523759f9","datavalue":{"value":{"amount":"+0.88967085","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q916672$0C174D30-5A6B-4462-870B-FFA03C0A437A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9dbfad506e04f00af2c7f0cec8d6496976af3e7a","datavalue":{"value":{"entity-type":"item","numeric-id":2975007,"id":"Q2975007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"008aa245410dbf0322d5d80870475092fcb26b65","datavalue":{"value":{"amount":"+0.8891523","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q916672$DC468A98-B242-46DD-A78F-28677EE6CEFA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Coherent algebras and the graph isomorphism problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Coherent_algebras_and_the_graph_isomorphism_problem"}}}}}