Embedding dimensions of matrices whose entries are indefinite distances in the pseudo-Euclidean space Hiroshi NozakiMasashi ShinoharaSho Suda

2025-05-03 0 0 504.44KB 25 页 10玖币

侵权投诉

Embedding dimensions of matrices whose entries are

indeﬁnite distances in the pseudo-Euclidean space

Hiroshi Nozaki∗Masashi Shinohara†Sho Suda‡

December 20, 2023

Abstract

A ﬁnite set of the Euclidean space is called an s-distance set provided the number

of Euclidean distances in the set is s. Determining the largest possible s-distance

set for the Euclidean space of a given dimension is challenging. This problem was

solved only when dealing with small values of sand dimensions. Lisonˇek (1997)

achieved the classiﬁcation of the largest 2-distance sets for dimensions up to 7, using

computer assistance and graph representation theory. In this study, we consider a

theory analogous to these results of Lisonˇek for the pseudo-Euclidean space Rp,q. We

consider an s-indeﬁnite-distance set in a pseudo-Euclidean space that uses the value

||x−y|| = (x1−y1)2+··· + (xp−yp)2−(xp+1 −yp+1)2− ··· − (xp+q−yp+q)2

instead of the Euclidean distance. We develop a representation theory for symmetric

matrices in the context of s-indeﬁnite-distance sets, which includes or improves the

results of Euclidean s-distance sets with large svalues. Moreover, we classify the

largest possible 2-indeﬁnite-distance sets for small dimensions.

Key words:s-distance set, graph representation, embedding dimension, pseudo-

Euclidean space

1 Introduction

A ﬁnite subset Xof the Euclidean space Rdis called an s-distance set if the number

of the distances between two distinct points in Xis s. The cardinality of an s-

distance set in Rdor the (d−1)-dimensional sphere, denoted as Sd−1, has a natural

∗Department of Mathematics Education, Aichi University of Education, 1 Hirosawa, Igaya-cho, Kariya,

Aichi 448-8542, Japan. hnozaki@auecc.aichi-edu.ac.jp

†Faculty of Education, Shiga University, 2-5-1 Hiratsu, Otsu, Shiga 520-0862, Japan.

shino@edu.shiga-u.ac.jp

‡Department of Mathematics, National Defense Academy of Japan, Yokosuka, Kanagawa 239-8686,

Japan. ssuda@nda.ac.jp

arXiv:2210.11749v2 [math.CO] 19 Dec 2023

upper bound, and determining the largest possible s-distance set for given dand s

values is a major challenge. Several results on the largest s-distance sets have been

obtained [10, 13, 17, 20, 24, 25]. The largest s-distance sets are closely related to

good combinatorial structures like designs or codes [1, 4, 7, 9, 10, 11].

For the classiﬁcation of the largest s-distance sets for small dimensions, consider-

ing the representations of graphs with srelations is useful. For disjoint symmetric bi-

nary relations R0={(x, x)|x∈S}, R1, . . . , Rson a ﬁnite set Swith S×S=Ss

i=0 Ri,

we consider a map ffrom Sto Rdsatisfying that there exist positive real numbers

a1, . . . , assuch that the distance of f(x) and f(y) is aiif (x, y)∈Ri. The image

f(S) is a representation of (S, {Ri}s

i=0) as an s-distance set in Rd. Finding repre-

sentations in minimal dimensions for a given size of Sand relations is challenging

in general. For 2-distance sets, only 2 minimal-dimensional representations exist for

a given graph [12], and Lisonˇek [15] classiﬁed the largest 2-distance sets in Rdfor

d≤7 using computer support. Moreover, for 2-distance sets, the minimal dimen-

sions of representations are explicitly obtained from the spectral information of the

adjacency matrices of a graph [23]. Moreover, it is possible to determine whether

the representation is on a sphere [19]. In this study, we consider extensions of such

results for the pseudo-Euclidean space Rp,q. The central problem addressed in this

study was investigated in previous works [5, 15].

Let Rp,q be the (p+q)-dimensional linear space over Rwith the bilinear form

⟨⟨x,y⟩⟩ =x1y1+··· +xpyp−xp+1yp+1 − ··· − xp+qyp+q

for x= (x1, . . . , xp+q)⊤,y= (y1, . . . , yp+q)⊤∈Rp+q. For a ﬁnite subset Xof Rp,q,

we deﬁne

A(X) = {||x−y||:x,y∈X, x̸=y},

where ||x|| =⟨⟨x,x⟩⟩. A ﬁnite subset Xof Rp,q is called an s-indeﬁnite-distance set

if |A(X)|=s. It is noteworthy that ||x−y|| is not a distance function except for

the Euclidean case Rp=Rp,0, and it may take on negative values. The s-indeﬁnite-

distance set in Rp,0is the s-distance set. Two subsets Xand Yof Rp,q are isomorphic

as s-indeﬁnite-distance sets if one can be transformed to the other using a function

deﬁned by f(x) = Rx+b, where Ris an element of the pseudo-orthogonal group

O(p, q) and b∈Rp,q . The s-indeﬁnite-distance sets in Rp,q are generally considered

up to isometry. An s-indeﬁnite-distance set in Rp,q is said to be proper if it is not in

Rk,l for (k, l)̸= (p, q) with k≤pand l≤q. Bannai, Bannai, and Stanton [2] gave

an upper bound |X| ≤ p+s

sfor a Euclidean s-distance set Xin Rp,0. Petrov and

Pohoata [22] also proved this bound using the Croot–Lev–Pach lemma [8]. The upper

bound for s-indeﬁnite-distance sets in Rp,q is analogously obtained using the method

given in [22] provided 0 ̸∈ A(X). We can construct inﬁnite s-indeﬁnite-distance

sets with 0 ∈A(X) for all dimensions, except for (p, q) = (1,1). An s-indeﬁnite-

distance set in R1,1with 0 ∈A(X) is ﬁnite. The problem we address in this study is

determining the largest possible s-indeﬁnite-distance sets for 0 ̸∈ A(X).

For this purpose, we would like to give the minimal-dimensions of representations

of (S, {Ri}s

i=0) in Rp,q using the spectral information of the relation matrices. For

the given relations {Ri}s

i=0 on S, a relation matrix Aiwith respect to Riis deﬁned

as a symmetric matrix. The rows and columns of this matrix are indexed by S, and

the entries in the matrix are (Ai)uv = 1 when (u, v)∈Ri, and 0 otherwise. A matrix

expressed by M=Ps

i=0 ciAiwith ci∈Ris called a dissimilarity matrix of (S, {Ri}).

Let P=I−(1/|S|)J, where Iis the identity matrix and Jis the all-one matrix.

When the signature (numbers of positive and negative eigenvalues) of −P M P is

(p, q), it indicates the presence of a subset Xof Rp,q whose indeﬁnite-distance matrix

(||x−y||)x,y∈Xis M[14]. The set X⊂Rp,q is called a representation of dissimilarity

matrix M. Moreover, there is no subset Xof Rp1,q1fulﬁlling (||x−y||)x,y∈X=M

for either p1< p or q1< q [14]. Roy [23] determined the exact minimal dimension

pfrom the spectral information of Mfor s= 2 and q= 0. We generalize his result

to the case of any s,p, and q(Theorem 3.2). This result can be used to determine

when the representation is on a sphere Sp,q (r) = {x∈Rp,q | ⟨⟨x,x⟩⟩ =r}. Moreover,

from these results, we can extend the Lisonˇek algorithm to classify the largest proper

(spherical) 2-indeﬁnite-distance sets in Rp,q for p+q≤7.

The remainder of this paper is organized as follows. In Section 2, we prove upper

bounds on the cardinality of an s-indeﬁnite-distance set in Rp,q with 0 ̸∈ A(X), and

consider the case 0 ∈A(X). In Section 3, we consider the minimal dimensions p, q,

for which a representation of a given dissimilarity matrix M=PciAiis feasible. In

Section 4, we classify the largest proper 2-indeﬁnite-distance sets in Rp,q for p+q≤7

using an extension of the Lisonˇek algorithm. In Section 5, we provide a necessary

and suﬃcient condition for a given indeﬁnite-distance matrix Mto be spherical.

Moreover, we classify the largest proper spherical 2-indeﬁnite-distance sets in Rp,q

for p+q≤7.

2 Upper bounds for s-indeﬁnite-distance sets

in Rp,q

Petrov and Pohoata [22] provided a simple proof of the upper bounds |X| ≤ d+s

s

for Euclidean s-distance sets in Rdusing the Croot–Lev–Pach lemma [8]. The up-

per bound for s-indeﬁnite-distance sets in Rp,q can be obtained using the method

described in [22]. Theorem 2.1 is a key theorem presented in [22]. The pair (r, s) is

called the signature of symmetric matrix M, where r(resp.s) is the number of pos-

itive (resp. negative) eigenvalues of Mcounting multiplicities. Let sign(M) denote

the signature of M.

Theorem 2.1 ([22]).Let Vbe a ﬁnite-dimensional vector space over a ﬁeld F, and X

be a ﬁnite set in V. Let sbe a nonnegative integer. Let F(x,y)be a 2·dim V-variate

polynomial with coeﬃcients in Fand a degree no greater than 2s+ 1. Let the matrix

M= (F(x,y))x,y∈X, and (r+, r−) = sign(M). Let dims(X)be the dimension of

the space of polynomials of degree at most sconsidered as functions on X. Then the

following hold.

(1) rank(M)≤2 dims(X).

(2) If F=R, then max{r+, r−} ≤ dims(X).

Theorem 2.2. Let Xbe an s-indeﬁnite-distance set in Rp,q . If 0̸∈ A(X)holds,

then

|X| ≤ p+q+s

s.

Proof. Deﬁne the polynomial Fof degree 2sas

F(x,y) = Y

α∈A(X)

(α− ||x−y||)/α

for 0 ̸∈ A(X). This polynomial satisﬁes F(x,x) = 1 and F(x,y) = 0 for distinct

x,y∈X. Here, M= (F(x,y))x,y∈Xis the identity matrix. Therefore, Theorem 2.1

implies that

|X|=r+≤dims(X)≤dims(Rp+q) = p+q+s

s.

If 0 ∈A(X) and (p, q)̸= (1,1), then there exists a proper s-indeﬁnite-distance

set Xin Rp,q with |X|=∞. This can be expressed as follows. We can assume that

p≥2 and q≥1 because the constructions are similar for p= 1 and q≥2. Let Ls

be a Euclidean s-distance set in R1. For instance, Lsmay be a set of s+ 1 points,

wherein two consecutive points maintain an equal interval. We deﬁne L0to be an

empty set. Since Lsis Euclidean, 0 ̸∈ A(Ls). Let V= SpanR{e2+ep+1}, where ei

is the vector with i-th entry 1, and 0 otherwise. It is noteworthy that A(V) = {0}.

Let L′

s={(ℓ, 0,...,0) ∈Rp,q |ℓ∈Ls}and

X={ℓ+v∈Rp,q |ℓ∈L′

s−1,v∈V}.

Therefore, for any x=ℓ+v,x′=ℓ′+v′∈X,

||x−x′|| =||ℓ−ℓ′|| +||v−v′|| ∈ A(Ls−1)∪ {0},

and |A(X)|=s. This set Xis an inﬁnite s-indeﬁnite-distance set in Rp,q with

distance 0.

The set {(x, y)∈R1,1|x=y}is an inﬁnite 1-indeﬁnite-distance set in R1,1with

A(X) = {0}. For s≥2, the cardinality of an s-indeﬁnite-distance set in R1,1is ﬁnite

even if 0 ∈A(X). This is substantiated below. For x= (x1, x2)∈R1,1and a∈R,

we deﬁne

Dx(a) = {x′∈R1,1:||x−x′|| =a}.

If a= 0, then Dx(a) is the union of two lines ℓ±with slopes ±1 and intersecting at

(x1, x2). If a̸= 0, Dx(a) is hyperbolic and its asymptotes are ℓ±. It should be noted

that Dx(a)∩Dx′(a′) is inﬁnite for distinct x,x′∈R1,1if and only if a=a′= 0 and

||x−x′|| = 0. Suppose any x,x′∈Xsatisfy ||x−x′|| ̸= 0. Then |X|is ﬁnite since

X\ {x,x′} ⊂ [

a,a′∈A(X)

(Dx(a)∩Dx′(a′)).

Therefore, an s-indeﬁnite-distance set X⊂R1,1for s≥2 is ﬁnite even for 0 ∈A(X).

3 Embedding dimensions of dissimilarity ma-

trices

Let Vbe a ﬁnite set, with |V|=n. We call R={R0, R1, . . . , Rs}relations on Vif

Ris a partition of V×V,R0={(u, u)|u∈V}, and Riis a nonempty symmetric

relation for each i. In this paper, we call (V, R) an s-relation graph. A matrix Aiis

arelation matrix with respect to Riif Aiis a symmetric (0,1)-matrix indexed by V

with (u, v)-entries

Ai(u, v) = (1 if (u, v)∈Ri,

0 otherwise.

A matrix DR(a) = D(a) = Ps

i=1 aiAiis called a dissimilarity matrix on (V, R) for

a= (a1, . . . , as)⊤∈Rs.

For X⊂Rp,q, the matrix D(X)=(||x−y||)x,y∈Xis called an indeﬁnite-distance

matrix of X. A dissimilarity matrix DR(a) on (V, R) is representable in Rp,q if there

exists X⊂Rp,q such that DR(a) = D(X). This set Xis called a representation

of DR(a). An s-relation graph (V, R) is representable in Rp,q if there exists a∈Rs

such that DR(a) = D(X) for some X⊂Rp,q . Moreover, the set Xis called a

representation of (V, R)in Rp,q. Let Xbe an n×(p+q) matrix whose rows are the

coordinates of the npoints of X⊂Rp,q. The dimensionality of DR(a) is the least

rank(X) in all representations Xof DR(a).

Let jbe the all-one vector. For a symmetric matrix Mand a vector ℓwith

ℓ⊤j= 1, let FM(ℓ) be the symmetric matrix deﬁned as

FM(ℓ) = −(I−jℓ⊤)M(I−ℓj⊤),

where Iis the identity matrix. Note that the matrix I−ℓj⊤is a projection matrix

onto j⊥. From (I−ℓj⊤)ℓ= 0, the vector ℓis an eigenvector of FM(ℓ) with an

eigenvalue of 0. Direct calculations show that

FD(X)(ℓ)=(−2⟨⟨x−u,y−u⟩⟩)x,y∈X,

where u=Px∈Xℓxxand ℓxis the x-th entry of ℓ. From the diagonalization of a

symmetric matrix Mwith signature (r, s), we obtain the coordinates of the points

of X⊂Rp,q such that M= (⟨⟨x,y⟩⟩)x,y∈X. Gower [14] showed that the signature

of FDR(a)(ℓ) is the same for all ℓwith ℓ⊤j= 1 and obtained the following theorem:

Theorem 3.1 (Theorems 8 and 9 in [14]).Let (p, q)be the signature of FDR(a)(ℓ),

which does not depend on the choice of ℓ. Then the dimensionality of DR(a)is p+q.

Moreover, there is no representation of DR(a)in Rs,t that satisﬁes s<por t<q.

The smallest dimension given in Theorem 3.1 as sign(FDR(a)(ℓ)) = (p, q) is called

the embedding dimension of a dissimilarity matrix DR(a). The signature of FDR(a)(ℓ)

can be calculated using the eigenvalues and main angles of DR(a) from Theorem 3.2.

Let Mbe a real symmetric matrix of order n. Let τibe an eigenvalue of Mwith

eigenspace Eiand an orthogonal projection matrix Eionto Eifor i= 1, . . . , r. The

main angle of τi(or Ei) is deﬁned as

βi=1

√nq(Eij)⊤(Eij).

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Embeddingdimensionsofmatriceswhoseentriesareindefinitedistancesinthepseudo-EuclideanspaceHiroshiNozaki∗MasashiShinohara†ShoSuda‡December20,2023AbstractAfinitesetoftheEuclideanspaceiscalledans-distancesetprovidedthenumberofEuclideandistancesinthesetiss.Determiningthelargestpossibles-distancesetforthe...

展开>> 收起<<

Embedding dimensions of matrices whose entries are indefinite distances in the pseudo-Euclidean space Hiroshi NozakiMasashi ShinoharaSho Suda.pdf

共25页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Embedding dimensions of matrices whose entries are indefinite distances in the pseudo-Euclidean space Hiroshi NozakiMasashi ShinoharaSho Suda

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: