Linear Codes and Self-Polarity

Abstract

This work studies projective self-dual (PSD) and self-polar linear codes over finite fields with q elements, where q is a power of a prime. The possible parameters for which PSD codes may exist are presented, and many examples are provided. Algorithms for checking whether a q-ary linear code is self-polar are described. Many PSD and self-polar codes over fields with two, three, four, and five elements with two and three nonzero weights are constructed.

1. Introduction

In the words of Michael Atiyah, duality in mathematics is not a theorem but a “principle” [1]. It appears in many subjects in mathematics and has been adapted and modified in different situations. We use a duality that comes from the finite geometry and apply it to the linear codes.

Whenever an object is equivalent to its own dual, then it is said to be self-dual, but, if it is equal to its dual, it is self-polar. Self-duality and self-polarity can be viewed as different degrees of symmetry. In this work, we use the duality between points and hyperplanes in the projective geometry $PG(k-1,q)$. Usually, the transform is defined constructively in terms of the projective geometry [2,3,4] by matrices [2,5] or by a characteristic vector [6]. Any point $a=(a_1,a_2,\dots ,a_k)$ defines a hyperplane $H_a$, which consists of all the points $x=(x_1,x_2,\dots ,x_k)$ such that $(a,x)=\sum a_i{x}_i=0$. This duality (known as projective duality or Delsarte duality) is useful in the study of two-weight codes (see [2,7,8]). A generalization of the projective duality was provided by Dodunekov and Simonis in [3].

Projective self-dual (PSD) and self-polar codes are related to other combinatorial structures, such as two-weight codes [2], divisible codes, self-dual bent Boolean functions [9], strongly regular graphs [7], association schemes, etc. [10]. This motivates us to study these codes. Furthermore, we associate them with square matrices and, especially in the case of self-polar codes, symmetric matrices.

The main problems related to the equivalence of combinatorial objects refer to answering the question of whether two objects are equivalent, to classifying structures with given properties, to finding automorphism groups or the canonical form, etc. Checking whether a given incidence structure is self-polar is related to these problems. We associate the self-polarity with solving the following problem: can a square matrix be reduced to a symmetric form with only permutations of rows and columns? If so, what is an efficient algorithm for this?

This work studies projective self-dual and self-polar linear codes over a finite field. The family of self-polar codes forms a subclass of the class of PSD codes over ${\mathbb{F}}_q$ for a given prime power q. We study two main problems. The first one is to determine the parameters regarding which the existence of a q-ary PSD code is possible. The second is related to the question of how to check whether a given projective self-dual code is self-polar. The first problem is solved with theoretical arguments, and, for some of the obtained families of codes, it is directly established that they consist of self-polar codes. To answer the question from the second problem, we use an algorithmic approach. The first step in this direction is to check whether a square matrix defined in a special way, related to the considered code, can be reduced to a symmetric form by permutations of rows and columns and, if so, to find the corresponding symmetric matrix. The second step is to find a characteristic vector of the code that proves its self-polarity. At the end of the paper, we also present classification results for PSD and self-polar codes with two and three nonzero weights.

This paper is organized as follows. We provide the main definitions in Section 2. Section 3 is devoted to the projective self-dual codes. In that section, we present the possible parameters for which PSD codes may exist and provide many examples. In Section 4, we associate PSD codes with square binary matrices and present an algorithm to check whether such a matrix is a permutation equivalent to a symmetric matrix, thus checking whether the corresponding code is self-polar. Some computational results and applications are provided in Section 5.

2. Preliminaries

Let q be a prime power and ${\mathbb{F}}_q$ be a finite field with q elements. A linear q-ary code of length n and dimension k is a subspace of the vector space ${\mathbb{F}}_q^n$. If $q=2$, the code is called binary, if $q=3$, the code is ternary, and, if $q=4$, it is quaternary. A $k\times n$ matrix G with elements from ${\mathbb{F}}_q$, whose rows form a basis of C is called a generator matrix of the code. If G does not have zero columns, the code has full length, and, if the columns of G are pairwise nonproportional, the code is called projective. In this work, we consider only linear codes of full length as later in the paper under linear code we will mean a code of full length. The columns of the matrix G can be considered as points in the projective geometry $PG(k-1,q)$. If we put all points of $PG(k-1,q)$ in a matrix $S_{k,q}$ as columns, then $S_{k,q}$ generates the simplex code ${\mathfrak{S}}_{k,q}$ of length $\theta (k,q)={\displaystyle \frac{q^k-1}{q-1}}$.

The (Hamming) weight of a vector $v\in {\mathbb{F}}_q^n$ is the number of its nonzero coordinates. If the nonzero codewords of the linear code C have exactly t different weights, C is a t-weight code. The simplex and replicated simplex codes are the only 1-weight linear codes [3]. All nonzero codewords in ${\mathfrak{S}}_{k,q}$ have weight $q^{k-1}$. The weight enumerator of a linear code of length n is the polynomial $W\left(y\right)={\sum }_{i=0}^n{A}_i{y}^i$, where $A_i$ is the number of codewords of weight i. The weight enumerator of the simplex code ${\mathfrak{S}}_{k,q}$ is $W\left(y\right)=1+(q^k-1)y^{q^{k-1}}$. The minimum nonzero weight of a codeword in C is called the minimum weight of the code. If C has length n, dimension k, and minimum weight d, it is said to be an ${[n,k,d]}_q$ code.

Two linear ${[n,k,d]}_q$ codes $C_1$ and $C_2$ are equivalent if there is a monomial $n\times n$ matrix M and an automorphism of the field $\gamma$ such that $vM\gamma \in C_2$ for each codeword $v\in C_1$. The pair $(M,\gamma )$ is called an automorphism of the code C if $vM\gamma \in C$ for all $v\in C$. All automorphisms of C form its automorphism group denoted by $\mathrm{Aut}\left(C\right)$. The permutation automorphism group $\mathrm{PAut}\left(C\right)$ consists of all permutations of the coordinates that preserve the code. Obviously, $\mathrm{PAut}\left(C\right)$ is a subgroup of the symmetric group $S_n$. We also require a definition for an automorphism of a square matrix. We say that the permutation of the rows of the square matrix A is an automorphism of A if it maps its columns into columns of the same matrix.

Using the matrix $S_{k,q}$ and a generator matrix G of the linear code C, we define a characteristic vector of C.

Definition 1. 

The characteristic vector of ${[n,k]}_q$ code C with respect to matrix G is

$$\chi (C,G)=({\chi }_1,{\chi }_2,\dots ,{\chi }_{\theta (k,q)})\in {\mathbb{Z}}^{\theta (k,q)}$$

(1)

where ${\chi }_i$ is the number of columns of G that are equal or proportional (with nonzero coefficients) to the i-th column of matrix $S_{k,q}$.

A code C can have different characteristic vectors depending on the matrix G and the considered generator matrix $S_{k,q}$ of the simplex code ${\mathfrak{S}}_{k,q}$. We fix the matrix $S_{k,q}$ to consist of all vectors in ${\mathbb{F}}_q^k$ whose first nonzero coordinate is 1, ordered lexicographically. If we permute the columns of the matrix G, we obtain a permutation equivalent code to C having the same characteristic vector. Moreover, from a characteristic vector, one can restore the columns of the generator matrix G, possibly in a different order and/or multiplied by nonzero elements of the field. Therefore, without loss of generality, we can suppose that the columns in G are ordered lexicographically and belong to the set of columns of the matrix $S_{k,q}$. When the code C and the matrix G are clear from the context, we will write briefly $\chi$. Note that the sum of the coordinates of a characteristic vector of C is equal to the length of the code.

Further, we consider the matrix $M_k=S_{k,q}^T·S_{k,q}$, where the multiplication is over ${\mathbb{F}}_q$. The rows of $M_k$ are nonproportional codewords in the simplex code ${\mathfrak{S}}_{k,q}$. Since $M_k^T={(S_{k,q}^T·S_{k,q})}^T=S_{k,q}^T·S_{k,q}=M_k$, $M_k$ is a symmetric q-ary $\theta (k,q)\times \theta (k,q)$ matrix. By $\mathcal{N}\left(M_k\right)$, we denote the matrix obtained from $M_k$ by replacing all nonzero elements by 1. Calculating the square and the determinant of this matrix, we obtain $\mathcal{N}{\left(M_k\right)}^2=q^{k-2}(q{J}_{\theta (k,q)}-I_{\theta (k,q)})$, where $I_{\theta (k,q)}$ and $J_{\theta (k,q)}$ are the identity and the all-ones matrix of order $\theta (k,q)$, respectively, and $det\left(\mathcal{N}{\left(M_k\right)}^2\right)=q^{k+\theta (k,q)(k-2)}$. Hence $\mathcal{N}\left(M_k\right)$ is an invertible matrix.

We use the matrix $\mathcal{N}\left(M_k\right)$ and a characteristic vector of the linear code C to define its projective dual code.

Definition 2. 

Let α and β be rational numbers such that $\alpha w_i+\beta$ is a non-negative integer for any nonzero weight w of a codeword in C. The projective dual code $D_{\alpha ,\beta ,k}\left(C\right)$ of C is the linear code with characteristic vector ${\chi }_{\alpha ,\beta }=\alpha \chi \mathcal{N}\left(M_k\right)+\beta \mathbf{1}$, where $\mathbf{1}$ is the all-ones vector of the corresponding length.

As described in [6], the i-th coordinate of ${\chi }_{\alpha ,\beta }$ is equal to $\alpha \mathrm{wt}\left(v_i\right)+\beta$, where $v_i\in C$ is the i-th row of the matrix $S_{k,q}^{T}G$.

If two linear codes are equivalent, then their projective dual codes for the given $\alpha$, $\beta$ and k are also equivalent [5]. The length of $D_{\alpha ,\beta ,k}\left(C\right)$ is $n_D=\alpha n{q}^{k-1}+\beta \theta (k,q)$ [5]. If C is a projective linear code, then its projective dual code has at most two nonzero weights, namely $w_1=\alpha q^{k-2}(q-1)n+\beta q^{k-1}$ and $w_2=\alpha q^{k-2}+w_1$. In the general case, the weights in $D_{\alpha ,\beta ,k}\left(C\right)$ are $q^{k-2}(\alpha {\chi }_i+\alpha (q-1)n+\beta q$, where ${\chi }_i$ represents the coordinates of the characteristic vector, $i=1,\dots ,\theta (k,q)$.

3. Projective Self-Dual (PSD) and Self-Polar Codes

The projective self-dual codes were studied first by Dodunekov and Simonis in [3], but they called the codes $\sigma$ self-dual. We used the term projective self-duality in our work [6], but here we propose to call these codes PSD codes in order to distinguish them from the well-known self-dual codes with respect to orthogonality.

Definition 3. 

The linear code C is projective self-dual (PSD) if it is equivalent to its projective dual code $D_{\alpha ,\beta }$ for some α and β. The code is self-polar if it has a characteristic vector χ such that ${\chi }_{\alpha ,\beta }=\chi$ for some α and β.

If C is an ${[n,k]}_q$ code with a characteristic vector $\chi$, and $tC=\left(C\right|C|\dots |C)$ is the code C, repeated t times, then the characteristic vector of $tC$ is $t\chi$ and therefore its projective dual for the same $\alpha$ and ${\beta }^{\prime }=t\beta$ is

$${\chi }_{\alpha ,t\beta }^{\prime }=\alpha t\chi \mathcal{N}\left(M_k\right)+t\beta \mathbf{1}=t{\chi }_{\alpha ,\beta }.$$

It follows that, if C is PSD (resp. self-polar), the same is $tC$. Consider now the code $C_{+1}=\left(C\right|S_{k,q})$. This code has a characteristic vector ${\chi }_{+1}=\chi +\mathbf{1}$. Then, its projective dual code $D_{\alpha ,{\beta }^{\prime }}$ has a characteristic vector

$$\begin{array}{cc}\hfill {\chi }_{+1,\alpha ,{\beta }^{\prime }}& \hfill =\alpha (\chi +\mathbf{1})\mathcal{N}\left(M_k\right)+{\beta }^{\prime }\mathbf{1}={\chi }_{\alpha ,\beta }+\alpha \mathbf{1}\mathcal{N}\left(M_k\right)+({\beta }^{\prime }-\beta )\mathbf{1}\hfill \\ \hfill & \hfill ={\chi }_{\alpha ,\beta }+\alpha q^{k-1}\mathbf{1}+({\beta }^{\prime }-\beta )\mathbf{1}={\chi }_{\alpha ,\beta }+(\alpha q^{k-1}+{\beta }^{\prime }-\beta )\mathbf{1}.\hfill \end{array}$$

If we take ${\beta }^{\prime }=1+\beta -\alpha q^{k-1}$, then ${\chi }_{+1}={\chi }_{\alpha ,\beta }+\mathbf{1}$, so, if C is PSD (resp. self-polar), the same is $C_{+1}$. Therefore, we will concentrate on linear codes for which the characteristic vector has zero coordinates and the greatest common divisor of the coordinates is 1.

Consider one more code, related to C, namely its projective complementary code $\overline{C}$. If C is a projective code, $\overline{C}$ is the code with characteristic vector $\overline{\chi }=\mathbf{1}-\chi$. If G is the corresponding generator matrix of C, the generator matrix of $\overline{C}$ consists of all columns of $S_{k,q}$ that do not belong to G. Then,

$$\begin{array}{cc}\hfill {\chi }_{\alpha ,{\beta }^{\prime }}& =\alpha (\mathbf{1}-\chi )\mathcal{N}\left(M_k\right)+{\beta }^{\prime }\mathbf{1}=\alpha \mathbf{1}\mathcal{N}\left(M_k\right)-\alpha \chi \mathcal{N}\left(M_k\right)+{\beta }^{\prime }\mathbf{1}\hfill \\ \hfill & =\alpha q^{k-1}\mathbf{1}-\alpha \chi \mathcal{N}\left(M_k\right)-\beta \mathbf{1}+(\beta +{\beta }^{\prime })\mathbf{1}\hfill \\ \hfill & =(\alpha q^{k-1}+\beta +{\beta }^{\prime })\mathbf{1}-{\chi }_{\alpha ,\beta }.\hfill \end{array}$$

We can take ${\beta }^{\prime }=1-\beta -\alpha q^{k-1}$, and then, if C is PSD (resp. self-polar), the same is $\overline{C}$. Therefore, for the projective codes of length n and dimension k, it is enough to check for projective self-duality only the codes with $n\le \theta k,q/2={\displaystyle \frac{q^k-1}{2(q-1)}}$.

In the case of non-projective codes, for $\overline{C}$, we take the code with a characteristic vector $\overline{\chi }=t\mathbf{1}-\chi$, where t is the largest integer among the coordinates of $\chi$.

The following theorem provides the possible parameters $\alpha$ and $\beta$ for which the projective dual $D_{\alpha ,\beta }\left(C\right)$ could be equivalent to the code C ([3] Proposition 6).

Theorem 1. 

Let C be q-ary $[n,k,d]$ projective self-dual code. If C is not a replicated simplex code, then

$$\alpha =\pm q^{1-{\displaystyle \frac{k}{2}}},\beta =-{\displaystyle \frac{q-1}{1+q^{k-1}\alpha }}n.$$

(2)

After converting formula (2), we obtain

$$\alpha ={\displaystyle \frac{ϵ}{q^{\frac{k}{2}-1}}},\beta =-{\displaystyle \frac{q-1}{1+q^{k-1}\frac{ϵ}{q^{\frac{k}{2}-1}}}}n=-{\displaystyle \frac{q-1}{1+ϵq^{\frac{k}{2}}}}n,$$

(3)

where $ϵ=\pm 1$.

It follows that

$$\left(i\right)\alpha ={\displaystyle \frac{1}{q^{\frac{k}{2}-1}}},\beta =-{\displaystyle \frac{q-1}{1+q^{\frac{k}{2}}}}n,\mathrm{or}\left(ii\right)\alpha =-{\displaystyle \frac{1}{q^{\frac{k}{2}-1}}},\beta ={\displaystyle \frac{q-1}{q^{\frac{k}{2}}-1}}n.$$

(4)

Since $\alpha$ is a rational number, then $q^{{\displaystyle \frac{k}{2}}-1}$ should be integer, so, if k is odd, then q is an even power of a prime. Moreover,

$${\displaystyle \frac{ϵw}{q^{\frac{k}{2}-1}}}-{\displaystyle \frac{q-1}{1+ϵq^{\frac{k}{2}}}}n\in \mathbb{Z}$$

for any nonzero weight of a codeword in C. Since $gcd(q^{{\displaystyle \frac{k}{2}}-1},1+ϵq^{{\displaystyle \frac{k}{2}}})=1$, the above number is an integer only if $q^{{\displaystyle \frac{k}{2}}-1}\mid w$ and $(1+ϵq^{{\displaystyle \frac{k}{2}}})\mid (q-1)n$. Hence, we can write the nonzero weights of the code in the form $w=q^{k/2-1}a$, where a is a positive integer.

If the projective linear code C is projective self-dual, it must be a two-weight code with two nonzero weights $w_1$ and $w_2=w_1+\alpha q^{k-2}$. We can calculate the weight distribution of C using the Pless power moments [11]

$$1+A_1+A_2=q^k,w_1{A}_1+w_2{A}_2=q^{k-1}(q-1)n.$$

Solving this system with unknowns $A_1$ and $A_2$, we obtain that $A_2=(q-1)n$ if $ϵ=1$ and $A_1=(q-1)n$ if $ϵ=-1$. In both cases, the maximal number of nonproportional codewords with one of the weights (say w) is equal to the length of the code, and, if we put these nonproportional codewords as rows in a matrix, this matrix will be an $n\times n$ square matrix. Denote this matrix by $M\left(G\right)$. As we mentioned after Definition 2, if $v_i$ is the ith row in $S_{k,q}^{T}G$, then ${\chi }_{\alpha ,\beta ,i}=\alpha \mathrm{wt}\left(v_i\right)+\beta$; hence, the coordinates of the characteristic vector ${\chi }_{\alpha ,\beta }$, which are equal to 1, correspond to codewords of C with weight w, and, furthermore, all these coordinates correspond to a maximal set of nonproportional codewords with this weight. As ${\left({\chi }_{\alpha ,\beta }\right)}_i=1$ shows, the i-th row of the matrix $S_{k,q}$ appears in the considered generator matrix $G_{\alpha ,\beta }$ of the projective dual code, $M\left(G\right)=G_{\alpha ,\beta }^{T}G$, and it can also be obtained by intersecting the columns and rows of $M_k$ corresponding to the coordinates equal to 1 in the characteristic vectors $\chi$ and ${\chi }_{\alpha ,\beta }$, respectively.

If the code is self-polar, then $G_{\alpha ,\beta }=G$, and therefore the matrix $M\left(G\right)=G^{T}G$ is symmetric. This proves the following theorem.

Theorem 2. 

Let C be a projective linear PSD $[n,k,\{w_1,w_2\}]$ code with a characteristic vector χ with respect to the generator matrix G. If $G_{\alpha ,\beta }$ is the generator matrix corresponding to the characteristic vector ${\chi }_{\alpha ,\beta }$, then $M\left(G\right)=G_{\alpha ,\beta }^{T}G$ is a square $n\times n$ matrix whose rows have the same weight w, where $w=w_1$ or $w_2$. Moreover, these rows form a maximal set of nonproportional codewords with this weight in the code C. If C is a self-polar code, the matrix $M\left(G\right)$ is symmetric.

Consider now a non-projective PSD code of length n and dimension k with a characteristic vector $\chi$ with respect to its generator matrix G. Suppose that $\chi$ has zero coordinates. If $G_{\alpha ,\beta }$ is the generator matrix that corresponds to the characteristic vector ${\chi }_{\alpha ,\beta }$, we consider the matrix $M\left(G\right)=G_{\alpha ,\beta }^{T}G$. As the code is PSD, this is a square matrix of order n. The following theorem generalizes Theorem 2. The PSD codes are divisible by $\Delta =q^{k/2-1}$.

Theorem 3. 

Let C be a PSD ${[n,k,d]}_q$ code with a characteristic vector χ with respect to its generator matrix G, and ${\chi }_{\alpha ,\beta }$ defines a code that is equivalent to C. Suppose that χ contains at least one zero coordinate and $W\left(y\right)=1+A_1{y}^{w_1}+\cdots +A_s{y}^{w_s}$ is the weight enumeration of C, where $A_i\ge 0$ for all $i=1,\dots ,s$, $s>1$, $w_1=d$, $w_2=d+\Delta ,\dots ,w_s=d+(s-1)\Delta \le n$. Then, $A_2+2A_3+\cdots +(s-1)A_s=(q-1)n$ or $(s-1)A_1+(s-2)A_2+\cdots +A_{s-1}=(q-1)n$. Moreover, if ${\chi }_{\alpha ,\beta }=\chi$, then $M\left(G\right)$ is a symmetric matrix.

Proof. 

As we mentioned above, if $v_i$ is the i-th row in $S_{k,q}^{T}G$, then ${\left({\chi }_{\alpha ,\beta }\right)}_i=\alpha \mathrm{wt}\left(v_i\right)+\beta$. As ${\chi }_{\alpha ,\beta }$ has zero coordinates, then $\alpha \mathrm{wt}\left(v_i\right)+\beta =0$ if $\mathrm{wt}\left(v_i\right)=d$ or $w_s$. Take $\alpha \mathrm{wt}\left(v_i\right)+\beta =0$ for $\mathrm{wt}\left(v_i\right)=d$, which means that $\alpha w_1+\beta =0$. It follows that $\alpha w_j+\beta =j-1$, $j=1,\dots ,s$.

As ${\left({\chi }_{\alpha ,\beta }\right)}_i=j$ shows that the i-th row of the matrix $S_{k,q}$ appears in the considered generator matrix $G_{\alpha ,\beta }$ of the projective dual code repeated j times, the corresponding vector from $S_{k,q}^{T}G$ appears as a row in $M\left(G\right)=G_{\alpha ,\beta }^{T}G$ also repeated j times. Moreover, ${\sum }_{i=1}^{\theta (k,q)}{\left({\chi }_{\alpha ,\beta }\right)}_i=n$ and therefore $A_2+2A_3+\cdots +(s-1)A_s=(q-1)n$, bearing in mind that in addition to the rows that belong to $S_{k,q}^{T}G$ we must also count all their proportional vectors. Here, we also use the fact that the code C is equivalent to its projective dual, so they share the same weight enumerator. Similarly, if $\alpha w_s+\beta =0$, then $(s-1)A_1+(s-2)A_2+\cdots +A_{s-1}=(q-1)n$.

Obviously, if ${\chi }_{\alpha ,\beta }=\chi$, then the two generator matrices coincide (recall that we take the columns in G in lexicographic order) and therefore $M\left(G\right)=G^{T}G$ is symmetric. □

Next, we provide some restrictions on the parameters of the PSD codes. We separately consider the two cases presented in (4) for even and odd values of the dimension k.

First, let $k=2k_1$ be even.

$\left(i_e\right)$

In this case, $\alpha ={\displaystyle \frac{1}{q^{k_1-1}}}$ and $\beta =-{\displaystyle \frac{q-1}{q^{k_1}+1}}n$. Since $\beta$ is an integer, $q^{k_1}+1$ must divide $(q-1)n$. If q is even, $gcd(q-1,q^{k_1}+1)=1$ and therefore $q^{k_1}+1$ will divide the length n. If q is odd, $gcd(q-1,q^{k_1}+1)=2$ and it is enough that n is a multiple of $(q^{k_1}+1)/2$. So, we have two subcases:

$\left(i_1\right)$

Let q be even. Now, $\beta =-(q-1)t$ and $n=(q^{k_1}+1)t$, where t is a positive integer. Since $\alpha w+\beta =a-(q-1)t\ge 0$, we have $a\ge (q-1)t$. Then, the parameters of the code are $[(q^{k_1}+1)t,2k_1,\ge q^{k_1-1}(q-1)t]$.

Applying the Griesmer bound to these parameters, we obtain

$$(q^{k_1}+1)t\ge \sum _{i=0}^{2k_1-1}\lceil {\displaystyle \frac{q^{k_1-1}(q-1)t}{q^i}}\rceil =\sum _{i=0}^{k_1-1}{q}^{k_1-1-i}(q-1)t+\sum _{i=k_1}^{2k_1-1}\lceil {\displaystyle \frac{(q-1)t}{q^{i-k_1+1}}}\rceil$$

$$\hspace{1em}\hspace{1em}\hspace{1em}\Rightarrow (q^{k_1}+1)t\ge (q^{k_1}-1)t+\sum _{i=1}^{k_1}\lceil {\displaystyle \frac{(q-1)t}{q^i}}\rceil$$

$$\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\Rightarrow 2t\ge \sum _{i=1}^{k_1}\lceil {\displaystyle \frac{(q-1)t}{q^i}}\rceil \ge k_1.$$

According this inequality, $t\ge \lceil {\displaystyle \frac{k_1}{2}}\rceil$. We will provide some examples.

Example 1. 

Let $q=2$. We are looking for $[(2^{k_1}+1)t,2k_1,\ge 2^{k_1-1}t\}]$ binary PSD codes for several values of $k_1$.

*

$k_1=2$) In this case, C is a binary even $[5t,4,\ge 2t]$ code. The code can be a projective two-weight PSD code only for $t<3$. The parity-check $[5,4,2]$ binary code is a projective self-dual two-weight code. Its projective complement is a two-weight $[10,4,4]$ code with weight enumerator $1+5y^4+10y^6$. There is at least one self-polar $[15,4,6]$ code with weight enumerator $W\left(y\right)=1+5y^6+5y^8+5y^{10}$, as an example, which is the code with characteristic vector $(0,1,0,1,2,0,1,0,2,2,2,0,2,1,1)$. This code is interesting also as a code with balanced weight distribution; i.e., it has the same number of codewords for each nonzero weight. This code is not projective and therefore is different from the codes with balanced weight distributions presented in [12].

*

$k_1=3$) In this case, C is a binary doubly even $[9t,6,\ge 4t]$ code, $t\ge 2$. There are one $[18,6,8]$ and five $[27,6,12]$ projective self-dual two-weight codes. Their weight enumerators are $1+45y^8+18y^{12}$ and $1+36y^8+27y^{12}$, respectively. The complement codes have parameters $[36,6,16]$ and $[45,6,20]$.

*

$k_1=4$) In this case, C is a binary $[17t,8,\ge 8t]$ code divisible by 8, $t\ge 2$. There is one two-weight $[51,8,24]$ code that is PSD and 41 two-weight $[68,8,\{32,40\left\}\right]$ codes, 29 of which are PSD [13].

*

$k_1=5$) In this case, C is a binary $[33t,10,\ge 16t]$ code divisible by 16, $t\ge 3$. There is a two-weight $[198,10,96]$ code.

Four families with binary two-weight codes have been studied in [14]. The codes in the family ${\Phi }_{k^{-}}^{\prime }$ have parameters $[(2^{k_1}+1)(2^{k_1-1}-1),2k_1,\{2^{2k_1-2}-2^{k_1-1},2^{2k_1-2}\}]$. The presented ${[5,4,2]}_2$ and ${[27,6,12]}_2$ two-weight codes belong to this family. The codes in the family ${\Phi }_{k^{+}}$ are projective complementary to the codes from ${\Phi }_{k^{-}}^{\prime }$ and have parameters $[(2^{k_1}+1)t,2k_1,2^{k_1-1}t\}]$ for $t=2^{k_1-1}$.

Example 2. 

Let $q=4$. The two-weight codes in this case have parameters $[(4^{k_1}+1)t,2k_1,\{4^{k_1-1}t,4^{k_1}t\}]$.

*

$k_1=2$) Now, C is a quaternary $[17t,4,\ge 4t]$ code. According to [13], there are 1 ${[17,4,12]}_4$ and 38 ${[34,4,24]}_4$ projective two-weight PSD codes.

*

$k_1=3$) In this case, C is a binary doubly even $[65t,6,\ge 16t]$ code, $t\ge 2$.

$\left(i_2\right)$

Let q be odd. Now, $\beta =-{\displaystyle \frac{q-1}{2}}t$ and $n={\displaystyle \frac{q^{k_1}+1}{2}}t$, where t is a positive integer. Since $\alpha w+\beta =a-{\displaystyle \frac{q-1}{2}}t\ge 0$, we have $a\ge {\displaystyle \frac{q-1}{2}}t$. The parameters of the codes in this case are $[{\displaystyle \frac{q^{k_1}+1}{2}}t,2k_1,\ge q^{k_1-1}{\displaystyle \frac{q-1}{2}}t]$. According to the Griesmer bound,

$${\displaystyle \frac{q^{k_1}+1}{2}}t\ge \sum _{i=0}^{2k_1-1}\lceil {\displaystyle \frac{q^{k_1-1}(q-1)t}{2q^i}}\rceil =\sum _{i=0}^{k_1-1}{q}^{k_1-1-i}{\displaystyle \frac{q-1}{2}}t+\sum _{i=k_1}^{2k_1-1}\lceil {\displaystyle \frac{(q-1)t}{2q^{i-k_1+1}}}\rceil$$

$$\Rightarrow {\displaystyle \frac{q^{k_1}+1}{2}}t\ge {\displaystyle \frac{q^{k_1}-1}{2}}t+\sum _{i=1}^{k_1}\lceil {\displaystyle \frac{(q-1)t}{2q^i}}\rceil$$

$$\Rightarrow t\ge \sum _{i=1}^{k_1}\lceil {\displaystyle \frac{(q-1)t}{2q^i}}\rceil \ge k_1.$$

Example 3. 

Let $q=3$. The ternary two-weight codes in this family have parameters $[{\displaystyle \frac{3^{k_1}+1}{2}}t,2k_1,\{3^{k_1-1}t,3^{k_1}t\}]$. If $k_1=2$, C is a ternary self-orthogonal $[5t,4,\ge 3t]$ code, $t\ge 2$. There are one ${[10,4,6]}_3$, two ${[15,4,9]}_3$, and four ${[20,4,12]}_3$ projective two-weight codes, and all of them are PSD [13]. If $k_1=3$, C is a ternary $[28t,6,\ge 18t]$ code, $t\ge 2$. The only projective two-weight ${[56,6,36]}_3$ code is PSD.

($i{i}_e$)

In this case, $n={\displaystyle \frac{q^{\frac{k}{2}}-1}{q-1}}\beta ={\displaystyle \frac{q^{k_1}-1}{q-1}}\beta =\theta (k_1,q)\beta =(q^{k_1-1}+\cdots +q+1)\beta$, $\beta \in \mathbb{N}$. Since $\alpha w+\beta =-a+\beta \ge 0$, we have $a\le \beta$. It follows that the nonzero weights of the code belong to the following set of positive integers $\{q^{k_1-1},2q^{k_1-1},\dots ,\beta q^{k_1-1}\}$. This means that, if C is not the replicated simplex code, then $\beta \ge 2$.

If C is a projective PSD two-weight code of length $n=\theta (k_1,q)\beta$ and dimension $2k_1$, its nonzero weights are $q^{k_1-1}(\beta -1)$ and $q^{k_1-1}\beta$. For the binary field, the codes have parameters $[(2^{k_1}-1)\beta ,2k_1,\{2^{k_1-1}(\beta -1),2^{k_1-1}\beta \}]$; for example, for $\beta =2$, the parameters are $[6,4,\{2,4\left\}\right]$, $[14,6,\{4,8\left\}\right]$, $[30,8,\{8,16\left\}\right]$, $[62,10,\{16,32\left\}\right]$, $[126,12,\{32,64\left\}\right]$, etc.

Example 4. 

There are two even ${[6,4,2]}_2$ codes of full length, namely codes $C_1$ and $C_2$, with characteristic vectors ${\chi }_1$, ${\chi }_2$, and weight enumerators $W_1$ and $W_2$, respectively, where

$${\chi }_1=(2,1,0,1,0,0,0,1,0,0,0,0,0,1,0),W_1\left(y\right)=1+7y^2+7y^4+y^6,$$

$${\chi }_2=(1,1,1,1,0,0,0,1,0,0,0,1,0,0,0),W_2\left(y\right)=1+6y^2+9y^4.$$

For this length, we take $\alpha =-1/2$, $\beta =2$. Since $-{\displaystyle \frac{1}{2}}·6+2<0$, we cannot consider a projective dual code of $C_1$, which means that $C_1$ is not projective self-dual. But, for $C_2$, we have

$$-{\displaystyle \frac{1}{2}}{\chi }_2\mathcal{N}\left(M_4\right)+(2,2,\dots ,2)=(1,1,1,1,0,0,0,1,0,0,0,1,0,0,0)={\chi }_2.$$

Hence, this code is not only PSD but self-polar.

Example 5. 

The codes in the family ${\Phi }_{k^{-}}$ from [14] have parameters $[(2^{k_1}-1)2^{k_1-1},2k_1$, $\{2^{2k_1-2}-2^{k_1-1},2^{2k_1-2}\}]$ and can be obtained in this case for $\beta =2^{k_1-1}$. The two-weight code from the previous example belongs to this family. There are exactly seven inequivalent ${[28,6,\{12,16\}]}_2$ codes in ${\Phi }_{6^{-}}$.

Example 6. 

For a positive integer $k_1$ and a prime power q, ${\mathfrak{S}}_{k_1,q}\oplus {\mathfrak{S}}_{k_1,q}$ is a projective two-weight code with parameters $[2{\displaystyle \frac{q^{k_1}-1}{q-1}},2k_1,q^{k_1-1}]$ and weight enumerator $W\left(y\right)=1+2(q^{k_1}-1)y^{q^{k_1-1}}+(q^{2k_1}-2q^{k_1}+1)y^{2q^{k_1-1}}$. Its characteristic vector is

$$\chi =(\underset{\theta (k_1,q)}{\underbrace{11\dots 1}}\underset{q^{k_1}}{\underbrace{10\dots 0}}\underset{q^{k_1}}{\underbrace{10\dots 0}}\dots \underset{q^{k_1}}{\underbrace{10\dots 0}}).$$

Computing ${\chi }_{\alpha ,\beta }=-{\displaystyle \frac{1}{2^{k_1-1}}}\chi +2=\chi$, we see that this code is self-polar. Thus, we obtain an infinite family of q-ary projective self-polar codes. If we take the code $C\cong t{\mathfrak{S}}_{k_1,q}\oplus (\beta -t){\mathfrak{S}}_{k_1,q}$, $1\le t<\beta$, where $t{\mathfrak{S}}_{k_1,q}=({\mathfrak{S}}_{k_1,q}|{\mathfrak{S}}_{k_1,q}|\dots |{\mathfrak{S}}_{k_1,q})$ is the concatenation of t copies of ${\mathfrak{S}}_{k_1,q}$, then C is a 3-weight self-polar code.

We will also provide an example for a projective self-dual 4-weight binary code.

Example 7. 

Let C be the binary $[12,4,2]$ code with a generator matrix

$$G=\left(\begin{array}{c}100000001000\\ 111111100100\\ 111111100010\\ 111100010001\end{array}\right).$$

This code has a weight enumerator $W\left(y\right)=1+2y^2+y^4+4y^6+8y^8$ and characteristic vector (with respect to the given generator matrix)

$$\chi =(2,1,0,1,0,3,3,1,0,0,0,0,0,0,1).$$

For the projective dual code, we obtain ${\chi }^{\prime }=(1,0,1,0,1,3,0,3,1,0,0,0,0,2,0)$ and

$$G^{\prime }=\left(\begin{array}{c}000000111111\\ 001111000011\\ 010111000011\\ 111000000100\end{array}\right).$$

It is easy to verify that these two codes are equivalent, and therefore C is a 4-weight projective self-dual code.

If k is odd ($k\ge 3$), then q must be an even power of a prime, or $q=p^{2s}$, where p is prime and s is a positive integer. Then, $q^{k/2}=p^{sk}$. Now,

$$\alpha ={\displaystyle \frac{ϵ}{p^{s(k-2)}}},\beta =-{\displaystyle \frac{p^{2s}-1}{1+ϵp^{sk}}}n,$$

and the weights have the form $w=p^{s(k-2)}a$.

Now, we again consider two cases according to (4).

($i_o$)

Now, $\alpha ={\displaystyle \frac{1}{p^{s(k-2)}}}$ and $\beta =-{\displaystyle \frac{(p^s-1)(p^s+1)}{1+p^{sk}}}n$. Since ${\displaystyle \frac{p^{sk}+1}{p^s+1}}=\theta (k,-p^s)$ is a positive integer, we have $\beta =-{\displaystyle \frac{(p^s-1)n}{\theta (k,-p^s)}}\in \mathbb{Z}$, and thus $n=\theta (k,-p^s)t$, $\beta =-(p^s-1)t$, $a\ge (p^s-1)t$. In this case, the codes have parameters $[{\displaystyle \frac{p^{sk}+1}{p^s+1}}t,k,\ge p^{s(k-2)}(p^s-1)t]$.

Example 8. 

Let $q=4$ and C be a ${[{\displaystyle \frac{2^k+1}{3}}t,k,\ge 2^{(k-2)}t]}_4$ code. One ${[6,3,4]}_4$ and one ${[9,3,6]}_4$ two-weight PSD codes are presented in [13].

($i{i}_o$)

If $\alpha =-{\displaystyle \frac{1}{p^{s(k-2)}}}$ and $\beta ={\displaystyle \frac{(p^s-1)(p^s+1)}{p^{sk}-1}}n={\displaystyle \frac{(p^s+1)n}{\theta (k,p^s)}}$, we have ${\displaystyle \frac{p^{sk}-1}{p^s-1}}\in \mathbb{Z}$, but $gcd({\displaystyle \frac{p^{sk}-1}{p^s-1}},p^s+1)=1$. Hence, $n={\displaystyle \frac{p^{sk}-1}{p^s-1}}t=\theta (k,p^s)t$ and $\beta =(p^s+1)t$ for a positive integer t. Since $\alpha w+\beta =-a+(p^s+1)t\ge 0$, then $a\le (p^s+1)t$.

Example 9. 

Let C again be a quaternary code, $p=2$, $s=1$. In this case, C is a code of dimension k and length $(2^k-1)t$. There is one two-weight quaternary ${[7,3,4]}_4$ code, and it is projective self-dual [13].

4. Self-Polar Codes—Computational Aspects

Let C be a linear PSD ${[n,k]}_q$ code with a characteristic vector $\chi$. First, we consider only projective codes, and in such a case the vector $\chi$ is binary. To check whether the code C is self-polar, we use the following matrices: $N_{\chi }=\left(\begin{array}{c}\chi \\ \mathcal{N}\left(M_k\right)\end{array}\right)$ and $N_{\chi ,\alpha ,\beta }=\left(\begin{array}{cc}0& \chi \\ {\chi }_{\alpha ,\beta }^T& \mathcal{N}\left(M_k\right)\end{array}\right)$. Obviously, if ${\chi }_{\alpha ,\beta }=\chi$, this matrix is symmetric, as well as the matrix $M\left(G\right)$ defined in Theorem 2.

We take a PSD code, which means that for some parameters $\alpha$ and $\beta$ the codes with characteristic vectors $\chi$ and ${\chi }_{\alpha ,\beta }$ are equivalent. From the previous section, we know that $\alpha$ and $\beta$ depend on the code parameters and are fixed for a given PSD ${[n,k]}_q$ code. Therefore, to verify that the code is self-polar, we need to prove that there are characteristic vectors of C and its projective dual code $C_{\alpha ,\beta }$ such that the corresponding matrix $N_{\chi ,\alpha ,\beta }$ is symmetric.

If we consider $N_{\chi ,\alpha ,\beta }$ as an incidence matrix of an incidence structure, this structure is self-polar if there exists a permutation matrix P such that $P{N}_{\chi ,\alpha ,\beta }=N_{\chi ,\alpha ,\beta }^T{P}^T$ [15]. The matrix P permutes the rows of $N_{\chi ,\alpha ,\beta }$, and $P^T$ permutes the columns of the transpose matrix. According to [16], two projective linear ${[n,k]}_q$ codes are equivalent if and only if their characteristic vectors belong to one orbit under the action of ${\mathrm{Aut}}_k$ on the set of all characteristic vectors of the projective linear ${[n,k]}_q$ codes, where ${\mathrm{Aut}}_k$ is the subgroup of the symmetric group $S_{\theta (k,q)}$, which consists of all permutation automorphisms of the rows of the matrix $\mathcal{N}\left(M_k\right)$. This means that, if $\sigma \in {\mathrm{Aut}}_k$, applying $\sigma$ to the rows of $\mathcal{N}\left(M_k\right)$, we obtain a matrix whose columns are the same but possibly in a different order. If P is the permutation matrix corresponding to $\sigma$, then there is another $\theta (k,q)\times \theta (k,q)$ permutation matrix Q such that $P\mathcal{N}\left(M_k\right)=\mathcal{N}\left(M_k\right)Q$.

Consider the characteristic vector $\chi P$ for $P\in {\mathrm{Aut}}_k$. Then,

$$\alpha \chi P\mathcal{N}\left(M_k\right)+\beta \mathbf{1}=\alpha \chi \mathcal{N}\left(M_k\right)Q+\beta \mathbf{1}=(\alpha \chi \mathcal{N}\left(M_k\right)+\beta \mathbf{1})Q={\chi }_{\alpha ,\beta }Q,$$

which proves that ${\left(\chi P\right)}_{\alpha ,\beta }={\chi }_{\alpha ,\beta }Q$.

Let $\overline{P}=\left(\begin{array}{cc}1& \mathbf{0}\\ {\mathbf{0}}^T& P\end{array}\right)$ and $\overline{Q}=\left(\begin{array}{cc}1& \mathbf{0}\\ {\mathbf{0}}^T& Q\end{array}\right)$. Then,

$${\overline{Q}}^T{N}_{\chi ,\alpha ,\beta }\overline{P}=\left(\begin{array}{cc}0& \chi P\\ Q^T{\chi }_{\alpha ,\beta }^T& Q^T\mathcal{N}\left(M_k\right)P\end{array}\right)=\left(\begin{array}{cc}0& \chi P\\ {\left(\chi P\right)}_{\alpha ,\beta }^T& \mathcal{N}\left(M_k\right)\end{array}\right)=N_{\chi P,\alpha ,\beta }.$$

Hence, if the code C is self-polar, the matrix $N_{\chi ,\alpha ,\beta }$ is equivalent to a symmetric matrix.

The above reasoning shows that we need an algorithm to check whether a given square matrix is equivalent to a symmetric matrix.

4.1. An Algorithm for Checking Whether a Given Square Matrix Is Equivalent to a Symmetric Matrix

We only consider binary matrices that are equivalent to their transpose matrices. Let A be a square $n\times n$ binary matrix of this type. Since we use canonical forms in the equivalence test, without loss of generality, we can assume that A is in canonical form. Let ${\mathcal{P}}_n$ be the group of all $n\times n$ permutation matrices. As already mentioned in this paper, we consider the following equivalence in the set ${\mathcal{M}}_n\left({\mathbb{F}}_2\right)$ of all $n\times n$ binary matrices: two matrices $A,B\in {\mathcal{M}}_n\left({\mathbb{F}}_2\right)$ are equivalent if the matrix B can be obtained after permuting the rows and columns of A. This means that $B=PAQ$ for two permutation matrices $P,Q\in {\mathcal{P}}_n$. This equivalence corresponds to an action of the group ${\mathcal{P}}_n\times {\mathcal{P}}_n$ on the set ${\mathcal{M}}_n\left({\mathbb{F}}_2\right)$, and the equivalence classes are the orbits under this action. The canonical representative of an orbit is a unique matrix from the orbit, and the canonical form of a matrix is the canonical representative of its equivalence class (orbit). So, all matrices in one equivalence class have the same canonical form. Description and references regarding the canonical form are provided in [16].

Consider the following automorphism group of A:

$$\mathrm{PAut}\left(A\right)=\{(P_1,P_2)\in {\mathcal{P}}_n\times {\mathcal{P}}_n:P_{1}A{P}_2=A\}.$$

If $\mathrm{PAut}\left(A\right)$ is trivial, there is only one pair $(T_1,T_2)\in {\mathcal{P}}_n\times {\mathcal{P}}_n$ such that $T_{1}A{T}_2=A^T$. If A is equivalent to a symmetric matrix, then $P_{3}A=A^T{P}_3^T$ for a permutation matrix $P_3$. Hence, $P_{3}A{P}_3=A^T$ and $T_1=P_3=T_2$. It follows that A is equivalent to a symmetric matrix if and only if $T_1=T_2$ and this symmetric matrix is $T_{1}A$. If the group $\mathrm{PAut}\left(A\right)$ is not trivial, $\mathrm{PAut}\left(A^T\right)=\{(P_2^T,P_1^T)\forall (P_1,P_2)\in \mathrm{PAut}\left(A\right)\}$. If $P_{3}A=A^T{P}_3^T$, then $P_3{P}_{1}A{P}_2{P}_3^T=A^T$ for any $(P_1,P_2)\in \mathrm{PAut}\left(A\right)$. These considerations prove the correctness of the algorithm presented below.

We present the transformation of a matrix to a symmetric form in the following Algorithm 1.

Algorithm 1. Checking for equivalence to a symmetric matrix

Input: A square binary matrix B.

Output: If B is equivalent to a symmetric matrix, the output is $B_a\cong B$; otherwise, the answer is negative. Compute the canonical form of B, and let this be matrix A. We find the canonical map $(T_1,T_2)$ and the automorphism group $\mathrm{PAut}\left(A^T\right)$. The canonical map sends the matrix into its canonical form, which is $T_1{A}^T{T}_2$. If this canonical form is not the matrix A, the given matrix cannot be equivalent to a symmetric matrix. Only if $T_1{A}^T{T}_2=A$, we continue the algorithm. For all matrices Q for which $(P,Q)\in \mathrm{PAut}\left(A^T\right)$ for a matrix $P\in {\mathcal{P}}_n$, do the following: Check whether the matrix $B_s={\left(Q{T}_2\right)}^{T}A$ is symmetric. If yes, B is equivalent to the symmetric matrix $B_s$ and the algorithm terminates with a positive answer. If ${\left(Q{T}_2\right)}^{T}A$ is not symmetric for all matrices Q, then B is not equivalent to a symmetric matrix and the algorithm terminates with a negative answer.

The complexity of this algorithm depends on the order of the automorphism group $\mathrm{PAut}\left(A^T\right)$. If the group is not trivial and the matrix B is equivalent to a symmetric matrix, there are actually more symmetric matrices equivalent to B.

4.2. Algorithm for Checking the Self-Polarity

For the following algorithm, we require an equivalence relation in the set of all symmetric binary matrices that is similar to the graph isomorphism. If we consider the symmetric matrices $A_1$ and $A_2$ as adjacency matrices of the undirected graphs $G_1$ and $G_2$, respectively, the two graphs are isomorphic if and only if there is a permutation matrix P such that $A_2=P^T{A}_{1}P$ [17]. In this case, we will say that the matrices $A_1$ and $A_2$ are graph-equivalent.

It is important to check when the characteristic vector $\chi$ has the same weight as some of the rows of the matrix $N_{\chi ,\alpha ,\beta }$. The weights of the vector rows in $N_{\chi ,\alpha ,\beta }$ are

$$\mathrm{wt}(0,\chi )=n,\mathrm{wt}(0,u)=q^{k-1},\mathrm{wt}(1,u)=q^{k-1}+1,$$

where u is a vector row in $\mathcal{N}\left(M_k\right)$. The possible values of the length n are provided in Section 3. In each of these cases, n cannot be equal to a power of q. But, there are a few possibilities when $n=q^{k-1}+1$.

• Let $k=2k_1$. It is easy to see that, if d is the greatest common divisor of $q^{k_1}+1$ or $q^{k_1}-1$ with $q^{k-1}+1=q^{2k_1-1}+1$, then d divides $q+1$. If $k_1=1$, then $n=q+1$, and thus C must be a projective $[q+1,2]$ code. The only such code is the simplex code ${\mathfrak{S}}_{2,q}$. Let $k_1\ge 2$. In the case $\left(i_1\right)$, if $n=(q^{k_1}+1)t=n=q^{k-1}+1$, then $d=q^{k_1}+1\mid q+1$, which is not possible. If q and t are odd and $n={\displaystyle \frac{q^{k_1}+1}{2}}t$ for an odd positive integer t (case $\left(i_2\right)$), $d={\displaystyle \frac{q^{k_1}+1}{2}}$ or $q^{k_1}+1$, but, in both cases, $n\ne q^{k-1}+1$.
  If $n={\displaystyle \frac{q^{k_1}-1}{q-1}}\beta$, $k_1\ge 2$, the needed equality holds only for $k_1=2$, $t=q^2-q+1$, and $n=q^3+1$. These codes have parameters $[q^3+1,4,\{q(q^2-q),q(q^2-q+1)\}]$, and they are complements of the $[q^2+q,4,\{q^2-q,q^2\}]$ codes (the codes denoted by SU2 in [10] for $l=2$ and $i=q$ have these parameters). Since $q^2+q<q^3+1$, we can study only the code SU2, for which the first row of the matrix $N_{\chi ,\alpha ,\beta }$ has a different weight compared to the other rows of the same matrix.
• Let k be odd, $k\ge 3$, $q=p^{2s}$, and $n={\displaystyle \frac{p^{sk}\pm 1}{p^s\pm 1}}t$. As in the previous case, if $d=gcd({\displaystyle \frac{p^{sk}\pm 1}{p^s\pm 1}},p^{2s(k-1)}+1)$, then $d\mid q+1$. But, when $n={\displaystyle \frac{p^{sk}\pm 1}{p^s\pm 1}}t=p^{2s(k-1)}+1$, $d={\displaystyle \frac{p^{sk}\pm 1}{p^s\pm 1}}\mid p^{2s}+1$, which is impossible for $k\ge 3$.

Hence, without loss of generality, we can suppose that $\mathrm{wt}\left(\chi \right)\notin \{q^{k-1},q^{k-1}+1\}$.

Next, we are looking for a characteristic vector ${\chi }^{\left(s\right)}$ of the self-polar code C such that ${\chi }_{\alpha ,\beta }^{\left(s\right)}={\chi }^{\left(s\right)}$. Let $N_{\chi ,\alpha ,\beta }$ be equivalent to the symmetric matrix $\overline{A}$. Without loss of generality, we can consider $\mathrm{wt}\left(\chi \right)=n\ne q^{k-1}+1$ (as described above) and can take $\overline{A}=\left(\begin{array}{cc}0& a\\ a^T& A\end{array}\right)$, where $\mathrm{wt}\left(a\right)=\mathrm{wt}\left(\chi \right)$. The matrix A is also symmetric and is equivalent to the symmetric matrix $\mathcal{N}\left(M_k\right)$, but we need to check if these two matrices are graph-equivalent. If yes, there is a permutation matrix P such that $P^{T}AP=\mathcal{N}\left(M_k\right)$. Let $\overline{P}=\left(\begin{array}{cc}1& \mathbf{0}\\ {\mathbf{0}}^T& P\end{array}\right)$. For the symmetric matrix ${\overline{P}}^T\overline{A}\overline{P}$, the following holds:

$$\begin{array}{cc}\hfill {\overline{P}}^T\overline{A}\overline{P}& =\left(\begin{array}{cc}1& \mathbf{0}\\ {\mathbf{0}}^T& P^T\end{array}\right)\left(\begin{array}{cc}0& a\\ a^T& A\end{array}\right)\left(\begin{array}{cc}1& \mathbf{0}\\ {\mathbf{0}}^T& P\end{array}\right)\hfill \\ & =\left(\begin{array}{cc}0& aP\\ P^T{a}^T& P^{T}AP\end{array}\right)=\left(\begin{array}{cc}0& aP\\ P^T{a}^T& \mathcal{N}\left(M_k\right)\end{array}\right).\hfill \end{array}$$

Hence, $aP$ is the required characteristic vector.

However, if A and $\mathcal{N}\left(M_k\right)$ are not graph-equivalent, we repeat the algorithm with another symmetric matrix $\overline{B}$ that is equivalent to $N_{\chi ,\alpha ,\beta }$ but not graph-equivalent to $\overline{A}$.

The described algorithm proceeds in the following steps:

• Checking whether the matrix $N_{\chi ,\alpha ,\beta }$ is equivalent to a symmetric matrix, say $\overline{A}$. If no, the algorithm terminates with the answer that the code is not self-polar. If yes, then we need all symmetric matrices, equivalent to $\overline{A}$, that are representatives of different equivalent classes according to the graph-equivalence.
• If the matrices A and $\mathcal{N}\left(M_k\right)$ are not graph-equivalent, then we take another matrix from the representatives of equivalent classes from the previous step. If neither of these representatives is graph-equivalent to $\mathcal{N}\left(M_k\right)$, the algorithm terminates with negative answer.
• Let A be graph-equivalent to $\mathcal{N}\left(M_k\right)$, finding a permutation matrix P such that $P^{T}AP=\mathcal{N}\left(M_k\right)$ (described in the above paragraph).
• The vector $aP$ is the needed characteristic vector.

In this algorithm, we need to prove that the codes with characteristic vectors $\chi$ and $aP$ are equivalent. Since the first row and column have specific weights, different from the other rows and columns, we have

$$\begin{array}{cc}\hfill \overline{A}& =\overline{Q_1}{N}_{\chi ,\alpha ,\beta }\overline{Q_2}=\left(\begin{array}{cc}1& \mathbf{0}\\ {\mathbf{0}}^T& Q_1\end{array}\right)\left(\begin{array}{cc}0& \chi \\ {\chi }_{\alpha ,\beta }^T& \mathcal{N}\left(M_k\right)\end{array}\right)\left(\begin{array}{cc}1& \mathbf{0}\\ {\mathbf{0}}^T& Q_2\end{array}\right)\hfill \\ & =\left(\begin{array}{cc}0& \chi Q_2\\ Q_1{\chi }_{\alpha ,\beta }^T& Q_1\mathcal{N}\left(M_k\right)Q_2\end{array}\right).\hfill \end{array}$$

Hence, $a=\chi Q_2$ and $P^T{Q}_1\mathcal{N}\left(M_k\right)Q_{2}P=\mathcal{N}\left(M_k\right)$. It follows that $Q_{2}P\in {\mathrm{Aut}}_k$, and therefore a code with characteristic vector $\chi Q_{2}P$ is equivalent to the considered code C [16].

If the code is not projective, we construct matrices $N_{\chi }$ and $N_{\chi ,\alpha ,\beta }$ in the following way. To obtain matrix $N_{\chi }$, we append $\mathcal{N}\left(M_k\right)$ with s more rows, where s is the maximal value of a coordinate in $\chi$. The j-th coordinate of the i-th added row is 1 if ${\chi }_j\ge i$ and 0 otherwise. Similarly, we construct $N_{\chi ,\alpha ,\beta }$, by expanding $N_{\chi }$ by the corresponding number of columns.

5. Applications

The most natural study of code self-polarity is related to projective two-weight codes. The reasons for this are as follows. These codes are related to many other interesting combinatorial structures, such as strongly regular graphs, bent functions, etc. and the self-polarity property has a direct relation to some properties of these objects. For example, some self-polar two-weight codes correspond to self-dual bent functions [6].

Information about SRGs, their properties, and their connection to linear codes can be found in [18]. The parameters of the SRGs associated with the listed projective two-weight binary and ternary codes are also provided in [13]. A strongly regular graph (SRG) is a regular graph $G=(V,E)$ with v vertices and degree k such that, for some given non-negative integers $\lambda$ and $\mu$, every two adjacent vertices have $\lambda$ common neighbors and every two non-adjacent vertices have $\mu$ common neighbors. Such a strongly regular graph is denoted by srg$(v,k,\lambda ,\mu )$.

A survey on two-weight codes was provided by Calderbank and Kantor [10]. An overview with additional families and examples was presented in [18].

When studying projective two-weight codes with small parameters, it is found that a large number of them are PSD. It is natural to ask how many of these PSD codes are also self-polar. Therefore, in this section, we examine for self-polarity all the two-weight codes classified in [13]. Along with this, we extend these results with new classification results, such as finding all ${[36,4,25]}_5$ codes.

It is known that to every two-weight code there corresponds a strongly regular graph with $q^k$ vertices. By examining the self-polarity, it was found that some of the codes also correspond to strongly regular graphs with n vertices, where n is the length of the code, and degree equal to one of the weights. The question remains, is there a relationship between the two graphs corresponding to the given code, and what is it?

From the study, it became clear that many non-projective codes are also self-polar. In Section 3, we presented some three- and even four-weight self-polar codes. In this section, we investigate binary and ternary three-weight codes, which are related to the presented projective two-weight codes. More precisely, for a given two-weight ${[n,k,\{w_1,w_2\}]}_q$ code, we consider the three-weight codes of the same length and dimension and three weights, $w_1$, $w_2$, and $w_3$.

The classification results were obtained using the program Generation, and the algorithms described in the previous section were implemented on the base of functions from the software package LCEquivalence, v. 1.1. These programs are freely available and can be downloaded from http://www.moi.math.bas.bg/moiuser/~data/Software/QextNewEdition.html (accessed on 1 September 2024).

Most of the binary two-weight codes, provided in

Table 1. Binary two-weight codes.

Code	Number	Weight Enumerators	PSD	Self-Polar	Additional Information
$[5,4,2]$	1	$1+10z^2+5z^4$	1	1	Ref. [13], Example 1: $k_1=2,t=1$
$[6,4,2]$	1	$1+6z^2+9z^4$	1	1	[10]
$[12,4,6]$	1	$1+12z^6+3z^8$	1	0
$[14,6,4]$	1	$1+14z^4+49z^8$	1	1	[10]
$[18,6,8]$	1	$1+45z^8+18z^{12}$	1	1	Example 1: $k_1=3,t=2$
$[21,6,8]$	2	$1+21z^8+42z^{12}$	2	2	[10]
$[27,6,12]$	5	$1+36z^{12}+27z^{16}$	5	4	Refs. [10,20], Example 1: $k_1=3,t=3$
$[28,6,12]$	7	$1+28z^{12}+35z^{16}$	7	6	Refs. [10,14,20], Example 6: $k_1=3$
$[56,6,28]$	1	$1+56z^{28}+7z^{32}$	1	-	the code may be self-polar
$[30,8,8]$	1	$1+30z^8+225z^{16}$	1	1	[10]
$[45,8,16]$	2	$1+45z^{16}+210z^{24}$	2	2	[10]
$[51,8,24]$	1	$1+204z^{24}+51z^{32}$	1	1	Ref. [13], Example 1: $k_1=4,t=3$
$[60,8,24]$	12	$1+60z^{24}+195z^{32}$	12	11	[10]
$[68,8,32]$	41	$1+187z^{32}+68z^{40}$	29	27	Ref. [13], Example 1: $k_1=4,t=4$

,

Table 2. Ternary two-weight codes.

Code	Number	Weight Enumerators	PSD	Self-Polar	Additional Information
$[10,4,6]$	1	$1+60z^6+20z^9$	1	1	Ref. [13], Example 3: $k_1=2,t=1$
$[12,4,6]$	2	$1+24z^6+56z^9$	2	2
$[15,4,9]$	2	$1+50z^9+30z^{12}$	2	0	Refs. [13,19], Example 3: $k_1=2,t=3$
$[16,4,9]$	4	$1+32z^9+48z^{12}$	4	4
$[20,4,12]$	4	$1+40z^{12}+40z^{15}$	4	4	Ref. [13], Example 3: $k_1=2,t=2$
$[11,5,6]$	1	$1+132z^6+110z^9$	0	0
$[55,5,36]$	1	$1+220z^{36}+22z^{45}$	0	0	[8]
$[56,6,36]$	1	$1+616z^{36}+112z^{45}$	1	1	Ref. [8],Example 3: $k_1=3,t=2$

and

Table 3. Quaternary two-weight codes.

Code	Number	Weight Enumerators	PSD	Self-Polar	Additional Information
$[6,3,4]$	1	$1+45z^4+18z^6$	1	1	Ref. [13], Example 8: $k=3,t=2$
$[7,3,4]$	1	$1+21z^4+42z^6$	1	1	Ref. [13], Example 9: $k=3,t=1$
$[9,3,6]$	1	$1+36z^6+27z^8$	1	1	Ref. [13], Example 8: $k=3,t=3$
$[10,4,4]$	1	$1+30z^4+225z^8$	1	1
$[15,4,8]$	2	$1+45z^8+210z^{12}$	2	2
$[17,4,12]$	1	$1+204z^{12}+51z^{16}$	1	1	Ref. [13], Example 2: $k_1=2,t=1$
$[20,4,12]$	7	$1+60z^{12}+195z^{16}$	7	6
$[25,4,16]$	19	$1+75z^{16}+180z^{20}$	19	13
$[30,4,20]$	68	$1+90z^{20}+165z^{24}$	66	34
$[34,4,24]$	84	$1+153z^{24}+102z^{28}$	38	33	Ref. [13], Example 2: $k_1=2,t=2$
$[35,4,24]$	231	$1+105z^{24}+150z^{28}$	179	57
$[40,4,28]$	481	$1+120z^{28}+135z^{32}$	315	93

, are known, as well as their self-duality. These codes are fully classified in [13], but some examples were previously provided in [10,19,20].

The first columns of the tables contain the parameters of the code, and the second ones contain the numbers of all the inequivalent codes of the corresponding length and dimension. In the third columns, we put the weight enumerators of the codes, but if there are no PSD codes they are omitted. PSD codes exist for all parameters of two-weight codes but not for all studied cases of three-weight codes. After the weight enumerators, the number of PSD and self-polar codes of the corresponding parameters are provided. The last columns of the tables contain additional information concerning the particular code. It is indicated which of the codes correspond to a certain example of q, $k_1$, and t (Section 3).

In the following example, we provide more details about one of the two-weight self-polar codes.

Example 10. 

Let C be the binary $[18,6,8]$ code. There exists one code with these parameters and it is a self-polar code. The weight enumerator of C is $W\left(y\right)=1+45y^8+18y^{12}$. The generator matrix for which C and its dual code have the same characteristic vector is

$$G=\left(\begin{array}{c}000000111111111111\\ 001111000000001111\\ 000011000011110011\\ 010100000100110111\\ 111111001101010011\\ 011101010010010001\end{array}\right).$$

The complementary code $\overline{C}$ is a binary $[45,6,20]$ code with weight enumerator $W\left(y\right)=1+18y^{20}+45y^{24}$, and it has a generator matrix

$$\overline{G}=\left(\begin{array}{c}000000000000000000000000011111111111111111111\\ 000000000000011111111111100000000111111111111\\ 000001111111100000011111100001111000000111111\\ 001110000111100011100111101110011000111000011\\ 010010011001100100100001110010101011011001100\\ 110100101010101001001010110110110101101010101\end{array}\right).$$

Recall that the columns of $\overline{G}$ are all columns of $S_{6,2}$, which does not belong to the matrix G. As we proved in the previous section, $\overline{C}$ is also a self-polar code.

Using G, we obtain the following symmetric matrix:

$$M\left(G\right)=G^{T}G=\left(\begin{array}{c}111111001101010011\\ 110110011011110101\\ 101101011111001101\\ 111001011011111010\\ 110011001110101111\\ 101110011100111110\\ 000000111111111111\\ 011101101101101110\\ 111111110010101100\\ 101011110110011011\\ 011110101110011101\\ 111100110001011111\\ 010111111000111011\\ 110101100111111001\\ 001111111111110000\\ 011011111011000111\\ 100111110101100111\\ 111010100111110110\end{array}\right).$$

Each row and column of $G^{T}G$ has weight 12. What is more, in this case, the main diagonal also has 12.

The studied three-weight codes are listed in

Table 4. Binary three-weight codes.

Code	Number	Weight Enumerators	PSD	Self-Polar	Additional Information
$[15,4,6]$	1	$1+2z^6+11z^8+2z^{10}$	1	0	Example 1: $k_1=2,t=3$
	2	$1+3z^6+9z^8+3z^{10}$	2	0
	6	$1+4z^6+7z^8+4z^{10}$	4	2
	4	$1+5z^6+5z^8+5z^{10}$	2	1
	4	$1+6z^6+3z^8+6z^{10}$	1	1
$[20,4,8]$	2	$1+1z^8+8z^{10}+6z^{12}$	2	0	Example 1: $k_1=2,t=4$
	3	$1+2z^8+6z^{10}+7z^{12}$	1	0
	6	$1+3z^8+4z^{10}+8z^{12}$	1	0
$[18,6,8]$	1	$1+46z^8+16z^{12}+1z^{16}$	1	1	Example 1: $k_1=3,t=2$
$[27,6,12]$	3	$1+37z^{12}+25z^{16}+1z^{20}$	3	3	Example 1: $k_1=3,t=3$
	5	$1+38z^{12}+23z^{16}+2z^{20}$	5	5
	5	$1+39z^{12}+21z^{16}+3z^{20}$	4	3
	2	$1+40z^{12}+19z^{16}+4z^{20}$	2	2
	1	$1+41z^{12}+17z^{16}+5z^{20}$	1	1
	1	$1+42z^{12}+15z^{16}+6z^{20}$	1	1
$[36,6,16]$	11	$1+28z^{16}+34z^{20}+1z^{24}$	7	7	Example 1: $k_1=3,t=4$
	109	$1+29z^{16}+32z^{20}+2z^{24}$	27	26
	479	$1+30z^{16}+30z^{20}+3z^{24}$	51	48
	1627	$1+31z^{16}+28z^{20}+4z^{24}$	94	88
	2888	$1+32z^{16}+26z^{20}+5z^{24}$	110	104
	3715	$1+33z^{16}+24z^{20}+6z^{24}$	124	118
	2764	$1+34z^{16}+22z^{20}+7z^{24}$	88	82
	1628	$1+35z^{16}+20z^{20}+8z^{24}$	59	53
	516	$1+36z^{16}+18z^{20}+9z^{24}$	21	19
	216	$1+37z^{16}+16z^{20}+10z^{24}$	20	15
	24	$1+38z^{16}+14z^{20}+11z^{24}$	1	1
	20	$1+39z^{16}+12z^{20}+12z^{24}$	3	3
	3	$1+41z^{16}+8z^{20}+14z^{24}$	1	1

and

Table 5. Ternary three-weight codes.

Code	Number	Weight Enumerators	PSD	Self-Polar	Additional Information
$[15,4,9]$	1	$1+52z^9+26z^{12}+2z^{15}$	1	0
$[16,4,6]$	4	$1+2z^6+28z^9+50z^{12}$	4	4
	5	$1+4z^6+24z^9+52z^{12}$	5	5
	4	$1+6z^6+20z^9+54z^{12}$	3	2
	3	$1+8z^6+16z^9+56z^{12}$	2	2
	1	$1+10z^6+12z^9+58z^{12}$	1	1
	1	$1+12z^6+8z^9+60z^{12}$	0	0
$[20,4,9]$	7	$1+2z^9+36z^{12}+42z^{15}$	7	5
	23	$1+4z^9+32z^{12}+44z^{15}$	15	12
	26	$1+6z^9+28z^{12}+46z^{15}$	12	6
	28	$1+8z^9+24z^{12}+48z^{15}$	20	14
	12	$1+10z^9+20z^{12}+50z^{15}$	5	2
	6	$1+12z^9+16z^{12}+52z^{15}$	3	3
	2	$1+14z^9+12z^{12}+54z^{15}$	0	0
	1	$1+16z^9+8z^{12}+56z^{15}$	1	1
$[20,4,12]$	5	$1+42z^{12}+36z^{15}+2z^{18}$	5	4	Example 2. $k_1=2,t=2$
	10	$1+44z^{12}+32z^{15}+4z^{18}$	8	5
	4	$1+46z^{12}+28z^{15}+6z^{18}$	4	2
	5	$1+48z^{12}+24z^{15}+8z^{18}$	3	1
	2	$1+50z^{12}+20z^{15}+10z^{18}$	2	0
	1	$1+52z^{12}+16z^{15}+12z^{18}$	1	1

. In the binary case, we are looking for codes with weights d, $d+t$, $d+2t$, when the codes are divisible by t. The PSD and self-polar codes with these parameters have weight enumerators $W\left(y\right)=1+A_1{y}^d+A_2{y}^{d+t}+A_3{y}^{d+2t}$, such that either $A_2+2A_3=n$ or $2A_1+A_2=n$.

Example 11. 

We consider one $[7,3,2]$ quaternary three-weight code that is self-polar. Its weight enumerator is $1+3z^2+15z^4+45z^6$. The generator matrix G and the matrix $G^{T}G$ have the following structures:

$$G=\left(\begin{array}{c}0111111\\ 1000123\\ 0233222\end{array}\right)$$

$$M\left(G\right)=G^{T}G=\left(\begin{array}{c}1000123\\ 0200222\\ 0033000\\ 0033000\\ 1200301\\ 2200013\\ 3200130\end{array}\right)$$

The third and fourth columns of G are equal. This corresponds to two equal rows in $G^{T}G$.

We list some new projective two-weight codes over ${\mathbb{F}}_5$. Classification results, as well as the number of PSD and self-polar codes, are provided in

Table 6. Two-weight codes over ${\mathbb{F}}_5$.

Code	Number	Weight Enumerators	PSD	Self-Polar
$[12,4,5]$	1	$1+48z^5+576z^{10}$	1	1
$[18,4,10]$	1	$1+72z^{10}+552z^{15}$	1	1
$[24,4,15]$	7	$1+96z^{15}+528z^{20}$	7	7
$[26,4,20]$	1	$1+520z^{20}+104z^{25}$	1	0
$[30,4,20]$	38	$1+120z^{20}+504z^{25}$	38	33
$[36,4,25]$	547	$1+144z^{25}+480z^{30}$	441	160
$[39,4,30]$	8	$1+468z^{30}+156z^{35}$	8	0

.

Finally, in

Table 7. Strongly regular graphs corresponding to PTW codes.

SRG Parameters $(\mathit{v},\mathit{k},\mathit{\lambda },\mathit{\mu })$	PTW Parameters	Weight Enumerators
(25,16,9,12)	${[25,4,16]}_4$	$1+75z^{16}+180z^{20}$
(27,16,10,8)	${[27,6,12]}_2$	$1+36z^{12}+27z^{16}$
(28,12,6,4)	${[28,6,12]}_2$	$1+28z^{12}+35z^{16}$
(36,25,16,20)	${[36,4,25]}_5$	$1+144z^{25}+480z^{30}$
(45,16,8,4)	${[45,8,16]}_2$	$1+45z^{16}+210z^{24}$
(56 45 36 36)	${[56,6,36]}_3$	$1+616z^{36}+112z^{45}$

, we list the parameters of some known SRGs that are derived from two-weight self-polar codes.

6. Conclusions

In this paper, we present an extended study on the projective self-dual (PSD) and self-polar codes. The self-polar code can be used for constructing other combinatorial structures, such as strongly regular graphs (SRGs), association schemes, bent Boolean functions, etc.

Two algorithms, connected to the problem of the self-polarity, are proposed. The first algorithm checks whether a binary square matrix can be reduced to a symmetric matrix by row and column permutations. If so, the algorithm provides the symmetric matrix (or matrices) itself. The second algorithm concerns checking the self-polarity of a PSD code. If one code is self-polar, then the algorithm returns such a generator matrix that provides one and the same characteristic vector of the code and its dual.

Using these two algorithms and the provided theoretical properties, the self-polarity of some projective two-weight (PTW) codes over fields with two, three, four, and five elements is investigated. It is shown that some of the known strongly regular graphs can be constructed using self-polar codes. The research is extended by constructing and testing for the self-polarity regarding some non-projective linear codes with three different weights. The parameters for which no PSD codes were found are not listed in the tables above, but all the studied structures are available online.

Finally, we will pose two open problems:

• In our examples, if there exists a projective PSD code of length n for which the number of codewords of the weight w is equal to $(q-1)n$ and there are also integers $\lambda$ and $\mu$ according to the parameters $(n,w,\lambda ,\mu )$ listed in Chapter 12 in [18], then there exists a strongly regular $(n,w,\lambda ,\mu )$ graph. Does this apply to all projective PSD codes with these properties?
• To investigate for self-polarity, other combinatorial structures are applied using the presented algorithms.