![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
We propose the algebraic connectivity of an undirected 2m-uniform hypergraph under the Einstein product. We generalize the algebraic connectivity to a directed 2m-uniform hypergraph and reveal the relationship between the vertex connectivity and the algebraic connectivity. We present some results on the eigenvalue multiplicity of the -splitting of tensors by the hypergraph method under the Einstein product.
1 Introduction
Hypergraph is widely used in many applications [Citation7, Citation8, Citation27, Citation35, Citation36]. Hypergraph generalizes the concept of edges, and a hyperedge can contain more than two vertices. As a result, the hypergraph model has more flexibility than that of the traditional graph model. The property of the hypergraph is much more complicated than the graph theory, which has attracted attention from both computer scientists [Citation2, Citation23, Citation41] and mathematicians [Citation21, Citation24, Citation30, Citation34]. The intention of the hypergraph varies a lot, resulting in various representations and the diverse studies of the hypergraph [Citation14, Citation40].
The connectivity of the hypergraph is a major concern in the theoretical analysis of the hypergraph. In the graph theory [Citation3], the connectivity of a connected graph can be measured by the edge connectivity and the vertex connectivity. However, computing the edge connectivity and the vertex connectivity are quite difficult. Fiedler [Citation22] proposed the algebraic connectivity and proved the relationship between the algebraic connectivity and the vertex connectivity, made it possible to bound the vertex connectivity on a relatively lower cost. Fiedler’s notion of algebraic connectivity has been generalized to directed graphs [Citation49]. Their idea is also widely discussed for the hypergraph. There are some matrix based approaches [Citation1, Citation4]. Hu and Qi [Citation24] represented a 2m-uniform hypergraph as a tensor and utilized H-eigenvalues and Z-eigenvalues [Citation33, Citation42, Citation50] to define the algebraic connectivity. Cooper and Dutle [Citation15] investigated spectral hypergraph theory via adjacency tensors.
There is a relationship between a graph and its corresponding adjacency matrix, and an m-uniform hypergraph is naturally corresponding to an m-th order n-dimensional tensor. Conversely, for a tensor-based analysis of the hypergraph, the uniform condition is necessary to construct the adjacency tensor. However, as the structures of tensor differ, the definitions of adjacency tensors may also differ. Besides H-eigenvalues and Z-eigenvalues, Chen et al. [Citation11, Citation12] used tensor decomposition to analyze the entropy and the controllability of an m-uniform hypergraph. In this paper, the Einstein product is applied to analyze the adjacency tensor and Laplacian tensor.
The Einstein product is firstly proposed by Nobel laureate Einstein in 1916 [Citation20]. This structure has been widely used in the tensor analysis [Citation6]. The Einstein product has similar properties as the matrix product and is easy to compute. In the structure of the Einstein product, the idea of eigenvalues and quadratic forms can be naturally generalized to the tensor form. Using the Einstein product, we propose the algebraic connectivity of a 2m-uniform hypergraph and reveal the relationship between the algebraic connectivity and the vertex connectivity. Starting from a tensor with the Einstein product, a hypergraph can help us to present results of the -splitting of a tensor. Schneider [Citation38] constructed a graph from a matrix and proved some results about the index and the algebraic multiplicity of eigenvalues of a matrix relevant to an
-splitting. Such techniques can be applied to tensors and hypergraphs. We then consider the multiplicity of eigenvalues related to an
-splitting of a tensor using the hypergraph method under the Einstein product.
The main contributions of this paper are listed as follows.
We propose the algebraic connectivity of an undirected 2m-uniform hypergraph under the Einstein product. We reveal the relationship between the vertex connectivity and the algebraic connectivity, and we enable the algebraic connectivity to serve as a bound of the vertex connectivity.
We generalize the algebraic connectivity to a directed 2m-uniform hypergraph. We prove the relationship between the vertex connectivity and the algebraic connectivity.
We present some results on the eigenvalue multiplicity of
-splitting of tensor using the hypergraph method under the Einstein product.
2 Preliminaries
2.1 Tensor and the Einstein Product
Tensor is a high order generalization of a matrix, and a matrix is called a second order tensor. A tensor is a multidimensional array [Citation13, Citation33, Citation48]. The order is the number of its indices. A tensor is denoted by calligraphic letters and so on. Specially, we use
to represent a zero tensor. An m-th order tensor has the form
. A square tensor has the same size in all its dimensions:
and is also called an m-th order n-dimensional tensor. An element in the tensor
is located by an ordered set of indices
by means of
. In this paper,
is an abbreviation for
if the order is clear.
In 1916 [Citation20], Albert Einstein firstly proposed a product “” between two tensors, named the Einstein product.
Definition 2.1.
The Einstein product of tensors and
is a tensor in
such that
For a 2m-th order tensor , its transpose under the structure of the Einstein product “
” is defined as
The square tensors possess some interesting properties [Citation6]. For 2m-th order n-dimensional tensors, a symmetric tensor is defined as and the identity
can be defined as
where
is the Kronecker delta. The inverse [Citation6] can be defined as
All the 2m-th order n-dimensional tensors form a ring that is isomorphic to the ring of all the matrices; there exists an one to one correspondence between a 2m-th order n-dimensional tensor and an
matrix and many properties, such as the product, the eigenvalue and the eigenvector, inverse and the Moore-Penrose inverse, the Drazin inverse and the Riccati equation can be generalized [Citation6, Citation9, Citation10, Citation25, Citation30, Citation39, Citation47]. Many concepts can be borrowed from matrices, such as the triangular matrix, invertibility, the linear equation and so on. In this paper, we discuss the 2m-th order n-dimensional tensor and its m-th order eigen-tensors or the solutions for multilinear systems [Citation6, Citation19, Citation43–46], “
” can be abbreviated as “
”.
For a 2m-th order n-dimensional tensor , its eigenvalue λ and corresponding eigen-tensor
is defined as
The eigenvalue under the Einstein product is easier to compute than that of the H-eigenvalue and the Z-eigenvalue [Citation17, Citation31, Citation33]. Borrowing the concept from matrices, the algebraic multiplicity of an eigenvalue λ of a tensor is denoted as
. The index of eigenvalue λ is defined as [Citation3, Citation28, Citation29]
A quadratic form of a tensor is defined as
for
. A tensor is called diagonally dominant, if
holds for all its diagonal elements. In the Einstein product, a symmetric diagonally dominant tensor with nonnegative diagonal elements is positive semidefinite because this property is invariant under the transformation from matrices to tensors. The Courant–Fischer theorem [3] also holds for the quadratic form of 2m-th order n-dimensional tensors, as there exists an isomorphism from
matrices to 2m-th order n-dimensional tensors and if two elements have the same indices
(or
), then it will be in the same row (or column) after the isomorphism.
2.2 Hypergraph
A hypergraph consists of two parts:
, where
is the set of vertices and
is the set of hyperedges. A hyperedge
consists of several vertices. A hypergraph is m-uniform if all its hyperedges contain the same number of vertices, i.e.,
, for
. Specially, a graph can be regarded as a 2nd uniform hypergraph.
For an undirected hypergraph, the hyperedge is a set without the order. For a directed hypergraph, its hyperedge is further divided into two parts: the head and the tail [Citation2, Citation23, Citation41]. In this paper, we only discuss the 2m-uniform hypergraph. For a directed 2m-uniform hypergraph, we always assume that
, for
.
The idea of a path can be generalized to a hypergraph form. In [Citation34], let , if
satisfies
then
is an s-path. This definition leads to
and when
,
Our definition is based on this. An s-path satisfies
and
as we only consider
.
Specially, a path in graph theory is a 1-path. We can further define the s-th path connectivity between two sets of vertices. Two sets are s-th path connected if there is an s-path
such that V1 is the subset of the first hyperedge E1 and V2 is the subset of the last hyperedge Et.
The vertex connectivity is the minimum size of a vertex cut.
where
is the sub-hypergraph generated by
, or saying, removing all the vertices in
and their incident hyperedges from
.
2.3 Adjacency tensor, Laplacian tensor and algebraic connectivity of hypergraph
For an undirected graph with
, its adjacency matrix [Citation3] is an n × n matrix
such that aij = 1 if and only if
and 0 otherwise; its degree matrix is an n × n diagonal matrix
such that
Furthermore, the Laplacian matrix of a graph is defined as
There are some basic properties of the Laplacian matrix. As the Laplacian matrix is diagonally dominant and all its diagonal elements are non-negative, it is symmetric positive semi-definite. The smallest eigenvalue is 0, as the sum of its row is 0. The second smallest eigenvalue of a Laplacian matrix is called the algebraic connectivity [Citation3] of the associated graph. This definition is firstly proposed by [Citation22], who displayed some important properties of the algebraic connectivity, especially the relations among the algebraic connectivity, the vertex connectivity and the edge connectivity.
The algebraic connectivity can also be expressed by the Courant–Fischer theorem [3, 22]. Let and
. As the sum of the row of the Laplacian matrix is 0, the eigenvector corresponding to the smallest eigenvalue 0 is
, i.e.,
. According to the Courant–Fischer theorem, for a graph G with the Laplacian matrix L, the algebraic connectivity can be expressed by Gallo et al. [Citation23] and Wu [Citation49]
(1)
(1)
For undirected graphs with nonnegative weights, with the inequality being strict if and only if G is connected. However, for a directed graph, a(G) can be negative as illustrated by the dis-connected graph in Wu [Citation49]. For a real symmetric matrix A of order n, let the eigenvalues of A be arranged as:
. It is well known that [Citation49, Lemma 3]
The adjacency matrix, the Laplacian matrix and the algebraic connectivity can be generalized to the hypergraph. The study of the Laplacian tensor for a uniform hypergraph was explored by Hu and Qi [Citation24]. Li, Qi and Yu [Citation26] proposed another definition of the Laplacian tensor. Later, [Citation51] introduced the signless Laplacian tensor for a uniform hypergraph. In 2014 [Citation32], Qi proposed the simple definitions
for the Laplacian tensor and
for the signless Laplacian tensor, all for a uniform hypergraph. The normalized abstract Laplacian tensor of a weighted hypergraph is investigated by Liu and Wei [Citation27].
For an undirected 2m-uniform hypergraph with n vertices, we define the adjacency tensor
as follows,
Some properties hold naturally. For a permutation we have
as they correspond to the same hyperedge in
. Therefore the adjacency tensor is permutation-invariant. If there exist unequal t1 and t2 such that
, then
because hyperedges forbid duplicate vertices. However, in Section 5 on the
-splitting, we start from the tensor rather than the hypergraph, therefore allowing such duplication and distinguishing the order. This also indicates that in adjacency tensor defined above, there are many redundant slices with all zero elements. The degree tensor
is defined as
and the Laplacian tensor is
.
For a directed 2m-uniform hypergraph, the definition of adjacency tensor is quite similar,
The following definition of the Laplacian tensor is the same.
For a 2m-uniform hypergraph and the corresponding 2m-th order n-dimensional adjacency tensor, the definition of the m-path is compatible with the adjacency tensor under the Einstein product. Suppose that and
are two adjacency tensors and
then
if and only if there is an m-path of length 2 from
to
, and the first hyperedge belongs to
and the second hyperedge belongs to
.
The definition of the adjacency tensor carries much more redundancy than the adjacency matrix and these redundancy remains in the Laplacian tensor. In the definition of the hypergraph, a hyperedge has no duplicate vertices. In the adjacency tensor, the duplication of the indices leads to a zero slice in . Let
denote the subspace of
spanned by eigen-tensors corresponding to these two situations of 0 eigenvalues:
All-one tensor, the same as the all-one eigenvector
of the eigenvalue 0 in the graph situation.
The slice that is all zero due to the duplication in vertex indices.
Then the algebraic connectivity can be defined as follows,
(2)
(2) where
is the Frobenius norm [Citation33] of the tensor
.
For an undirected hypergraph, as
is weakly diagonally dominant and symmetric and all the diagonal elements are non-negative. For a directed hypergraph, the definition of algebraic connectivity is the same as (2).
3 Undirected 2m-uniform Graph
Lemma 3.1.
The algebraic connectivity is the - th smallest eigenvalue of
.
Proof. The algebraic connectivity is an eigenvalue of by the Courant–Fischer theorem. We simply count the number of indices
with duplicate indices ij = ik (
). In total there are nm indices, and there are
indices with no duplication.
Therefore there are eigen-tensors in
corresponding to eigenvalue 0 due to the duplicated vertex indices. Furthermore, the all-one tensor is in
as the sum of all the elements of
is 0. Thus there are
eigen-tensors in
corresponding to the eigenvalue 0. Therefore the algebraic connectivity is the
-th smallest eigenvalue of
. □
Theorem 3.2.
If is m-connected, i.e., for any
, there exists an m-path from
to
, then
.
Proof.
Consider the quadratic form
An m-path indicates that each Ei can be split into two parts:
and
; each parts have m vertices and
.
If , then
and
,
holds. As
is m-connected, i.e.,
, there exists an m-path from
to
, all the values in the path equal to
. Therefore
where
is all-one tensor with the same order and dimension as
. It means all the elements in
are a constant k. □
Theorem 3.2 shows that algebraic connectivity can distinguish the m-connected hypergraph from dis-connected one. Further, we move on to the order property of the algebraic connectivity.
Lemma 3.3.
Let ,
and
. If
, then
Proof.
Let be the Laplacian tensors corresponding to hypergraphs
, then
□
Using the non-negative property of the algebraic connectivity for the undirected hypergraph and Lemma 3.3, Corollary 3.4 holds.
Corollary 3.4.
Let and
, if
, then
.
Now we move to the relationship between the algebraic connectivity and the vertex connectivity.
Lemma 3.5.
Let be a 2m-uniform hypergraph, let
arise from removing r vertices and all their incident hyperedges. Then
Proof.
Let arise from removing one vertex from
. Without loss of generality, we assume that the vertex deleted is vn.
Let and
be corresponding Laplacian tensors for hypergraphs
and
. Suppose that the eigen-tensor of
is
. Let
be such that
and
if
.
Meanwhile, let and construct an auxiliary tensor
.
has such form,
(3)
(3)
We can identify that is symmetric and diagonally dominant and all the diagonal elements are non-negative. The same as Laplacian tensor,
satisfies
.
Then for with
, we have
Otherwise, if , then
The last equality is due to the orthogonality between eigen-tensors corresponding to different eigenvalues 0 and . Therefore
and
.
From the construction of , we can conclude
As a result, we have
The remaining part of the proof follows by mathematical induction on r. As the loss of algebraic connectivity is at most 1 on the removal of 1 vertex, the lemma is easy to prove. □
In the definition of the adjacency tensor and Laplacian tensor, the coefficient of a hyperedge is . This can be improved by a constant. In (3), this leads to the addition
in the diagonal elements whose indices
does not contain n because
There are exactly
terms in the last summation.
To improve it, we firstly substitute with
in the definition of adjacency tensor and Laplacian tensor. Furthermore, when constructing
, let
and the other cases are the same as (3). This also leads to a symmetric diagonally dominant
and
as there are exactly
terms this time. The other cases follow similarly. In this way, we can also prove Lemma 3.5 and the relationship between the algebraic connectivity and the vertex connectivity. The algebraic connectivity is
times larger and therefore serves as a better lower bound. However, when m is much smaller than n, the ratio is nearly 1, then we may retain the former definition for succinctness.Corollary 3.6 follows immediately from Lemma 3.5.
Corollary 3.6.
Suppose that has a splitting
and generates the sub-hypergraphs
. Then
Theorem 3.7.
For a hypergraph we have
Proof.
Suppose ,
and generates the dis-connected hypergraph
, it follows from Corollary 3.6 and
that
□
We use a 4-uniform n-dimensional hypergraph to illustrate our theory.
corresponds to a 4th-order n-dimensional tensor. The number of zero eigenvalues due to the duplicate indices is
and the algebraic connectivity is the
-th smallest eigenvalue.
We compute the algebraic connectivity for the complete hypergraph in .
Table 1 The algebraic connectivity for 4-uniform n-dimensional complete hypergraph.
Note that a 4-uniform 4-dimensional complete hypergraph is not 2-path connected. Consider and
, the only hyperedge
violates
, because
. But a 4-uniform 5-dimensional complete hypergraph is 2-path connected, as there are a 2-path
connecting
and
. Thus the vertex connectivity of 4-uniform n-dimensional hypergraph is n – 4. The result supports our theory.
4 Directed 2m-uniform graph
The exploration on eigenvalues need an additional condition for directed hypergraphs.
Lemma 4.1.
Assume that a directed hypergraph satisfies for
, if
, then
Then the algebraic connectivity is the th smallest eigenvalue of
.
Proof.
We see the fact that
As , we have
Thus has the same property as
, the Laplacian tensor of an undirected 2m-uniform hypergraph in Lemma 3.1. The remaining proof is similar. □
For an arbitrary directed hypergraph, the positive semi-definite property no longer holds. Using the fact that for the indicator
of some connected component
, we have the following theorem.
Theorem 4.2.
If is not m-connected, then
.
Lemma 4.3.
Let ,
and
. If
, then
The proof is analogous to the case of the undirected hypergraph.
For the directed hypergraph, no longer holds, and the proof of the following lemma is modified.
Lemma 4.4.
Let be a 2m-uniform hypergraph, and let
arise from removing r vertices and all incident hyperedges. Then
Proof.
Let be constructed by removing the last vertex vn from
. Let
be the Laplacian tensor and
be the Laplacian tensor of
, then
and
have following property,
(4)
(4)
In (4), and we use v, w and z to represent the slices of
of which indices contain n. Define the auxiliary tensor
as follows,
Let , then
where
is an informal representation: in the first
hypercube,
is the same as
; the other part is filled with zeros.
Consider the last term . For
it is symmetric and diagonally dominant and all the diagonal elements are non-negative. As a result,
. Finally we have
Using the mathematical induction, the lemma is proved. □
This lemma leads to a corollary immediately.
Corollary 4.5.
Suppose that has a splitting
and generates sub-hypergraphs
. Then
Finally the relationship between the algebraic connectivity and the vertex connectivity is proved.
Theorem 4.6.
holds for a directed hypergraph
.
5 From tensor to hypergraph: ![](//:0)
-splitting
We construct a hypergraph from a tensor: will lead to a hyperedge
and we use
to represent the hypergraph. Thus some questions of tensor can be solved via the hypergraph approach. A splitting of a tensor
is
. A
-tensor
is
where
is an identity tensor and
is nonnegative.
Furthermore, if , where
is the spectral radius of
, then
is an
-tensor [Citation18]. By the Perron-Frobenius theorem [18, 33], that
is a nonsingular
-tensor is equivalent to
.
is a singular
-tensor if and only if
.
In this case, as we start from tensors rather than hypergraphs, the duplication of the indices is not prohibited. Moreover, we distinguish the order of indices inside and
, allowing it to be not permutation-invariant. For an m-path
with
, as we distinguish the order, we ask
where Hi and
are ordered set.
Let Δ be the hypergraph induced by the identity tensor. The closure is defined as
If the vertex set has access to
via an m-path of length k, then
. Specially,
is irreducible if and only if
is m-connected.
For a splitting , it is said to be
weak regular if
and
;
regular if
and
;
an
-splitting if
is an -tensor and
;
graph compatible if
;
Lemma 5.1.
If
is an
-splitting, then
is a
-tensor.
, Δ is the hypergraph derived from the identity tensor.
is graph compatible.
.
Proof.
As and
, then
. For
is equivalent to
. Moreover,
. This leads to Δ and the first three results. For the last result, we just need to prove
, which is obvious because
as
. □
Let the m-path or hyperedge generated from be red and the m-path or hyperedge generated from be bl
ue [Citation38].
Lemma 5.2.
Let ,
and
. Then
if and only if in
, and there is an m-path starting from
and ending by
with an initial red path followed by a single blue hyperedge.
Proof.
If there is an m-path from to
via an initial red path followed by a single blue hyperedge, then there exists
Then . The converse is a inference from Lemma 5.1. □
As a result, we can conclude the conclusion.
Theorem 5.3.
Let be an
-splitting. Let
have m elements. There is a nonempty path from
to
in
if and only if there exists an m-path from
to
in
that end in a blue hyperedge.
Proof.
If there exists an m-path from to
ending with a blue hyperedges in
, then the path can be split by all its blue hyperedges. Each partition is a path starting with a red path and ending with a blue hyperedges, therefore the hyperedge that consists of the endpoints of this part belongs to
. The total m-path is a path in
. The converse is from Lemma 5.1. □
We further consider the index and algebraic multiplicity of the tensor derived from a splitting. It is necessary to build the isomorphism from tensor to matrix [Citation6]. Let be the map from 2m-th order n-dimensional tensor ring to
matrix ring and the map from the indices of ordered set in tensor from to the indices of matrices. An index
is mapped to
, then
can be defined by
preserves the product operation. Moreover, many properties for eigenvalues, indices, irreducibility and algebraic multiplicity are also preserved.
Lemma 5.4.
Every irreducible singular -tensor has a simple eigenvalue 0 and its principal sub-tensor is a nonsingular
-tensor.
Proof.
By the definition of a singular -tensor,
with
and
. As
is irreducible,
is also irreducible. Then by the Perron-Frobenius theorem [33],
is a simple eigenvalue and its eigen-tensor
. Then 0 is a single eigenvalue of
. Similarly,
is a singular
-tensor and there exists
satisfying
. Extend
to the
matrix
, then the principal sub-tensor corresponds to a principal sub-matrix of
and the adjoint matrix of
has the form [Citation5, Theorem 4.16]
As 0 is a simple eigenvalue, . If
, then
. As it is a continuous function of
, there exists
such that
. However,
is a nonsingular
-tensor and
is a nonsingular M-matrix. Its inverse is positive, a contradiction. So
and therefore
. Specially, all the principal minors of
is positive, which indicate all the principal sub-matrix of
is nonsingular. As a principal sub-tensor of a singular
-tensor corresponds to a principal sub-matrix of
, the principle sub-tensor is nonsingular. □
Theorem 5.5.
Suppose is an
-tensor,
is a weak regular splitting.
If
is nonsingular
-tensor, then
is also a singular
-tensor and
.
Suppose
is singular
-tensor. If there exists
such that
, then
is also a singular
-tensor and
.
Proof.
Using the isomorphism , this theorem is the tensor form of Lemmas 4.1 and 4.3 in [Citation38]. □
Let be a singular
-tensor. By the Perron-Frobenius theorem [33] the eigen-tensor
of
is positive. It leads to a corollary.
Corollary 5.6.
Suppose is an irreducible singular
-tensor, if
is a weak regular splitting. Then
is a singular
-tensor and
.
Let be the family of all the m elements subsets of
. The strong m-connected relation between the ordered vertex set
forms an equivalent relationship on the ordered vertex set
, splitting it into several parts
. Moreover, the accessibility by an m-path from one part to another forms an order on such partition. If V1 has access to V2 and vice versa, then V1 and V2 are strongly m-connected and therefore V 1 = V 2. If V1 has access to V2 and V2 has access to V3 then V1 has access to V3. We may assume Vk has access to
for all k.
The 2m-th order n-dimensional tensor can be extend to an matrix via the isomorphism
. Suppose
is extended to matrix
, then
and
can lead to a sub-matrix
from
. Suppose
If t1 = t2 we simply denote them as and
. The eigenvalues of
and
are the same besides some 0 eigenvalues in
. The 0 eigenvalues result from the indices that are not in Vt lead to a zero slice. When considering the eigenvalues or singularity of
, we omit these 0 eigenvalues and only consider the inherent eigenvalues.
This partition makes it possible to generalize Rothblum’s index theorem for a nonnegative matrix [Citation37] to the tensor form. If λ is an eigenvalue of , we say Vt is a λ-class. A sequence of λ-class
such that
has access to
forms a λ-chain. Use the isomorphism
, we can deduce the following theorem.
Theorem 5.7
(Rothblum’s index theorem for a nonnegative tensor). Let and
be its spectral radius. Then
equals to the length of the longest λ-path
We check the isomorphism which preserves eigenvalues with Vt corresponding to the set of vertices.
Theorem 5.8.
Suppose is a singular
-tensor,
is a graph compatible weak-regular splitting, then
.
.
.
These property also holds for the -splitting.
Proof.
By the partition, for
. As the splitting is graph compatible,
for
, therefore
for
.
As is a singular
-tensor, there is at least one singular
. For each singular
, by definition being irreducible, it follows from Lemma 5.4 that the algebraic multiplicity of the eigenvalue 0 is 1; from Corollary 5.6 it is an
-tensor. Therefore
is also a singular
-tensor and the multiplicity of the eigenvalue 0 is 1. For each nonsingular
, by Theorem 5.5,
is a nonsingular
-tensor. Therefore
is a singular
-tensor. Then
. The first statement is proved.
Furthermore, every singular sub-tensor adds 1 to the multiplicity of the eigenvalue 0 and also leads to a singular diagonal block inside
. For a singular diagonal block of
, the multiplicity of the eigenvalue 0 is equal to the multiplicity of the eigenvalue 1 in tensor
. The second statement is proved.
Suppose . Let
be a partition for
. Then
. By Rothblum’s index theorem of tensor form, there exists a chain
for the eigenvalue 1. As the splitting is graph compatible, each
is contained in a
and
corresponds to a singular
. As
has access to
in
, such access also holds in
. Therefore
has access to
.
If two is contained in the same
, then by Theorem 5.7,
. Then
, which is contrary to the fact that
for singular blocks. Thus two
cannot be contained in the same Vj. Therefore
. □
Acknowledgments
The authors would like to thank Professor Manjunatha Prasad Karantha and the referee for their detailed comments.
Additional information
Funding
References
- Asadi, M. M., Khosravi, M., Aghdam, A. G., Blouin, S. (2016). “Generalized Algebraic Connectivity for Asymmetric Networks. In: 2016 American Control Conference (ACC), pp. 5531–5536.
- Ausiello, G., Laura, L. (2016). Directed hypergraphs: Introduction and fundamental algorithms—a survey. Theor. Comput. Sci. 658: 293–306.
- Bapat, R. B. (2010). Graphs and Matrices, Vol. 27. London: Springer.
- Barik, S., Pati, S. (2005). On algebraic connectivity and spectral integral variations of graphs. Linear Algebra Appl. 397(2): 209–222.
- Berman, A., Plemmons, R. J. (1994). Nonnegative Matrices in the Mathematical Sciences. Philadelphia, PA: Society for Industrial and Applied Mathematics.
- Brazell, M., Li, N., Navasca, C., Tamon, C. (2013). Solving multilinear systems via tensor inversion. SIAM J. Matrix Anal. Appl. 34(2): 542–570.
- Chang, J., Chen, Y., Qi, L. (2016). Computing eigenvalues of large scale sparse tensors arising from a hypergraph. SIAM J. Sci. Comput. 38(6): A3618–A3643.
- Chang, J., Chen, Y., Qi, L., Yan, H. (2020). Hypergraph clustering using a new laplacian tensor with applications in image processing. SIAM J. Imaging Sci. 13(3): 1157–1178.
- Chang, S. Y., Wei, Y. (2022). General tail bounds for random tensors summation: majorization approach. J. Comput. Appl. Math. 416: 114533.
- Chang, S. Y., Wei, Y. (2022). Sherman-Morrison-Woodbury identity for tensors. Pac. J. Optim. 18(1): 27–53.
- Chen, C., Surana, A., Bloch, A. M., Rajapakse, I. (2021). Controllability of hypergraphs. IEEE Trans. Netw. Sci. Eng. 8(2): 1646–1657.
- Chen, C., Rajapakse, I. (2020). Tensor entropy for uniform hypergraphs. IEEE Trans. Netw. Sci. Eng. 7(4): 2889–2900.
- Che, M., Wei, Y. (2020). Theory and Computation of Complex Tensors and its Applications. Singapore: Springer.
- Chowdhury, S., Needham, T, Semrad, E., Wang, B., Zhou, Y. (2021). Hypergraph co-optimal transport: Metric and categorical properties. arXiv preprint arXiv:2112.03904.
- Cooper, J., Dutle, A. (2012). Spectra of uniform hypergraphs. Linear Algebra Appl. 436(9): 3268–3292.
- Ding, W., Qi, L., Wei, Y. (2013). M-tensors and nonsingular M-tensors. Linear Algebra Appl. 439(10): 3264–3278.
- Ding, W., Wei, Y. (2015). Generalized tensor eigenvalue problems. SIAM J. Matrix Anal. Appl. 36(3): 1073–1099.
- Ding, W., Qi, L., Wei, Y. (2013). M-tensors and nonsingular M-tensors. Linear Algebra Appl. 439(10): 3264–3278.
- Ding, W., Wei, Y. (2016). Solving multi-linear systems with M M-tensors. J. Sci. Comput. 68(2): 689–715.
- Einstein, A. (1916). Die grundlage der allgemeinen relativitätstheorie. Ann. Phys. 49: 769–822.
- Feng, K., Li, W.-C. W. (1996). Spectra of hypergraphs and applications. J. Number Theory 60(1): 1–22.
- Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak Math. J. 23(98): 298–305.
- Gallo, G., Longo, G., Pallottino, S., Nguyen, S. (1993). Directed hypergraphs and applications. Discrete Appl. Math. 42(2–3): 177–201.
- Hu, S., Qi, L. (2012). Algebraic connectivity of an even uniform hypergraph. J. Comb. Optim. 24(4): 564–579.
- Ji, J., Wei, Y. (2018). The Drazin inverse of an even-order tensor and its application to singular tensor equations. Comput. Math. Appl. 75(9): 3402–3413.
- Li, G., Qi, L., Yu, G. (2013). The Z-eigenvalues of a symmetric tensor and its application to spectral hypergraph theory. Numerical Linear Algebra Appl. 20(6): 1001–1029.
- Liu, T., Wei, Y. (2022). The abstract Laplacian tensor of a hypergraph with applications in clustering. J. Sci. Comput. 93(1): Article 7.
- Miao, Y., Qi, L., Wei, Y. (2020). Generalized tensor function via the tensor singular value decomposition based on the T-product. Linear Algebra Appl. 590: 258–303.
- Miao, Y., Qi, L., Wei, Y. (2021). T-Jordan canonical form and T-Drazin inverse based on the T-product. Commun. Appl. Math. Comput. 3(2): 201–220.
- Miao, Y., Wei, Y., Chen, Z. (2022). Fourth-order tensor Riccati equations with the Einstein product. Linear Multilinear Algebra 70(10): 1831–1853.
- Mo, C., Wang, X., Wei, Y. (2020). Time-varying generalized tensor eigenanalysis via Zhang neural networks. Neurocomputing 407: 465–479.
- Qi, L. (2014). H +-eigenvalues of laplacian and signless laplacian tensors. Commun. Math. Sci. 12(6): 1045–1064.
- Qi, L., Luo, Z. (2017). Tensor Analysis: Spectral Theory and Special Tensors. Philadelphia, PA: Society for Industrial and Applied Mathematics.
- Qi, L., J.-Y. Shao, Wang, Q. (2014). Regular uniform hypergraphs, s-cycles, s-paths and their largest Laplacian H-eigenvalues. Linear Algebra Appl. 443: 215–227.
- Rota Bulò, S., Pelillo, M. (2013). A game-theoretic framework for similarity-based data clustering. IEEE Trans Pattern Anal. Mach. Intell. 35: 1312–1327.
- Rota Bulò, S., Pelillo, M. (2009). A generalization of the Motzkin–Straus theorem to hypergraphs. Optim. Lett. 3(2): 287–295.
- Rothblum, U. G. (1975). Algebraic eigenspaces of nonnegative matrices. Linear Algebra Appl. 12(3): 281–292.
- Schneider, H. (1984). Theorems on M-splittings of a singular M-matrix which depend on graph structure. Linear Algebra Appl. 58: 407–424.
- Sun, L., Zheng, B., Bu, C., Wei, Y. (2016). Moore–Penrose inverse of tensors via Einstein product. Linear Multilinear Algebra 64(4): 686–698.
- Tudisco, F., Higham, D. J. (2022). Core-periphery detection in hypergraphs. SIAM J. Math. Data Science 5(2023): 1–21.
- Volpentesta, A. P. 2008. Hypernetworks in a directed hypergraph. Eur. J. Oper. Res. 188(2): 390–405.
- Wan, J.-C., Wang, Y., Hu, F.-T. (2022). Spectra of weighted uniform hypertrees. Electron. J. Comb. 29(2): P2–40.
- Wang, X., Mo, C., Qiao, S., Wei, Y. (2022). Predefined-time convergent neural networks for solving the time-varying nonsingular multi-linear tensor equations. Neurocomputing 472: 68–84.
- Wang, X., Che, M., Mo, C., Wei, Y. (2023). Solving the system of nonsingular tensor equations via randomized Kaczmarz-like method. J. Comput. Appl. Math. 421: 114856.
- Wang, X., Che, M., Wei, Y. (2020). Neural network approach for solving nonsingular multi-linear tensor systems. J. Comput. Appl. Math. 368: 112569.
- Wang, X., Che, M., Wei, Y. (2022). Randomized Kaczmarz methods for tensor complementarity problems. Comput. Optim. Appl. 82(3): 595–615.
- Wang, Y., Wei, Y. (2022). Generalized eigenvalue for even order tensors via Einstein product and its applications in multilinear control systems. Comput. Appl. Math. 41(2022): Paper No. 419.
- Wei, Y., Ding, W. (2016). Theory and Computation of Tensors: Multi-Dimensional Arrays. New York: Academic Press.
- Wu, C. W. 2005. Algebraic connectivity of directed graphs. Linear Multilinear Algebra 53(3): 203–223.
- Xie, J., Qi, L. (2016). Spectral directed hypergraph theory via tensors. Linear Multilinear Algebra 64(4): 780–794.
- Xie, J., Chang, A. (2013). On the Z-eigenvalues of the adjacency tensors for uniform hypergraphs. Linear Algebra Appl. 439(8): 2195–2204.