The group isomorphism problem is to determine whether two groups, given by their Cayley (multiplication) tables, are isomorphic. The problem is among a few classes of problems in NP that are not known to be solvable in polynomial time or NP-Complete [24]. The group isomorphism problem and its variants have close connections to cryptography, computational group theory, and algebraic complexity theory [30]. Furthermore, following Babai's breakthrough on the quasi-polynomial time algorithm for graph isomorphism [4,5], group isomorphism has become a bottleneck for an 𝑛 𝑜 (log 𝑛) time algorithm of graph isomorphism because group isomorphism reduces to graph isomorphism.
The group isomorphism problem has been extensively studied since the 1970s [7, 8, 11, 16-18, 21, 22, 25, 26, 32, 34-36, 38, 39, 41-45, 50, 54, 55]. A simple algorithm for group isomorphism, attributed to Tarjan, picks a generating set in one of the groups and checks for all possible images of the generating set in the other group, whether the partial correspondence extends to an isomorphism [39]. Since every group of order 𝑛 has a generating set of size at most log 2 𝑛, this algorithm results in an 𝑛 log 2 𝑛+𝑂 (1) running time. The current best-known algorithm for the group isomorphism problem has an 𝑛 (1/4+𝑜 (1)) log 2 𝑛 running time [43].
It is long believed that the isomorphism testing of 𝑝-groups of class 2 and exponent 𝑝 is a major bottleneck for the group isomorphism problem [7,15,17,18,35,36,43]. A group 𝐺 is a 𝑝-group of (nilpotent) class 2 and exponent 𝑝 for some prime number 𝑝 if every element except the identity has an order of 𝑝, and 𝐺 is not abelian but [𝐺, [𝐺, 𝐺]] only contains the identity element, where [𝐺, 𝐻 ] denotes the group generated by 𝑥𝑦𝑥 -1 𝑦 -1 for all 𝑥 ∈ 𝐺, 𝑦 ∈ 𝐻 .
The best-known algorithm for the isomorphism testing of 𝑝groups of class 2 and exponent 𝑝 does not have a major advantage in the running time, being 𝑛 𝑂 (log 2 𝑛) [43], over the general groups, even though the structure of 𝑝-groups of class 2 and exponent 𝑝 was well understood [13,51,54,55], and the isomorphism testing of this group class has been studied in depth [15,17,18,35,36,43,46]. Hence, to develop a better algorithm for isomorphism testing of general groups, it is necessary to provide a faster algorithm for 𝑝-groups of class 2 and exponent 𝑝.
In this paper, we present an isomorphism testing algorithm for 𝑝-groups of class 2 and exponent 𝑝 with 𝑛 𝑜 (log 𝑛) running time for any odd prime 𝑝.
Theorem 1.1. Let 𝐺 and 𝐻 be two groups of order 𝑛. If both 𝐺 and 𝐻 are 𝑝-groups of class 2 and exponent 𝑝 for some prime number 𝑝 > 2, then given the Cayley tables of 𝐺 and 𝐻 , there is an algorithm with running time 𝑛 𝑂 ( (log 𝑛) 5/6 ) to determine whether 𝐺 and 𝐻 are isomorphic.
Theorem 1.1 utilizes the Baer's correspondence [13], which reduces the group isomorphism problem for 𝑝-groups of class 2 and exponent 𝑝 to the isometry testing problem of skew-symmetric matrix spaces.
A square matrix 𝐴 is a skew-symmetric matrix if 𝐴 𝑇 = -𝐴. In the isometry testing problem for skew-symmetric matrix spaces, the input consists of the linear bases of two skew-symmetric matrix spaces 𝔄 and 𝔅. The problem is to decide whether there is an isometry 𝑆 from 𝔄 to 𝔅, i.e., an invertible matrix 𝑆 such that 𝑆𝔄𝑆 𝑇 = 𝔅, where 𝑆𝔄𝑆 𝑇 is the linear span of the matrices 𝑆𝐴𝑆 𝑇 for all the matrices 𝐴 ∈ 𝔄. We prove the following result for the isometry testing problem of skew-symmetric matrix spaces.
Theorem 1.2. Let 𝔄 and 𝔅 be two linear matrix spaces, both of dimension 𝑚, such that every matrix in 𝔄 or 𝔅 is an 𝑛 × 𝑛 skew-symmetric matrix over F 𝑝 for some prime number 𝑝 > 2 and positive integers 𝑚, 𝑛. There is an algorithm with running time 𝑝 𝑂 ( (𝑛+𝑚) 1.8 •log(𝑝)) to determine whether there is an invertible 𝑛 × 𝑛 matrix 𝑆 over F 𝑝 such that 𝑆𝔄𝑆 𝑇 = 𝔅.
We obtain Theorem 1.2 by combining several new tools to analyze matrix spaces, including an individualization-refinement method for matrix spaces, a characterization of low rank matrix spaces, and a reduction from the isometry testing of skew-symmetric matrix spaces to the isometry testing of skew-symmetric matrix tuples [30].
To obtain Theorem 1.1, let 𝑘 denote log 𝑝 (𝑛). We apply Theorem 1.2 for the case of 𝑘 > (log 2 (𝑝)) 5 by constructing the skewsymmetric matrix spaces for both input groups according to the Baer's correspondence [13]. Theorem 1.2 implies the running time for this case is 𝑛 𝑂 ( (log 𝑛) 5/6 ) . For the case of 𝑘 ≤ (log 2 (𝑝)) 5 , we run the aforementioned generating set enumeration algorithm [39]. Because every 𝑝 group of order 𝑝 𝑘 has a generating set of size at most 𝑘, the running time of the algorithm for this case is 𝑝 𝑂 (𝑘 2 ) , which is also 𝑛 𝑂 ( (log 𝑛) 5/6 ) .
The group isomorphism problem has been studied for variant group classes. Polynomial time algorithms have been developed for abelian groups [32,45,50], groups formed by semidirect products of an abelian group and a cyclic group [34,54,55], groups with normal Hall subgroups [42], groups with abelian Sylow towers [11], and groups with no abelian normal subgroups [8]. Dietrich and Wilson recently showed that the group isomorphism problem can be solved in nearly linear time for most orders [21].
For 𝑝-groups of class 2 and exponent 𝑝, algorithms for some nontrivial subclasses of this group class have been proposed [17,18,35]. Li and Qiao showed that if the 𝑝-groups of class 2 and exponent 𝑝 are generated randomly, then the isomorphism testing problem can be solved in polynomial time in the average case [36]. In [15], the average case running time was further improved to linear. In this work, we focus on the isomorphism testing for 𝑝-groups of class 2 and exponent 𝑝 in the worst case.
The refinement methods, such as the naive refinement [9] and Weisfeiler-Leman refinement [52], have been powerful tools for the graph isomorphism problem. The refinement methods have been successfully used for graph isomorphism testing algorithms [2, 3, 6, 9, 10, 12, 19, 20, 27-29, 33, 37, 40, 47, 48, 53, 56], including the celebrated quasi-polynomial time algorithm for graph isomorphism [4,5].
The refinement approach does not extend to groups in a naive way. Several representations of groups that allow refinement have been proposed. In [15], the authors defined a hypergraph using recursively refinable filters and proposed applying the Weisfeiler-Leman refinement on the hypergraph. Brachter and Schweitzer proposed defining colors of group element tuples by group operation patterns of the elements involved in the tuple and applying the Weisfeiler-Leman refinement to refine the colors of element tuples [14]. Both approaches can distinguish between several nonisomorphic constructions of 𝑝-groups of class 2 and exponent 𝑝. However, it was unclear how these refinement methods could be used to develop faster worst case isomorphism testing algorithms.
The isometry testing of skew-symmetric matrix spaces was studied in [16,25,26,36]. Its applications in cryptography were investigated in [15,31,49].
We give the notations and previous results used in this paper.
Throughout the paper, the vectors and matrices are over F 𝑝 for a prime number 𝑝 > 2. Let F 𝑛 𝑝 be the linear space of row vectors of length 𝑛 over F 𝑝 . Unless specified, the vectors are row vectors. We use ⟨•⟩ to denote the linear span.
Matrices. Let 𝑀 (𝑛, F 𝑝 ) (and respectively 𝑀 (𝑚, 𝑛, F 𝑝 )) be the linear space of 𝑛 × 𝑛 (and respectively 𝑚 × 𝑛) matrices over F 𝑝 . Let GL(𝑛, F 𝑝 ) be the group of 𝑛 × 𝑛 invertible matrices over F 𝑝 .
For a matrix 𝐴 ∈ 𝑀 (𝑚, 𝑛, F 𝑝 ), let rank (𝐴) be the rank of 𝐴, and 𝐴 𝑇 be the transpose of 𝐴. A square matrix 𝐴 ∈ 𝑀 (𝑛, F 𝑝 ) is a skewsymmetric matrix if and only if 𝐴 = -𝐴 𝑇 . For any 1 ≤ 𝑖 ≤ 𝑚, 1 ≤ 𝑗 ≤ 𝑛, let 𝐴[𝑖, 𝑗] be the entry of 𝐴 in the 𝑖-th row and 𝑗-th column.
For two matrices 𝐴, 𝐵 ∈ 𝑀 (𝑚 × 𝑛, F 𝑝 ), 𝐴 is lexically smaller than 𝐵 if there exist 1 ≤ 𝑞 ≤ 𝑚 and 1 ≤ 𝑟 ≤ 𝑛 such that the following conditions hold:
Matrix Tuples and Matrix Spaces. An 𝑚 ×𝑛 matrix tuple A of length 𝑘, denoted as A = (𝐴 1 , . . . , 𝐴 𝑘 ), is an element in 𝑀 (𝑚, 𝑛, F 𝑝 ) 𝑘 . For any 𝑃 ∈ 𝑀 (𝛼, 𝑚, F 𝑝 ) and 𝑄 ∈ 𝑀 (𝑛, 𝛽, F 𝑝 ) with some positive integers 𝛼 and 𝛽, let
An 𝑚 × 𝑛 matrix space 𝔄 is a linear subspace of 𝑀 (𝑚, 𝑛, F 𝑝 ). For any 𝑃 ∈ 𝑀 (𝛼, 𝑚, F 𝑝 ) and 𝑄 ∈ 𝑀 (𝑛, 𝛽, F 𝑝 ) with some positive integers 𝛼 and 𝛽, let
Since any linear combination of skew-symmetric matrices of the same dimension is also a skew-symmetric matrix, we use SS(𝑛, F 𝑝 ) to denote the linear space of all the 𝑛 × 𝑛 skew-symmetric matrices.
We define equivalence relations for matrix tuples. Definition 2.1 (Matrix tuple equivalence). Let A = (𝐴 1 , . . . , 𝐴 𝑘 ) and B = (𝐵 1 , . . . , 𝐵 𝑘 ) be two matrix tuples in 𝑀 (𝑚, 𝑛, F 𝑝 ) 𝑘 . A and B are equivalent if there exist two matrices 𝑃 ∈ GL(𝑚, F 𝑝 ) and 𝑄 ∈ GL(𝑛, F 𝑝 ) such that 𝑃 A𝑄 = B.
Definition 2.2 (Skew-symmetric matrix tuple isometry). Let A = (𝐴 1 , . . . , 𝐴 𝑘 ) and B = (𝐵 1 , . . . , 𝐵 𝑘 ) be two skew-symmetric matrix tuples in SS(𝑛, F 𝑝 ) 𝑘 . A and B are isometric if there exists a matrix
In this paper, we use the algorithm for the isometry testing of two skew-symmetric matrix tuples (Theorem 2.4) and the algorithm for the equivalence testing of two matrix tuples (Theorem 2.3), both proposed by Ivanyos and Qiao in [30].
Theorem 2.3 (Proposition 3.2 of [30]). Given two matrix tuples A = (𝐴 1 , . . . , 𝐴 𝑘 ) and B = (𝐵 1 , . . . , 𝐵 𝑘 ) in 𝑀 (𝑚, 𝑛, F 𝑝 ) 𝑘 for some prime 𝑝 > 2 and positive integers 𝑘, 𝑚 and 𝑛, there is an algorithm with running time poly(𝑘, 𝑛, 𝑚, 𝑝) to determine whether A and B are equivalent.
Theorem 2.4 (Theorem 1.7 of [30]). Let A = (𝐴 1 , . . . , 𝐴 𝑘 ) and B = (𝐵 1 , . . . , 𝐵 𝑘 ) be two skew-symmetric matrix tuples of length 𝑘 such that the matrices in A and B are of dimension 𝑛 × 𝑛 over F 𝑝 for some prime 𝑝 > 2. There is an algorithm with running time poly(𝑛, 𝑘, 𝑝) to determine whether there is an isometry from A to B. If yes, the algorithm also returns an isometry from A to B.
Following the definitions for matrix tuples, we also define the isometry of skew-symmetric matrix spaces.
Definition 2.5 (Skew-symmetric matrix space isometry). Let 𝔄, 𝔅 be two skew-symmetric matrix spaces. 𝔄 and 𝔅 are isometric if there exists a matrix 𝑃 ∈ GL(𝑛, F 𝑝 ) such that 𝑃𝔄𝑃 𝑇 = 𝔅. 𝑃 is called an isometry from 𝔄 to 𝔅 if 𝑃 exists.
In Section 2.3, we will use the Baer's correspondence to reduce the group isomorphism for 𝑝-groups of class two and exponent 𝑝 to the problem of isometry testing for skew-symmetric matrix spaces.
For a 𝑝-group of nilpotent class 2 and exponent 𝑝, let 𝑝 𝑘 denote the order of the group. Because of the class two and exponent 𝑝 condition, 𝐺/𝑍 (𝐺) is isomorphic to Z 𝑛 𝑝 , and [𝐺, 𝐺] is isomorphic to Z 𝑚 𝑝 for some positive integers 𝑛 and 𝑚 such that 𝑛 + 𝑚 ≤ 𝑘, where 𝑍 (𝐺) denotes the center of 𝐺, and [𝐺, 𝐺] denotes the group generated by 𝑥𝑦𝑥 -1 𝑦 -1 for all 𝑥, 𝑦 ∈ 𝐺. Taking an arbitrary basis of 𝐺/𝑍 (𝐺), an arbitrary basis of [𝐺, 𝐺], and taking the commutator bracket, we obtain a skew-symmetric bilinear map 𝑏 𝐺 :
𝑝 , which can be represented by a skew-symmetric matrix tuple G = (𝐺 1 , . . . , 𝐺 𝑚 ) such that every 𝐺 𝑖 is a matrix in SS(𝑛, F 𝑝 ). Such a skew-symmetric matrix tuple is called a skew-symmetric matrix tuple of 𝐺.
For two 𝑝-groups 𝐺 and 𝐻 of nilpotent class 2 and exponent 𝑝, it is necessary for 𝐻 to be isomorphic to 𝐺 that
The following theorem, also called Baer's correspondence, was proved by Baer in [13].
Theorem 2.6 (Baer's correspondence [13], rephrased). Let 𝐺 and 𝐻 be two 𝑝-groups of class two and exponent 𝑝 for some prime number 𝑝 with the same order. Let G and H be the skew-symmetric matrix tuples of 𝐺 and 𝐻 , respectively. If both G and H are 𝑛×𝑛 skewsymmetric matrix tuples of length 𝑚, then 𝐺 and 𝐻 are isomorphic if and only if there are matrices 𝑃 ∈ GL(𝑛, F 𝑝 ) and 𝑄 ∈ GL(𝑚, F 𝑝 ) such that
Furthermore, we can also represent skew-symmetric matrix tuples of groups by skew-symmetric matrix spaces. Given an arbitrary skew-symmetric matrix tuple G of group 𝐺, the skew-symmetric matrix space 𝔊 of 𝐺 is the linear matrix space spanned by matrices in G. Hence, Baer's correspondence can be rephrased as follows.
Corollary 2.7. Let 𝐺 and 𝐻 be two 𝑝-groups of class two and exponent 𝑝 for some prime number 𝑝 with the same order. Let 𝔊 and ℌ be the skew-symmetric matrix spaces of 𝐺 and 𝐻 , respectively. 𝐺 and 𝐻 are isomorphic if and only if 𝔊 and ℌ are isometric.
We provide an overview of the algorithm for the isometry testing of skew-symmetric matrix spaces (Theorem 1.2).
The main idea of proving Theorem 1.2 is to reduce the isometry testing of skew-symmetric matrix spaces to the isometry testing of skew-symmetric matrix tuples, which can be solved efficiently by Theorem 2.4. The difference between the two problems is that the correspondence between matrices from two matrix tuples is fixed by the indices of the matrices, whereas for matrix spaces, no such correspondence is given.
For an input of the skew-symmetric matrix space isometry testing problem, let 𝑚 be the dimension of the input matrix spaces and 𝑛 be the number of rows (or columns) for each square matrix in the matrix spaces. If one enumerates all the possible correspondences between the matrices of the two matrix spaces, then the running time of the algorithms is 𝑂 (𝑝 𝑚 2 • poly(𝑚, 𝑛, 𝑝)), which offers no improvement on the isomorphism of 𝑝-groups of class 2 and exponent 𝑝.
In this work, we give a 𝑝 𝑂 ( (𝑛+𝑚) 1.8 •log 𝑝) time reduction to the skew-symmetric matrix tuple isometry problem. The reduction is obtained by investigating several new tools for analyzing the structure of skew-symmetric matrix spaces, including a matrix space individualization-refinement method (Section 3.1) and a characterization of the low rank matrix spaces (Section 3.2).
One powerful technique for graph isomorphism is the method of individualization-refinement [2-4, 6, 9, 12, 19, 47, 48, 56]. For graphs, the individualization-refinement method first chooses a set of a small number of vertices and assigns each chosen vertex a distinct vertex color, and then it refines the vertex colors by assigning distinguished vertices different colors in a canonical way until vertices of the same color cannot be further distinguished.
A natural question for the group isomorphism problem is whether it is possible to define individualization-refinement operations for group isomorphism. Based on the connection between group isomorphism for 𝑝-groups of class 2 and exponent 𝑝 and the skewsymmetric matrix space isometry problem [13], Li and Qiao proposed a matrix space individualization-refinement method, which follows the individualization-refinement for random graphs [9], and analyzed the isometry testing of skew-symmetric matrix spaces in the average case [36].
In this work, we propose a different matrix space individualizationrefinement to enable the analysis of the isometry of skew-symmetric matrix spaces in the worst case. Consider an 𝑚 × 𝑛 matrix space 𝔄. The individualization in our scenario is defined by a left individualization matrix 𝐿 and a right individualization matrix 𝑅, where 𝐿 is a matrix with 𝑚 columns and 𝑅 is a matrix with 𝑛 rows. In the refinement, we compute 𝐿𝐴𝑅 for each matrix 𝐴 ∈ 𝔄. If 𝐿𝐴 ′ 𝑅 does not equal 𝐿𝐴 ′′ 𝑅 for some 𝐴 ′ , 𝐴 ′′ ∈ 𝔄, then 𝐴 ′ and 𝐴 ′′ are distinguished.
Ideally, if 𝐿𝐴 ′ 𝑅 does not equal 𝐿𝐴 ′′ 𝑅 for any two matrices 𝐴 ′ and 𝐴 ′′ in 𝔄, then each matrix 𝐴 in the space can be uniquely identified by 𝐿𝐴𝑅, and thus all the matrices in 𝔄 are distinguished. Consider two isometric skew-symmetric matrix spaces 𝔄 and 𝔅. Let 𝐿 𝔄 and 𝑅 𝔄 be individualization matrices for 𝔄 that distinguish all the matrices in 𝔄. Let 𝐿 𝔅 and 𝑅 𝔅 be individualization matrices for 𝔅 such that 𝐿 𝔅 = 𝐿 𝔄 𝑆 -1 and 𝑅 𝔅 = 𝑆 𝑇 -1 𝑅 𝔄 for some isometry 𝑆 from 𝔄 to 𝔅. One can distinguish all the matrices in both spaces by their individualization matrices and then establish a bijection between the matrices in the two spaces. Thus the skew-symmetric matrix space isometry problem reduces to the skew-symmetric matrix tuple isometry problem, which can be efficiently solved by Theorem 2.4. Furthermore, suppose 𝐿 𝔄 contains a small number of rows and 𝑅 𝔄 contains a small number of columns.
Then one can solve the skew-symmetric matrix space isometry problem efficiently by enumerating all the possible corresponding 𝐿 𝔅 and 𝑅 𝔅 . We show that the number of rows for the left individualization matrices and the number of columns for the right individualization matrices are related to the rank of matrices in the matrix space. Lemma 3.1. Let 𝔄 be a 𝑑-dimensional matrix subspace of 𝑀 (𝑚, 𝑛, F 𝑝 ) for a prime 𝑝 and some positive integers 𝑑, 𝑚, 𝑛. For any 𝑘 ≥ 4, denote
There is a left individualization matrix 𝐿 ∈ 𝑀 (𝑡, 𝑚, F 𝑝 ) and a right individualization matrix 𝑅 ∈ 𝑀 (𝑛, 𝑡, F 𝑝 ) such that for any 𝐴 ∈ 𝔄 of rank at least 𝑘, 𝐿𝐴𝑅 is a non-zero matrix.
By Lemma 3.1, if every matrix (except the zero matrix) in a skewsymmetric matrix space is of high rank, then the skew-symmetric matrix space isometry problem reduces to the skew-symmetric matrix tuple isometry problem efficiently.
The hard case for the matrix space individualization/refine method is that there are some matrices 𝐴 in the space such that 𝐿𝐴𝑅 are zero matrices. Because of the linearity, such matrices form a linear subspace of the original matrix space. To tackle this hard case, we characterize the structure of the matrix space in which every matrix is of low rank. Such a matrix space is called a low rank matrix space.
As our main technical result for the low rank matrix space characterization, we show that, for a matrix space 𝔄 such that every matrix in the space is of rank at most 𝑟 , there are invertible matrices 𝑃 and 𝑄, called left and right formatting matrices, such that for each 𝐴 ∈ 𝔄, 𝑃𝐴𝑄 has non-zero entries only in the last 𝑂 (𝑟 2 ) rows or columns. Lemma 3.2. Let 𝔄 be a matrix subspace of 𝑀 (𝑚, 𝑛, F 𝑝 ) or a skewsymmetric matrix subspace of SS(𝑛, F 𝑝 ) such that for each 𝐴 ∈ 𝔄, rank (𝐴) ≤ 𝑟 for some positive integer 𝑟 . There is a matrix 𝑃 ∈ GL(𝑚, F 𝑝 ), a matrix 𝑄 ∈ GL(𝑛, F 𝑝 ), and an integer ℓ = 𝑂 (𝑟 2 ) such that for any 𝐴 ∈ 𝔄, 𝑃𝐴𝑄 [𝑖, 𝑗] = 0 for all the 1 ≤ 𝑖 ≤ 𝑛ℓ and 1 ≤ 𝑗 ≤ 𝑛ℓ. Furthermore, 𝑄 = 𝑃 𝑇 if 𝔄 is a skew-symmetric matrix space.
We remark that similar characterizations were studied in [1,23]. But to the author's knowledge, all the previous results require that the underlying field has at least 𝑟 + 1 elements.
Together with matrix space individualization-refinement, we can represent a matrix space in a more structured way. First, we construct a "semi-canonical" basis for the input matrix space. Suppose we apply left and right individualization matrices 𝐿 and 𝑅 to a matrix space 𝔄 of dimension 𝑑 and compute a linear basis (𝐴 1 , . . . , 𝐴 𝑑 ) of 𝔄 such that (𝐿𝐴 1 𝑅, 𝐿𝐴 2 𝑅, . . . , 𝐿𝐴 𝑑 𝑅) is lexically minimized among all the linear basis of 𝔄. Because the zero matrix is lexically the smallest among all the matrices, the first few matrices in the semicanonical basis correspond to a linear basis of ℭ, which is the linear span of all the matrices 𝐴 ∈ 𝔄 such that 𝐿𝐴𝑅 is a zero matrix.
We further apply formatting matrices 𝑃 and 𝑄 for ℭ to each matrix in the semi-canonical basis of 𝔄 (every matrix 𝐴 in the semicanonical basis becomes 𝑃𝐴𝑄). Then by our low rank matrix space characterization, the matrices that form a linear basis of ℭ have non-zero entries only in the last few rows or columns. See Figure 1 for an illustration.
The semi-canonical basis is not canonical because, for fixed individualization matrices, there can be different semi-canonical bases. But the semi-canonical bases can provide a partial correspondence between two isometric skew-symmetric matrix spaces. Suppose two skew-symmetric matrix spaces 𝔄 and 𝔅 are isometric and let 𝑆 be an isometry from 𝔄 to 𝔅. For individualization matrices 𝐿 and 𝑅 of 𝔄, let (𝐴 1 , . . . , 𝐴 𝑑 ) be a semi-canonical basis of 𝔄 with 𝐿 and 𝑅 as individualization matrices, and (𝐵 1 , . . . , 𝐵 𝑑 ) be a semi-canonical basis of 𝔅 with 𝐿𝑆 -1 and (𝑆 𝑇 ) -1 𝑅 as individualization matrices. Then for each 1 ≤ 𝑖 ≤ 𝑑, 𝑆𝐴 𝑖 𝑆 𝑇 = 𝐵 𝑖 + 𝐵 ′ 𝑖 for some 𝐵 ′ 𝑖 satisfying the condition that is a zero matrix. The partial correspondence also holds for two equivalent matrix spaces. Two matrix spaces 𝔄 and 𝔅, in which matrices are not necessarily square matrices, are equivalent if there are invertible matrices 𝑋 and 𝑌 such that 𝑋 𝔄𝑌 = 𝔅, i.e., 𝔅 equals the space spanned by 𝑋𝐴𝑌 for all the matrices 𝐴 ∈ 𝔄.
Next, we combine the matrix space individualization-refinement and the low rank matrix space characterization to analyze skewsymmetric matrix spaces. For convenience, let us define a threetensor representation for skew-symmetric matrix spaces following [36]. For a skew-symmetric matrix space 𝔄 of dimension 𝑚 such that every matrix in the space is an 𝑛 × 𝑛 matrix, a threetensor G ∈ F 𝑚×𝑛×𝑛 𝑝 is a skew-symmetric matrix space tensor of 𝔄 if G[𝑖, 𝑗, 𝑘] = 𝐴 𝑖 [ 𝑗, 𝑘] for a linear basis (𝐴 1 , . . . , 𝐴 𝑚 ) of 𝔄, where 𝐴 𝑖 [ 𝑗, 𝑘] is the ( 𝑗, 𝑘)-th entry of 𝐴 𝑖 , and G[𝑖, 𝑗, 𝑘] is the (𝑖, 𝑗, 𝑘)-th entry of G.
Given a skew-symmetric matrix space tensor G, we use 𝔛 G,𝑖 to denote the 𝑛 × 𝑛 skew-symmetric matrix such that
and use ℨ G,𝑘 to denote the 𝑚 × 𝑛 matrix such that
Since 𝐴 𝑖 are skew-symmetric matrices for all the 1 ≤ 𝑖 ≤ 𝑚, 𝔛 G,𝑖 are skew symmetric matrices for all the 1 ≤ 𝑖 ≤ 𝑚, and 𝔜 G,𝑗 equals to -ℨ G,𝑗 for all the 1 ≤ 𝑗 ≤ 𝑛.
We also use 𝔛 G to denote the matrix space ⟨𝔛 G,1 , . . . 𝔛 G,𝑚 ⟩, use 𝔜 G to denote the matrix space ⟨𝔜 G,1 , . . . 𝔜 G,𝑛 ⟩, and use ℨ G to denote the matrix space ⟨ℨ G,1 , . . . ℨ G,𝑛 ⟩, where ⟨•⟩ is the linear span. We remark that 𝔛 G is a skew-symmetric matrix space, but 𝔜 G and ℨ G are not.
One can verify that two skew-symmetric matrix spaces are isometric if and only if their tensors (denoted as G and H) are isometric, i.e., there is an 𝑛 × 𝑛 invertible matrix 𝑁 and an 𝑚 × 𝑚 invertible matrix 𝑀 such that the transform of G by 𝑁 and 𝑀, denoted as Trans 𝑁 ,𝑀 (G), equals H, where
The purpose of the tensor representation of a skew-symmetric matrix space is to incorporate the matrix space individualizationrefinement and the low rank matrix space characterization techniques so the tensor is transformed into a more structured form, called the "semi-canonical form" of the tensor. For a skew-symmetric matrix space tensor G, the semi-canonical form of G, denoted as SC(G), is obtained by applying the two techniques to the three matrix spaces 𝔛 G , 𝔜 G , and ℨ G so matrices in each of the three matrix spaces have the structure shown in Figure 1.
To achieve this, we need to carefully choose the individualization and formatting matrices in a coordinated fashion. In particular, if the individualization and formatting matrices are chosen such that, for the left formatting matrix 𝑃 used for 𝔛 G , 𝑃 𝑇 can also be used as the right formatting matrix for 𝔜 G and ℨ G , then the tensor semi-canonical form has the structure shown in Figure 2(a). The tensor values in the transparent region are all zero. The union of the transparent region and the red cube is called the kernel of the tensor semi-canonical form. The blue region is called the surface of the tensor semi-canonical form.
For fixed individualization and formatting matrices, the tensor semi-canonical form is also fixed. However, for an efficient tensor isometry testing algorithm, it is unacceptable to enumerate all possible formatting matrices, though it is affordable to enumerate all possible individualization matrices. To address this issue, we show that if the individualization matrices are fixed, and the formatting matrices are partially fixed (i.e., only a few key rows are fixed, and all the other rows satisfy certain conditions), then the kernel is fixed. This is also the reason for the term "semi-canonical form": the semi-canonical form is not unique for fixed individualization matrices and partially fixed formatting matrices, but the kernel is unique.
In other words, if two tensors are isometric, and one constructs the semi-canonical forms of the two tensors using individualization matrices and partially fixed formatting matrices that are the same up to some isometry, then the kernels of the two semi-canonical forms are identical. Therefore, to determine whether the two tensors are isometric, one only needs to check further if there are formatting matrices that make the surface identical for the two tensors while keeping the kernel unchanged.
In addition, based on the the matrix space individualizationrefinement and the low rank matrix space characterization, there are always semi-canonical forms such that the numbers of matrices in the surfaces of 𝔛 G , 𝔜 G , and ℨ G (Figure 2(b)) are small. Hence, in the partially fixed formatting matrices, we also fix the rows related to the surfaces of 𝔛 G , 𝔜 G , and ℨ G . Then matrices in the surfaces from the three matrix spaces are fixed up to some formatting matrices satisfying the partially fixed constraint.
Hence, the isometry testing of skew-symmetric matrix space tensors reduces to the isometry testing of their semi-canonical forms by enumerating individualization matrices and partially fixed formatting matrices for both tensors. Due to the fixed kernel for all the semi-canonical forms, the isometry testing of semi-canonical forms further reduces to deciding whether the surfaces are identical between semi-canonical forms up to some formatting matrices satisfying the partially fixed constraint.
Tuple Isometry Testing We use the submatrices on 𝑅 1 (as Figure 3) for all the matrices in F SC(G) to encode the skew-symmetric matrices in the surface of 𝔛 G . We also use the submatrices on 𝑅 2 for all the matrices in F SC(G) to encode the matrices in the surface of 𝔜 G (excluding the intersection with the surface of 𝔛 G ). Consequently, the submatrices on 𝑅 3 for all the matrices in F SC(G) , which is the negative transpose of submatrices on 𝑅 2 by the skew-symmetric condition, encode the matrices in the surface of ℨ G (excluding the intersection with the surface of 𝔛 G ). We use the other submatrices to ensure constraints given by the partially fixed formatting matrices.
By carefully designing matrix tuples constructed from tensor semi-canonical forms, we show that the semi-canonical forms of two skew-symmetric matrix space tensors are isometric if and only if there is an isometry 𝑆 between the skew-symmetric matrix tuples such that 𝑆 is a block diagonal matrix 𝑆 = 𝑄 0 0 𝑊 for some (3 + 𝑛) × (3 + 𝑛) matrix 𝑄 and 𝑚 ′ × 𝑚 ′ matrix 𝑊 .
Naturally, we want to determine the isometry of the two tensors by running the skew-symmetric matrix tuple isometry algorithm (Theorem 2.4) on the matrix tuples constructed from the semi-canonical forms. However, the requirement of 𝑆 being block diagonal makes things more complex.
Suppose we run the algorithm for skew-symmetric matrix tuple isometry on the matrix tuples constructed. If the algorithm returns no, then the two semi-canonical forms are not isometric. If the algorithm returns yes and an isometry that is block diagonal, then the two semi-canonical forms are isometric. The difficult case is when the algorithm returns yes and an isometry that is not block diagonal. For this case, we can neither certify that the two semicanonical forms are isometric, nor show that the two semi-canonical forms are not isometric.
Let us consider an easier scenario: Suppose for each non-zero row vector 𝑣 ∈ F 𝑛 𝑝 , there is a matrix 𝑋 in the surface of 𝔛 G such that 𝑣𝑋 is a non-zero vector. With this condition, together with our construction of matrix tuples, we can show that the isometry returned is of the form 𝑋 𝑌 0 𝑍 .
After carefully analyzing the matrix tuples constructed, we show that 𝑋 0 0 𝑍 is also an isometry, and thus the two semi-canonical forms are isometric.
The general case is more complex because the left bottom submatrix of the isometry returned can be non-zero. However, we show that either we can certify that there exists another block diagonal isometry for the skew-symmetric matrix tuples, or we can reduce the problem to a matrix tuple equivalence problem (Definition 2.1). By Theorem 2.3, the matrix tuple equivalence problem can be solved efficiently.