Even order uniform hypergraph via the Einstein product

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 $\mathcal{M}$-splitting of tensors by the hypergraph method under the Einstein product.

KEYWORDS:

• Uniform hypergraph
• the Einstein product
• vertex connectivity
• the algebraic connectivity
• $\mathcal{M}$-splitting

AMS CLASSIFICATION:

• 15A18
• 65F15
• 65F10

1 Introduction

Hypergraph is widely used in many applications [7, 8, 27, 35, 36]. 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 [2, 23, 41] and mathematicians [21, 24, 30, 34]. The intention of the hypergraph varies a lot, resulting in various representations and the diverse studies of the hypergraph [14, 40].

The connectivity of the hypergraph is a major concern in the theoretical analysis of the hypergraph. In the graph theory [3], 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 [22] 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 [49]. Their idea is also widely discussed for the hypergraph. There are some matrix based approaches [1, 4]. Hu and Qi [24] represented a 2m-uniform hypergraph as a tensor and utilized H-eigenvalues and Z-eigenvalues [33, 42, 50] to define the algebraic connectivity. Cooper and Dutle [15] 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. [11, 12] 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 [20]. This structure has been widely used in the tensor analysis [6]. 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 $\mathcal{M}$-splitting of a tensor. Schneider [38] 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 $\mathcal{M}$-splitting. Such techniques can be applied to tensors and hypergraphs. We then consider the multiplicity of eigenvalues related to an $\mathcal{M}$-splitting of a tensor using the hypergraph method under the Einstein product.

The main contributions of this paper are listed as follows.

1. 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.

2. We generalize the algebraic connectivity to a directed 2m-uniform hypergraph. We prove the relationship between the vertex connectivity and the algebraic connectivity.

3. We present some results on the eigenvalue multiplicity of $\mathcal{M}$-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 [13, 33, 48]. The order is the number of its indices. A tensor is denoted by calligraphic letters $\mathcal{A},\mathcal{B}$ and so on. Specially, we use $\mathcal{O}$ to represent a zero tensor. An m-th order tensor has the form $\mathcal{A}\in {\mathbb{R}}^{n_1\times n_2\times \cdots \times n_m}$. A square tensor has the same size in all its dimensions: $\mathcal{A}\in {\mathbb{R}}^{n\times \cdots \times n}={\mathbb{R}}^{n^m}$ and is also called an m-th order n-dimensional tensor. An element in the tensor $\mathcal{A}$ is located by an ordered set of indices $\widehat{i}=(i_1,i_2,\dots ,i_m)$ by means of $a_{\widehat{i}}=a_{i_1,i_2,\dots ,i_m}={(\mathcal{A})}_{\widehat{i}}$. In this paper, $\widehat{i}$ is an abbreviation for $(i_1,i_2,\dots ,i_m)$ if the order is clear.

In 1916 [20], Albert Einstein firstly proposed a product “${*}_m$” between two tensors, named the Einstein product.

Definition 2.1.

The Einstein product of tensors $\mathcal{A}\in {\mathbb{R}}^{n_1\times \cdots \times n_k\times p_1\times \cdots \times p_m}$ and $\mathcal{B}\in {\mathbb{R}}^{p_1\times \cdots \times p_m\times q_1\times \cdots \times q_l}$ is a tensor in ${\mathbb{R}}^{n_1\times \cdots \times n_k\times q_1\times \cdots \times q_l}$ such that $${(\mathcal{A}{*}_m\mathcal{B})}_{i_1,\dots ,i_k,j_1,\dots ,j_l}=\sum _{t_1,t_2,\dots ,t_m}{a}_{i_1,\dots ,i_k,t_1,\dots ,t_m}{b}_{t_1,\dots ,t_m,j_1,\dots ,j_l}.$$

For a 2m-th order tensor $\mathcal{A}$, its transpose under the structure of the Einstein product “${*}_m$” is defined as $${({\mathcal{A}}^{\top })}_{i_1,\dots ,i_m,j_1,\dots ,j_m}={(\mathcal{A})}_{j_1,\dots ,j_m,i_1,\dots ,i_m}.$$

The square tensors possess some interesting properties [6]. For 2m-th order n-dimensional tensors, a symmetric tensor is defined as $\mathcal{A}={\mathcal{A}}^{\top }$ and the identity $\mathcal{I}$ can be defined as $${\mathcal{I}}_{\widehat{i},\widehat{j}}=\prod _{k=1}^m{\delta }_{i_k{j}_k},$$where ${\delta }_{i_k{j}_k}$ is the Kronecker delta. The inverse [6] can be defined as $$\mathcal{A}{*}_m{\mathcal{A}}^{-1}={\mathcal{A}}^{-1}{*}_m\mathcal{A}=\mathcal{I}.$$

All the 2m-th order n-dimensional tensors form a ring that is isomorphic to the ring of all the $n^m\times n^m$ matrices; there exists an one to one correspondence between a 2m-th order n-dimensional tensor and an $n^m\times n^m$ 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 [6, 9, 10, 25, 30, 39, 47]. 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 [6, 19, 43–46], “${*}_m$” can be abbreviated as “$*$”.

For a 2m-th order n-dimensional tensor $\mathcal{A}$, its eigenvalue λ and corresponding eigen-tensor $\mathcal{X}\in {\mathbb{R}}^{n^m}$ is defined as $$\mathcal{A}{*}_m\mathcal{X}=\lambda \mathcal{X},\hspace{1em}\mathcal{X}\ne \mathcal{O}.$$

The eigenvalue under the Einstein product is easier to compute than that of the H-eigenvalue and the Z-eigenvalue [17, 31, 33]. Borrowing the concept from matrices, the algebraic multiplicity of an eigenvalue λ of a tensor $\mathcal{A}$ is denoted as ${\text{mult}}_{\lambda }(\mathcal{A})$. The index of eigenvalue λ is defined as [3, 28, 29] $${\text{ind}}_{\lambda }(\mathcal{A})=\arg \underset{{}_k}{\min }\left\{\text{ker}({(\lambda \mathcal{I}-\mathcal{A})}^k)=\text{ker}({(\lambda \mathcal{I}-\mathcal{A})}^{k+1})\right\}.$$

A quadratic form of a tensor $\mathcal{A}$ is defined as ${\mathcal{X}}^{\top }{*}_m\mathcal{A}{*}_m\mathcal{X}$ for $\mathcal{X}\in {\mathbb{R}}^{n^m}$. A tensor is called diagonally dominant, if $$\left|a_{\widehat{i},\widehat{i}}\right|\ge \sum _{\widehat{j}\ne \widehat{i}}\left|a_{\widehat{i},\widehat{j}}\right|$$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 $n^m\times n^m$ matrices to 2m-th order n-dimensional tensors and if two elements have the same indices $\widehat{i}$ (or $\widehat{j}$), then it will be in the same row (or column) after the isomorphism.

2.2 Hypergraph

A hypergraph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ consists of two parts: $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}=\{v_1,v_2,\dots ,v_n\}$ is the set of vertices and $\mathcal{E}=\{E_1,E_2,\dots ,E_t\}$ is the set of hyperedges. A hyperedge $E_i\subseteq \mathcal{V}$ consists of several vertices. A hypergraph is m-uniform if all its hyperedges contain the same number of vertices, i.e., $\left|E_i\right|=m$, for $E_i\in \mathcal{E}$. 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 $E_i=(T_i,H_i)$ is further divided into two parts: the head and the tail [2, 23, 41]. In this paper, we only discuss the 2m-uniform hypergraph. For a directed 2m-uniform hypergraph, we always assume that $\left|H_i\right|=\left|T_i\right|=m$, for $E_i\in \mathcal{E}$.

The idea of a path can be generalized to a hypergraph form. In [34], let $\mathcal{V}=\{1,\dots ,s+t(k-s)\}$, if $(E_1,E_2,\dots ,E_t)$ satisfies $$E_i=\{1+(i-1)(k-s),\dots ,s+i(k-s)\},$$then $(E_1,E_2,\dots ,E_t)$ is an s-path. This definition leads to $$|E_i\cap E_{i+1}|=s,\hspace{1em}i=1,2,\dots ,t-1,$$ and when $s\le m$, $$\hspace{1em}{E}_i\cap E_{i+1}\cap E_{i+2}=\varnothing ,\hspace{1em}i=1,2,\dots ,t-2.$$

Our definition is based on this. An s-path satisfies $$|E_i\cap E_{i+1}|=s,\hspace{1em}i=1,2,\dots ,t-1,$$and $$\hspace{1em}{E}_i\cap E_{i+1}\cap E_{i+2}=\varnothing ,\hspace{1em}i=1,2,\dots ,t-2,$$ 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 $V_1,V_2\subseteq \mathcal{V}$ are s-th path connected if there is an s-path $(E_1,E_2,\dots ,E_t)$ such that V₁ is the subset of the first hyperedge E₁ and V₂ is the subset of the last hyperedge E_t.

The vertex connectivity $v(\mathcal{G})$ is the minimum size of a vertex cut. $$v(\mathcal{G})=\underset{{}_{\widehat{\mathcal{V}}\subseteq \mathcal{V}}}{\min }\left\{\right|\widehat{\mathcal{V}}|:\mathcal{G}(\mathcal{V}\backslash \widehat{\mathcal{V}})\text{is}\text{not}s\text{-connected}\},$$where $\mathcal{G}(\mathcal{V}\backslash \widehat{\mathcal{V}})$ is the sub-hypergraph generated by $\mathcal{V}\backslash \widehat{\mathcal{V}}$, or saying, removing all the vertices in $\widehat{\mathcal{V}}$ and their incident hyperedges from $\mathcal{G}$.

2.3 Adjacency tensor, Laplacian tensor and algebraic connectivity of hypergraph

For an undirected graph $G=(V,E)$ with $\left|V\right|=n$, its adjacency matrix [3] is an n × n matrix $A={(a_{ij})}_{i,j=1}^n$ such that a_ij = 1 if and only if $(i,j)\in E$ and 0 otherwise; its degree matrix is an n × n diagonal matrix $D={(d_{ij})}_{i,j=1}^n$ such that $$d_{ii}=\sum _{j=1}^n{a}_{ij}.$$

Furthermore, the Laplacian matrix of a graph is defined as $$L=D-A.$$

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 [3] of the associated graph. This definition is firstly proposed by [22], 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 $\mathbf{e}={[1,1,\dots ,1]}^{\top }\in {\mathbb{R}}^n$ and $\mathbf{E}=\text{span}\left\{\mathbf{e}\right\}$. As the sum of the row of the Laplacian matrix is 0, the eigenvector corresponding to the smallest eigenvalue 0 is $\mathbf{e}$, i.e., $L\mathbf{e}=\mathbf{0}$. 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. [23] and Wu [49] (1) $$a(G)=\underset{{}_{\begin{array}{c}\left|\right|x|{|}_2=1,\\ x\in {\mathit{E}}^{\perp }\end{array}}}{\min }{x}^{\top }Lx.$$(1)

For undirected graphs with nonnegative weights, $a(G)\ge 0$ 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 [49]. For a real symmetric matrix A of order n, let the eigenvalues of A be arranged as: ${\lambda }_1(A)\le {\lambda }_2(A)\le \cdots \le {\lambda }_n(A)$. It is well known that [49, Lemma 3] $${\lambda }_1\left(\frac{1}{2}\left(L+L^{\top }\right)\right)\le a(G)\le {\lambda }_2\left(\frac{1}{2}\left(L+L^{\top }\right)\right).$$

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 [24]. Li, Qi and Yu [26] proposed another definition of the Laplacian tensor. Later, [51] introduced the signless Laplacian tensor for a uniform hypergraph. In 2014 [32], Qi proposed the simple definitions $$\mathcal{L}=\mathcal{D}-\mathcal{A}$$for the Laplacian tensor and $\mathcal{L}=\mathcal{D}+\mathcal{A}$ 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 [27].

For an undirected 2m-uniform hypergraph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ with n vertices, we define the adjacency tensor $\mathcal{A}\in {\mathbb{R}}^{n^{2m}}$ as follows, $$a_{i_1,\dots ,i_m,i_{m+1},\dots ,i_{2m}}=\{\begin{array}{c}\frac{1}{n^{m-1}}\hspace{1em}\{i_1,i_2,\dots ,i_{2m}\}\in \mathcal{E},\hfill \\ 0\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}\hspace{1em}\text{otherwise}.\hfill \end{array}$$

Some properties hold naturally. For a permutation $\sigma :\{1,2,\dots ,2m\}\to \{1,2,\dots ,2m\}$ we have $$a_{i_1,\dots ,i_m,i_{m+1},\dots ,i_{2m}}=a_{i_{\sigma (1)},\dots ,i_{\sigma (m)},i_{\sigma (m+1)},\dots ,i_{\sigma (2m)}},$$as they correspond to the same hyperedge in $\mathcal{E}$. Therefore the adjacency tensor is permutation-invariant. If there exist unequal t₁ and t₂ such that $i_{t_1}=i_{t_2}$, then $a_{i_1,\dots ,i_m,i_{m+1},\dots ,i_{2m}}=0$ because hyperedges forbid duplicate vertices. However, in Section 5 on the $\mathcal{M}$-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 $\mathcal{D}\in {\mathbb{R}}^{n^{2m}}$ is defined as $$d_{i_1,\dots ,i_m,i_1,\dots ,i_m}=\sum _{j_1,\dots ,j_m=1}^n{a}_{i_1,\dots ,i_m,j_1,\dots ,j_m}$$ and the Laplacian tensor is $\mathcal{L}=\mathcal{D}-\mathcal{A}$.

For a directed 2m-uniform hypergraph, the definition of adjacency tensor is quite similar, $$a_{i_1,\dots ,i_m,i_{m+1},\dots ,i_{2m}}=\frac{1}{n^{m-1}}\iff (\{i_1,\dots ,i_m\},\{i_{m+1},\dots ,i_{2m}\})\in \mathcal{E}.$$

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 $\mathcal{A}$ and $\mathcal{B}$ are two adjacency tensors and $$\mathcal{C}=\mathcal{A}*\mathcal{B},$$then $c_{\widehat{i},\widehat{j}}\ne 0$ if and only if there is an m-path of length 2 from $\widehat{i}$ to $\widehat{j}$, and the first hyperedge belongs to ${\mathcal{G}}_{\mathcal{A}}$ and the second hyperedge belongs to ${\mathcal{G}}_{\mathcal{B}}$.

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 $\mathcal{A}$. Let $\mathbf{E}$ denote the subspace of ${\mathbb{R}}^{n^m}$ spanned by eigen-tensors corresponding to these two situations of 0 eigenvalues:

1. All-one tensor, the same as the all-one eigenvector $\mathbf{e}$ of the eigenvalue 0 in the graph situation.

2. The slice that is all zero due to the duplication in vertex indices.

Then the algebraic connectivity can be defined as follows, (2) $$a(\mathcal{G})=\underset{{}_{\begin{array}{c}\left|\right|\mathcal{X}|{|}_F=1\\ \mathcal{X}\perp \mathit{E}\end{array}}}{\min }{\mathcal{X}}^{\top }*\mathcal{L}*\mathcal{X},$$(2) where $\left|\right|\mathcal{X}|{|}_F$ is the Frobenius norm [33] of the tensor $\mathcal{X}$.

For an undirected hypergraph, $a(\mathcal{G})\ge 0$ as $\mathcal{L}$ 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 $(n^m-\frac{n!}{(n-m)!}+2)$- th smallest eigenvalue of $\mathcal{L}$.

Proof. The algebraic connectivity is an eigenvalue of $\mathcal{L}$ by the Courant–Fischer theorem. We simply count the number of indices $\widehat{i}$ with duplicate indices i_j = i_k ($j\ne k$). In total there are n^m indices, and there are $\frac{n!}{(n-m)!}$ indices with no duplication.

Therefore there are $n^m-\frac{n!}{(n-m)!}$ eigen-tensors in $\mathbf{E}$ corresponding to eigenvalue 0 due to the duplicated vertex indices. Furthermore, the all-one tensor is in $\mathbf{E}$ as the sum of all the elements of $\mathcal{L}$ is 0. Thus there are $n^m-\frac{n!}{(n-m)!}+1$ eigen-tensors in $\mathbf{E}$ corresponding to the eigenvalue 0. Therefore the algebraic connectivity is the $(n^m-\frac{n!}{(n-m)!}+2)$-th smallest eigenvalue of $\mathcal{L}$. □

Theorem 3.2.

If $\mathcal{G}$ is m-connected, i.e., for any $\{i_1,i_2,\dots ,i_m\},\{j_1,j_2,\dots ,j_m\}\subset \mathcal{V}$, there exists an m-path from $\{i_1,i_2,\dots ,i_m\}$ to $\{j_1,j_2,\dots ,j_m\}$, then $a(\mathcal{G})>0$.

Proof.

Consider the quadratic form ${\mathcal{X}}^{\top }*\mathcal{A}*\mathcal{X}=\frac{1}{2}{\displaystyle \sum _{\widehat{i},\widehat{j}}{a}_{\widehat{i},\widehat{j}}}{(x_{\widehat{i}}-x_{\widehat{j}})}^2.$

An m-path $(E_1,E_2,\dots ,E_t)$ indicates that each E_i can be split into two parts: $E_{i-1}\cap E_i$ and $E_i\cap E_{i+1}$; each parts have m vertices and $(E_{i-1}\cap E_i)\cap (E_i\cap E_{i+1})=\varnothing$.

If ${\mathcal{X}}^{\top }*\mathcal{A}*\mathcal{X}=0$, then $\forall x_{i_1,\dots ,i_m}\ne 0$ and $\forall \{i_1,\dots ,i_m,j_1,\dots ,j_m\}\in \mathcal{E}$, $x_{i_1,\dots ,i_m}=x_{j_1,\dots ,j_m}$ holds. As $\mathcal{G}$ is m-connected, i.e., $\forall \{i_1,i_2,\dots ,i_m\},\{j_1,j_2,\dots ,j_m\}\in \mathcal{V}$, there exists an m-path from $\{i_1,i_2,\dots ,i_m\}$ to $\{j_1,j_2,\dots ,j_m\}$, all the values in the path equal to $x_{i_1,\dots ,i_m}$. Therefore $\mathcal{X}=k*\text{ones}(\text{size}(\mathcal{X}))$ where $\text{ones}(\text{size}(\mathcal{X}))$ is all-one tensor with the same order and dimension as $\mathcal{X}$. It means all the elements in $\mathcal{X}$ 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 ${\mathcal{G}}_1=(\mathcal{V},{\mathcal{E}}_1)$, ${\mathcal{G}}_2=(\mathcal{V},{\mathcal{E}}_2)$ and $\mathcal{G}=(\mathcal{V},{\mathcal{E}}_1\cup {\mathcal{E}}_2)$. If ${\mathcal{E}}_1\cap {\mathcal{E}}_2=\varnothing$, then $$a(\mathcal{G})\ge a({\mathcal{G}}_1)+a({\mathcal{G}}_2).$$

Proof.

Let $\mathcal{L},{\mathcal{L}}_1,{\mathcal{L}}_2$ be the Laplacian tensors corresponding to hypergraphs $\mathcal{G},{\mathcal{G}}_1,{\mathcal{G}}_2$, then $$\begin{array}{c}a(\mathcal{G})=\underset{{}_{\mathcal{X}\perp \mathit{E}}}{\min }{\mathcal{X}}^{\top }*\mathcal{L}*\mathcal{X}=\underset{{}_{\mathcal{X}\perp \mathit{E}}}{\min }{\mathcal{X}}^{\top }*({\mathcal{L}}_1+{\mathcal{L}}_2)*\mathcal{X}\\ \ge \underset{{}_{\mathcal{X}\perp \mathit{E}}}{\min }{\mathcal{X}}^{\top }*{\mathcal{L}}_1*\mathcal{X}+\underset{{}_{\mathcal{X}\perp \mathit{E}}}{\min }{\mathcal{X}}^{\top }*{\mathcal{L}}_2*\mathcal{X}\\ =a({\mathcal{G}}_1)+a({\mathcal{G}}_2).\end{array}$$□

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 ${\mathcal{G}}_1=(\mathcal{V},{\mathcal{E}}_1)$ and ${\mathcal{G}}_2=(\mathcal{V},{\mathcal{E}}_2)$, if ${\mathcal{E}}_1\subseteq {\mathcal{E}}_2$, then $a({\mathcal{G}}_1)\le a({\mathcal{G}}_2)$.

Now we move to the relationship between the algebraic connectivity and the vertex connectivity.

Lemma 3.5.

Let $\mathcal{G}$ be a 2m-uniform hypergraph, let ${\mathcal{G}}_1$ arise from removing r vertices and all their incident hyperedges. Then $$a({\mathcal{G}}_1)\ge a(\mathcal{G})-r.$$

Proof.

Let ${\mathcal{G}}_1=(\mathcal{V},{\mathcal{E}}_1)$ arise from removing one vertex from $\mathcal{G}=(\mathcal{V},\mathcal{E})$. Without loss of generality, we assume that the vertex deleted is v_n.

Let $\mathcal{L}$ and ${\mathcal{L}}_1$ be corresponding Laplacian tensors for hypergraphs $\mathcal{G}$ and ${\mathcal{G}}_1$. Suppose that the eigen-tensor of $a({\mathcal{G}}_1)$ is $\mathcal{X}$. Let $\mathcal{Y}\in {\mathbb{R}}^{n^m}$ be such that $$y_{i_1,\dots ,i_m}=x_{i_1,\dots ,i_m}\iff i_t<n,\hspace{1em}t\in \{1,2,\dots ,m\}$$and $y_{i_1,\dots ,i_m}=0$ if $n\in \{i_1,i_2,\dots ,i_m\}$.

Meanwhile, let ${\mathcal{L}}_1=\left\{l_{i_1,i_2,\dots ,i_m,j_1,\dots ,j_m}\right\}$ and construct an auxiliary tensor ${\mathcal{L}}_0=\left\{{\widehat{l}}_{i_1,i_2,\dots ,i_m,j_1,\dots ,j_m}\right\}$. ${\widehat{l}}_{i_1,i_2,\dots ,i_m,j_1,j_2,\dots ,j_m}$ has such form, (3) $$\begin{array}{c}{\widehat{l}}_{i_1,i_2,\dots ,i_m,j_1,j_2,\dots ,j_m}\\ =\{\begin{array}{c}{l}_{\widehat{i},\widehat{j}}\text{if}{i}_t<n\text{and}{j}_t<n,\forall t\in \{1,2,\dots ,n\}\text{and}\widehat{i}\ne \widehat{j}\hfill \\ l_{\widehat{i},\widehat{j}}+1\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}\text{if}{i}_t<n\text{and}{j}_t<n,\forall t\in \{1,2,\dots ,n\}\text{and}\widehat{i}=\widehat{j}\hfill \\ -\frac{1}{n^{m-1}}\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}\text{if}n\in \{i_1,i_2,\dots ,i_m,j_1,j_2,\dots ,j_m\}\text{and}\widehat{i}\ne \widehat{j}\hfill \\ n\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}\hspace{1em}\text{if}n\in \{i_1,i_2,\dots ,i_m,j_1,j_2,\dots ,j_m\}\text{and}\widehat{i}=\widehat{j}.\hfill \end{array}\end{array}$$(3)

We can identify that ${\mathcal{L}}_0$ is symmetric and diagonally dominant and all the diagonal elements are non-negative. The same as Laplacian tensor, ${\mathcal{L}}_0$ satisfies ${\mathcal{L}}_0*\text{ones}(\text{size}(\mathcal{X}))=\mathcal{O}$.

Then for $i_1,i_2,\dots ,i_m$ with $i_t<n,t\in \{1,2,\dots ,m\}$, we have $$\begin{array}{c}{({\mathcal{L}}_0*\mathcal{Y})}_{\widehat{i}}=\sum _{j_1,\dots ,j_m=1}^n{\widehat{l}}_{\widehat{i},\widehat{j}}{y}_{\widehat{j}}\\ =\sum _{j_1,\dots ,j_m=1}^{n-1}{\widehat{l}}_{\widehat{i},\widehat{j}}{y}_{\widehat{j}}+\sum _{n\in \{j_1,\dots ,j_m\}}{\widehat{l}}_{\widehat{i},\widehat{j}}{y}_{\widehat{j}}\\ =\sum _{j_1,\dots ,j_m=1}^{n-1}(l_{\widehat{i},\widehat{j}}+{\delta }_{\widehat{i},\widehat{j}})x_{\widehat{j}}\\ ={({\mathcal{L}}_1*\mathcal{X})}_{\widehat{i}}+x_{\widehat{i}}\\ =(a({\mathcal{G}}_1)+1)x_{\widehat{i}}\\ =(a({\mathcal{G}}_1)+1)y_{\widehat{i}}.\end{array}$$

Otherwise, if $n\in \{i_1,i_2,\dots ,i_m\}$, then $$\begin{array}{c}{({\mathcal{L}}_0*\mathcal{Y})}_{\widehat{i}}=\sum _{j_1,\dots ,j_m=1}^n{\widehat{l}}_{\widehat{i},\widehat{j}}{y}_{\widehat{j}}\\ =\sum _{j_1,\dots ,j_m=1}^{n-1}{\widehat{l}}_{\widehat{i},\widehat{j}}{y}_{\widehat{j}}+\sum _{n\in \{j_1,\dots ,j_m\}}{\widehat{l}}_{\widehat{i},\widehat{j}}{y}_{\widehat{j}}\\ =\sum _{j_1,\dots ,j_m=1}^{n-1}\frac{1}{n^{m-1}}{x}_{\widehat{j}}\\ =\frac{1}{n^{m-1}}\sum _{j_1,\dots ,j_m=1}^{n-1}{x}_{\widehat{j}}\\ =0.\end{array}$$

The last equality is due to the orthogonality between eigen-tensors corresponding to different eigenvalues 0 and $a({\mathcal{G}}_1)$. Therefore ${\mathcal{Y}}^{\top }*{\mathcal{L}}_0*\mathcal{Y}=a({\mathcal{G}}_1)+1$ and $\mathcal{Y}\perp \mathbf{E}$.

From the construction of ${\mathcal{L}}_0$, we can conclude $$\begin{array}{c}{\mathcal{Y}}^{\top }*{\mathcal{L}}_0*\mathcal{Y}=\sum _{\widehat{i}\ne \widehat{j}}{\widehat{l}}_{i_1,\dots ,i_m,j_1,\dots ,i_m}{(y_{i_1,\dots ,i_m}-y_{j_1,\dots ,j_m})}^2\\ \ge \sum _{\widehat{i}\ne \widehat{j}}{l}_{i_1,\dots ,i_m,j_1,\dots ,i_m}{(y_{i_1,\dots ,i_m}-y_{j_1,\dots ,j_m})}^2\\ ={\mathcal{Y}}^{\top }*\mathcal{L}*\mathcal{Y}.\end{array}$$

As a result, we have $$\begin{array}{c}a(\mathcal{G})=\underset{{}_{\begin{array}{c}\left|\right|\mathcal{X}|{|}_F=1\\ \mathcal{X}\perp E\end{array}}}{\min }{\mathcal{X}}^{\top }*\mathcal{L}*\mathcal{X}\le {\mathcal{Y}}^{\top }*\mathcal{L}*\mathcal{Y}\le {\mathcal{Y}}^{\top }*{\mathcal{L}}_0*\mathcal{Y}\\ =a({\mathcal{G}}_1)+1.\end{array}$$

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 $\frac{1}{n^{m-1}}$. This can be improved by a constant. In (3), this leads to the addition ${\widehat{l}}_{\widehat{i},\widehat{i}}=l_{\widehat{i},\widehat{i}}+1$ in the diagonal elements whose indices $\widehat{i}$ does not contain n because $${\widehat{l}}_{\widehat{i},\widehat{i}}=-\sum _{\widehat{j}\ne \widehat{i}}{l}_{\widehat{i},\widehat{j}}=l_{\widehat{i},\widehat{i}}+\sum _{n\in \widehat{j}}\frac{1}{n^{m-1}}=l_{\widehat{i},\widehat{j}}+1.$$

There are exactly $n^{m-1}$ $\frac{1}{n^{m-1}}$ terms in the last summation.

To improve it, we firstly substitute $\frac{1}{n^{m-1}}$ with $\frac{1}{(\begin{array}{c}n-m-1\\ m-1\end{array})m!}=\frac{(n-2m)!}{(n-m-1)!}$ in the definition of adjacency tensor and Laplacian tensor. Furthermore, when constructing ${\mathcal{L}}_0$, let $${\widehat{l}}_{\widehat{i},\widehat{j}}=\{\begin{array}{c}-\frac{(n-2m)!}{(n-m-1)!}\hspace{1em}\text{if}n\in \widehat{i}\cup \widehat{j}\text{and}\widehat{i}\ne \widehat{j}\text{and}\text{no duplicate}\hfill \\ \text{vertices}\text{in}\widehat{i}\cup \widehat{j}\hfill \\ 0\hspace{1em}\text{if}n\in \widehat{i}\cup \widehat{j}\text{and}\widehat{i}\ne \widehat{j}\text{and}\text{existing}\hfill \\ \text{duplicate}\text{vertices}\text{in}\widehat{i}\cup \widehat{j}\hfill \\ -\sum _{\widehat{j}\ne \widehat{i}}{l}_{\widehat{i},\widehat{j}}\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}\text{if}n\in \widehat{i}\cup \widehat{j}\text{and}\widehat{i}=\widehat{j}\hfill \end{array},$$and the other cases are the same as (3). This also leads to a symmetric diagonally dominant ${\mathcal{L}}_0$ and ${\widehat{l}}_{\widehat{i},\widehat{i}}=l_{\widehat{i},\widehat{i}}+1$ as there are exactly $\frac{(n-m-1)!}{(n-2m)!}$ $\frac{(n-2m)!}{(n-m-1)!}$ 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 $\frac{n^{m-1}}{(n-m-1)(n-m-2)\cdots (n-2m+1)}$ 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 $\mathcal{G}=(\mathcal{V},\mathcal{E})$ has a splitting $\mathcal{V}={\mathcal{V}}_1\cup {\mathcal{V}}_2$ and generates the sub-hypergraphs ${\mathcal{G}}_i=({\mathcal{V}}_i,{\mathcal{E}}_i),i=1,2$. Then $$a(\mathcal{G})\le \min \{a({\mathcal{G}}_1)+|{\mathcal{V}}_2|,a({\mathcal{G}}_2)+|{\mathcal{V}}_1\left|\right\}.$$

Theorem 3.7.

For a hypergraph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ we have $$a(\mathcal{G})\le v(\mathcal{G}).$$

Proof.

Suppose $\mathcal{V}={\mathcal{V}}_1\cup {\mathcal{V}}_2$, ${\mathcal{V}}_2\ne \varnothing$ and generates the dis-connected hypergraph ${\mathcal{G}}_2$, it follows from Corollary 3.6 and $a({\mathcal{G}}_2)=0$ that $$a(\mathcal{G})\le \left|{\mathcal{V}}_1\right|+a({\mathcal{G}}_2)=\left|{\mathcal{V}}_1\right|=v(\mathcal{G}).$$□

We use a 4-uniform n-dimensional hypergraph ${\mathcal{K}}_n$ to illustrate our theory. ${\mathcal{K}}_n$ corresponds to a 4th-order n-dimensional tensor. The number of zero eigenvalues due to the duplicate indices is $n^2-n(n-1)$ and the algebraic connectivity is the $(n^2-n(n-1)+2)$-th smallest eigenvalue.

We compute the algebraic connectivity for the complete hypergraph in Table 1.

Table 1 The algebraic connectivity for 4-uniform n-dimensional complete hypergraph.

n	4	5	6	7	8	9	10	11
Algebraic connectivity	0	0.800	1.667	2.571	3.450	4.445	5.400	6.367

Note that a 4-uniform 4-dimensional complete hypergraph is not 2-path connected. Consider $\widehat{i}=\{1,2\}$ and $\widehat{j}=\{1,3\}$, the only hyperedge $\{1,2,3,4\}$ violates $E_i\cap E_{i+1}\cap E_{i+2}=\varnothing$, because $\{1,2\}\cap \{1,2,3,4\}\cap \{1,3\}=\left\{1\right\}\ne \varnothing$. But a 4-uniform 5-dimensional complete hypergraph is 2-path connected, as there are a 2-path $E_1=\{1,2,4,5\},E_2=\{5,4,1,3\}$ connecting $\widehat{i}=\{1,2\}$ and $\widehat{j}=\{1,3\}$. 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 $\mathcal{G}$ satisfies for $S\subseteq \mathcal{V}$, if $\left|S\right|=m$, then $$\left|\right\{E\in \mathcal{E}:E=(S,H)\left\}\right|=\left|\right\{E\in \mathcal{E}:E=(T,S)\left\}\right|.$$

Then the algebraic connectivity is the $(n^m-\frac{n!}{(n-m)!}+2)$th smallest eigenvalue of $\frac{1}{2}(\mathcal{L}+{\mathcal{L}}^{\top })$.

Proof.

We see the fact that $${\mathcal{X}}^{\top }*\mathcal{L}*\mathcal{X}={\mathcal{X}}^{\top }*{\mathcal{L}}^{\top }*\mathcal{X}={\mathcal{X}}^{\top }*\frac{1}{2}(\mathcal{L}+{\mathcal{L}}^{\top })*\mathcal{X}.$$

As $\left|\right\{E\in \mathcal{E}:E=(S,H)\left\}\right|=\left|\right\{E\in \mathcal{E}:E=(T,S)\left\}\right|$, we have $$\mathcal{L}*\text{ones}(\text{size}(\mathcal{X}))=\text{ones}{(\text{size}(\mathcal{X}))}^{\top }*\mathcal{L}=\mathcal{O}.$$

Thus $\frac{1}{2}(\mathcal{L}+{\mathcal{L}}^{\top })$ has the same property as $\mathcal{L}$, 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 ${\mathbf{1}}_{\mathcal{C}}^{\top }*\mathcal{L}*{\mathbf{1}}_{\mathcal{C}}=0$ for the indicator ${\mathbf{1}}_{\mathcal{C}}$ of some connected component $\mathcal{C}$, we have the following theorem.

Theorem 4.2.

If $\mathcal{G}$ is not m-connected, then $a(\mathcal{G})\le 0$.

Lemma 4.3.

Let ${\mathcal{G}}_1=(\mathcal{V},{\mathcal{E}}_1)$, ${\mathcal{G}}_2=(\mathcal{V},{\mathcal{E}}_2)$ and $\mathcal{G}=(\mathcal{V},{\mathcal{E}}_1\cup {\mathcal{E}}_2)$. If ${\mathcal{E}}_1\cap {\mathcal{E}}_2=\varnothing$, then $$a(\mathcal{G})\ge a({\mathcal{G}}_1)+a({\mathcal{G}}_2).$$

The proof is analogous to the case of the undirected hypergraph.

For the directed hypergraph, ${\mathcal{L}}^{\top }=\mathcal{L}$ no longer holds, and the proof of the following lemma is modified.

Lemma 4.4.

Let $\mathcal{G}$ be a 2m-uniform hypergraph, and let ${\mathcal{G}}_1$ arise from removing r vertices and all incident hyperedges. Then $$a({\mathcal{G}}_1)\ge a(\mathcal{G})-r.$$

Proof.

Let ${\mathcal{G}}_1$ be constructed by removing the last vertex v_n from $\mathcal{G}$. Let $\mathcal{L}$ be the Laplacian tensor and $\widehat{\mathcal{L}}$ be the Laplacian tensor of $\mathcal{G}$, then $\widehat{\mathcal{L}}$ and $\mathcal{L}$ have following property, (4) $${\widehat{l}}_{\widehat{i},\widehat{j}}=\{\begin{array}{cc}{l}_{\widehat{i},\widehat{j}}& \text{if}{i}_t<n\text{and}{j}_t<n,\forall t\in \{1,2,\dots ,n\}\text{and}\widehat{i}\ne \widehat{j}\\ l_{\widehat{i},\widehat{j}}+d_{\widehat{i}}& \text{if}{i}_t<n\text{and}{j}_t<n,\forall t\in \{1,2,\dots ,n\}\text{and}\widehat{i}=\widehat{j}\\ -v_{\widehat{i},\widehat{j}}& \text{if}n\notin \{i_1,i_2,\dots ,i_m\}\text{and}n\in \{j_1,j_2,\dots ,j_m\}\\ w_{\widehat{i},\widehat{j}}& \text{if}n\notin \{j_1,j_2,\dots ,j_m\}\text{and}n\in \{i_1,i_2,\dots ,i_m\}\\ z_{\widehat{i},\widehat{j}}& \text{if}n\in \{i_1,i_2,\dots ,i_m,j_1,j_2,\dots ,j_m\}\text{and}\widehat{i}=\widehat{j}.\end{array}$$(4)

In (4), $d_{\widehat{i}}=\sum _{\widehat{j}}{v}_{\widehat{i},\widehat{j}}$ and we use v, w and z to represent the slices of $\widehat{\mathcal{L}}$ of which indices contain n. Define the auxiliary tensor $\mathcal{F}$ as follows, $$f_{\widehat{i},\widehat{j}}=\{\begin{array}{cc}{l}_{\widehat{i},\widehat{j}}& \text{if}{i}_t<n\text{and}{j}_t<n,\forall t\in \{1,2,\dots ,n\}\text{and}\widehat{i}\ne \widehat{j}\\ l_{\widehat{i},\widehat{j}}+1& \text{if}{i}_t<n\text{and}{j}_t<n,\forall t\in \{1,2,\dots ,n\}\text{and}\widehat{i}=\widehat{j}\\ -\frac{1}{n^{m-1}}& \text{if}n\notin \{i_1,i_2,\dots ,i_m\}\text{and}n\in \{j_1,j_2,\dots ,j_m\}\\ w_{\widehat{i},\widehat{j}}-\frac{1}{n^{m-1}}+v_{\widehat{i},\widehat{j}}& \text{if}n\notin \{j_1,j_2,\dots ,j_m\}\text{and}n\in \{i_1,i_2,\dots ,i_m\}\\ z_{\widehat{i}}+n^m-\sum d_{\widehat{i}}& \text{if}n\in \{i_1,i_2,\dots ,i_m,j_1,j_2,\dots ,j_m\}\text{and}\widehat{i}=\widehat{j}.\end{array}$$

Let $\mathcal{Y}=\arg {\min }_{\mathcal{Y}\perp \mathbf{E}}{\mathcal{Y}}^{\top }*\mathcal{L}*\mathcal{Y}$, then $$\begin{array}{c}{(\mathcal{Y}0)}^{\top }*\mathcal{F}*(\mathcal{Y}0)=a({\mathcal{G}}_1)+1\ge \underset{{}_{\mathcal{X}\perp \mathit{E}}}{\min }{\mathcal{X}}^{\top }*\mathcal{F}*\mathcal{X}\\ \ge \underset{{}_{\mathcal{X}\perp \mathit{E}}}{\min }{\mathcal{X}}^{\top }*\mathcal{L}*\mathcal{X}+\underset{{}_{\mathcal{X}\perp \mathit{E}}}{\min }{\mathcal{X}}^{\top }*(\mathcal{F}-\mathcal{L})*\mathcal{X}\\ =a(\mathcal{G})+\underset{{}_{\mathcal{X}\perp \mathit{E}}}{\min }{\mathcal{X}}^{\top }*(\mathcal{F}-\mathcal{L})*\mathcal{X},\end{array}$$where $(\mathcal{Y}0)$ is an informal representation: in the first $(n-1)\times (n-1)\times \cdots \times (n-1)$ hypercube, $(\mathcal{Y}0)$ is the same as $\mathcal{Y}$; the other part is filled with zeros.

Consider the last term $\underset{\mathcal{X}\perp \mathbf{E}}{\min }{\mathcal{X}}^{\top }*(F-\mathcal{L})*\mathcal{X}$. For $\mathcal{F}-\mathcal{L}$ it is symmetric and diagonally dominant and all the diagonal elements are non-negative. As a result, $\underset{\mathcal{X}\perp \mathbf{E}}{\min }{\mathcal{X}}^{\top }*(F-\mathcal{L})*\mathcal{X}\ge 0$. Finally we have $$a({\mathcal{G}}_1)+1\ge a(\mathcal{G}).$$

Using the mathematical induction, the lemma is proved. □

This lemma leads to a corollary immediately.

Corollary 4.5.

Suppose that $\mathcal{G}=(\mathcal{V},\mathcal{E})$ has a splitting $\mathcal{V}={\mathcal{V}}_1\cup {\mathcal{V}}_2$ and generates sub-hypergraphs ${\mathcal{G}}_i=({\mathcal{V}}_i,{\mathcal{E}}_i),i=1,2$. Then $$a(\mathcal{G})\le \min \{a({\mathcal{G}}_1)+|{\mathcal{V}}_2|,a({\mathcal{G}}_2)+|{\mathcal{V}}_1\left|\right\}.$$

Finally the relationship between the algebraic connectivity and the vertex connectivity is proved.

Theorem 4.6.

$a(\mathcal{G})\le v(\mathcal{G})$ holds for a directed hypergraph $\mathcal{G}$.

5 From tensor to hypergraph: $\mathcal{M}$-splitting

We construct a hypergraph from a tensor: ${\mathcal{A}}_{\widehat{i},\widehat{j}}\ne 0$ will lead to a hyperedge $(\widehat{i},\widehat{j})$ and we use $\Gamma (\mathcal{A})$ to represent the hypergraph. Thus some questions of tensor can be solved via the hypergraph approach. A splitting of a tensor $\mathcal{A}$ is $\mathcal{A}=\mathcal{M}-\mathcal{N}$. A $\mathcal{Z}$-tensor $\mathcal{A}$ is $$\mathcal{A}=s\mathcal{I}-\mathcal{P},$$where $\mathcal{I}$ is an identity tensor and $\mathcal{P}$ is nonnegative.

Furthermore, if $s\ge \rho (\mathcal{P})$, where $\rho (\mathcal{P})$ is the spectral radius of $\mathcal{P}$, then $\mathcal{A}$ is an $\mathcal{M}$-tensor [18]. By the Perron-Frobenius theorem [18, 33], that $\mathcal{A}$ is a nonsingular $\mathcal{M}$-tensor is equivalent to $s>\rho (\mathcal{P})$. $\mathcal{A}$ is a singular $\mathcal{M}$-tensor if and only if $s=\rho (\mathcal{P})$.

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 $\widehat{i}$ and $\widehat{j}$, allowing it to be not permutation-invariant. For an m-path $E_1,\dots ,E_t$ with $E_i=(T_i,H_i)$, as we distinguish the order, we ask $H_i=T_{i+1}$ where H_i and $T_{i+1}$ are ordered set.

Let Δ be the hypergraph induced by the identity tensor. The closure $\overline{\Gamma (\mathcal{A})}$ is defined as $$\overline{\Gamma (\mathcal{A})}=\Delta \cup \Gamma (\mathcal{A})\cup \Gamma ({\mathcal{A}}^2)\cup \cdots .$$

If the vertex set $\widehat{i}$ has access to $\widehat{j}$ via an m-path of length k, then ${({\mathcal{A}}^k)}_{\widehat{i},\widehat{j}}>0$. Specially, $\mathcal{A}$ is irreducible if and only if $\Gamma (\mathcal{A})$ is m-connected.

For a splitting $\mathcal{A}=\mathcal{M}-\mathcal{N}$, it is said to be

1. weak regular if ${\mathcal{M}}^{-1}\ge \mathcal{O}$ and ${\mathcal{M}}^{-1}*\mathcal{N}\ge \mathcal{O}$;

2. regular if ${\mathcal{M}}^{-1}\ge \mathcal{O}$ and $\mathcal{N}\ge \mathcal{O}$;

3. an $\mathcal{M}$-splitting if $\mathcal{M}$ is an -tensor and $\mathcal{N}\ge \mathcal{O}$ ;

4. graph compatible if $\Gamma (\mathcal{M})\subseteq \overline{\Gamma (\mathcal{A})}$;

Lemma 5.1.

If $\mathcal{A}=\mathcal{M}-\mathcal{N}$ is an $\mathcal{M}$ -splitting, then $\mathcal{M}$

1. $\mathcal{A}$ is a $\mathcal{Z}$-tensor.

2. $\Gamma (\mathcal{M},\mathcal{N}):=\Gamma (\mathcal{M})\cup \Gamma (\mathcal{N})=\Gamma (\mathcal{A})\cup \Delta$, Δ is the hypergraph derived from the identity tensor.

3. is graph compatible.

4. $\Gamma ({\mathcal{M}}^{-1}*\mathcal{N})=\overline{\Gamma (\mathcal{M})}\Gamma (\mathcal{N})$.

Proof.

As $\mathcal{A}=\mathcal{M}-\mathcal{N}=s\mathcal{I}-\mathcal{P}-\mathcal{N},\mathcal{P}\ge \mathcal{O}$ and $\mathcal{N}\ge \mathcal{O}$, then $\mathcal{P}+\mathcal{N}\ge \mathcal{O}$. For $\widehat{i}\ne \widehat{j},a_{\widehat{i},\widehat{j}}=0$ is equivalent to ${\mathcal{M}}_{\widehat{i},\widehat{j}}={\mathcal{N}}_{\widehat{i},\widehat{j}}=0$. Moreover, ${\mathcal{M}}_{\widehat{i},\widehat{i}}>0$. This leads to Δ and the first three results. For the last result, we just need to prove $\Gamma ({\mathcal{M}}^{-1})\subseteq \overline{\Gamma (\mathcal{M})}$, which is obvious because $${\mathcal{M}}^{-1}={(s\mathcal{I}-\mathcal{P})}^{-1}=\frac{1}{s}\sum _{i=0}^n{(s^{-1}\mathcal{P})}^i$$as $s>\rho (\mathcal{P})$. □

Let the m-path or hyperedge generated from $\Gamma (\mathcal{M})$ be red and the m-path or hyperedge generated from be bl $\Gamma (\mathcal{N})$ ue [38].

Lemma 5.2.

Let $\mathcal{A}=\mathcal{M}-\mathcal{N}$, $\widehat{i}=(i_1,i_2,\dots ,i_m)$ and $\widehat{j}=(j_1,j_2,\dots ,j_m)$. Then $(\widehat{i},\widehat{j})\in \Gamma ({\mathcal{M}}^{-1}*\mathcal{N})$ if and only if in $\Gamma (\mathcal{M})\cup \Gamma (\mathcal{N})$, and there is an m-path starting from $\widehat{i}$ and ending by $\widehat{j}$ with an initial red path followed by a single blue hyperedge.

Proof.

If there is an m-path from $(i_1,i_2,\dots ,i_k)$ to $(j_1,j_2,\dots ,j_k)$ via an initial red path followed by a single blue hyperedge, then there exists $$\begin{array}{c}(i_1,i_2,\dots ,i_m,t_1,t_2,\dots ,t_m)\in \overline{\Gamma (\mathcal{M})},\\ (t_1,t_2,\dots ,t_m,j_1,j_2,\dots ,j_m)\in \overline{\Gamma (\mathcal{N})}.\end{array}$$

Then $(i_1,i_2,\dots ,i_m,j_1,j_2,\dots ,j_m)\in \Gamma ({\mathcal{M}}^{-1}*\mathcal{N})$. The converse is a inference from Lemma 5.1. □

As a result, we can conclude the conclusion.

Theorem 5.3.

Let $\mathcal{A}=\mathcal{M}-\mathcal{N}$ be an $\mathcal{M}$-splitting. Let $\widehat{i},\widehat{j}\subseteq \mathcal{V}$ have m elements. There is a nonempty path from $\widehat{i}$ to $\widehat{j}$ in $\Gamma ({\mathcal{M}}^{-1}*\mathcal{N})$ if and only if there exists an m-path from $\widehat{i}$ to $\widehat{j}$ in $\Gamma (\mathcal{M},\mathcal{N})$ that end in a blue hyperedge.

Proof.

If there exists an m-path from $\widehat{i}$ to $\widehat{j}$ ending with a blue hyperedges in $\Gamma (\mathcal{M},\mathcal{N})$, 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 $\Gamma ({\mathcal{M}}^{-1}*\mathcal{N})=\overline{\Gamma (\mathcal{M})}\Gamma (\mathcal{N})$. The total m-path is a path in $\Gamma ({\mathcal{M}}^{-1}*\mathcal{N})$. 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 [6]. Let $\text{Ext}(·)$ be the map from 2m-th order n-dimensional tensor ring to $n^m\times n^m$ matrix ring and the map from the indices of ordered set in tensor from to the indices of matrices. An index $\widehat{i}=(i_1,i_2,\dots ,i_m)$ is mapped to $\text{Ext}(\widehat{i})=1+{\sum }_{k=1}^m(i_k-1)n^{m-k}$, then $\text{Ext}(\mathcal{A})\in {\mathbb{R}}^{n^m\times n^m}$ can be defined by $${\left(\text{Ext}(\mathcal{A})\right)}_{\text{Ext}(\widehat{i}),\text{Ext}(\widehat{j})}=a_{\widehat{i},\widehat{j}}.$$

$\text{Ext}(·)$ preserves the product operation. Moreover, many properties for eigenvalues, indices, irreducibility and algebraic multiplicity are also preserved.

Lemma 5.4.

Every irreducible singular $\mathcal{M}$-tensor has a simple eigenvalue 0 and its principal sub-tensor is a nonsingular $\mathcal{M}$-tensor.

Proof.

By the definition of a singular $\mathcal{M}$-tensor, $\mathcal{A}=s\mathcal{I}-\mathcal{P}$ with $s=\rho (\mathcal{P})$ and $\mathcal{P}\ge \mathcal{O}$. As $\mathcal{A}$ is irreducible, $\mathcal{P}$ is also irreducible. Then by the Perron-Frobenius theorem [33], $\rho (\mathcal{P})$ is a simple eigenvalue and its eigen-tensor $\mathcal{X}>\mathcal{O}$. Then 0 is a single eigenvalue of $\mathcal{A}$. Similarly, ${\mathcal{A}}^{\top }$ is a singular $\mathcal{M}$-tensor and there exists $\mathcal{Y}>\mathcal{O}$ satisfying ${\mathcal{A}}^{\top }*\mathcal{Y}=\mathcal{O}$. Extend $\mathcal{A}$ to the $n^m\times n^m$ matrix $\text{Ext}(\mathcal{A})$, then the principal sub-tensor corresponds to a principal sub-matrix of $\text{Ext}(\mathcal{A})$ and the adjoint matrix of $\text{Ext}(\mathcal{A})$ has the form [5, Theorem 4.16] $$\text{adj}(\text{Ext}(\mathcal{A}))=\lambda \text{Ext}(\mathcal{X})\text{Ext}{(\mathcal{Y})}^{\top }.$$

As 0 is a simple eigenvalue, $\lambda \ne 0$. If $\lambda <0$, then $\text{adj}(\text{Ext}(\mathcal{A}))<0$. As it is a continuous function of $\mathcal{A}$, there exists $\delta >0$ such that $\text{adj}(\text{Ext}(\mathcal{A}+\delta \mathcal{I}))<0$. However, $\mathcal{A}+\delta \mathcal{I}$ is a nonsingular $\mathcal{M}$-tensor and $\text{Ext}(\mathcal{A}+\delta \mathcal{I})$ is a nonsingular M-matrix. Its inverse is positive, a contradiction. So $\lambda >0$ and therefore $\text{adj}(\text{Ext}(\mathcal{A}))>0$. Specially, all the principal minors of $\text{Ext}(\mathcal{A})$ is positive, which indicate all the principal sub-matrix of $\text{Ext}(\mathcal{A})$ is nonsingular. As a principal sub-tensor of a singular $\mathcal{M}$-tensor corresponds to a principal sub-matrix of $\text{Ext}(\mathcal{A})$, the principle sub-tensor is nonsingular. □

Theorem 5.5.

Suppose $\mathcal{A}\in {\mathbb{R}}^{n^{2m}}$ is an $\mathcal{M}$-tensor, $\mathcal{A}=\mathcal{M}-\mathcal{N}$ is a weak regular splitting.

1. If $\mathcal{A}$ is nonsingular $\mathcal{M}$-tensor, then $\mathcal{B}=\mathcal{I}-{\mathcal{M}}^{-1}*\mathcal{N}$ is also a singular $\mathcal{M}$-tensor and ${\text{ind}}_0(\mathcal{B})=1$.

2. Suppose $\mathcal{A}$ is singular $\mathcal{M}$-tensor. If there exists $\mathcal{X}\in {\mathbb{R}}^{n^m}$ such that $\mathcal{A}*\mathcal{X}\ge \mathcal{O}$, then $\mathcal{B}=\mathcal{I}-{\mathcal{M}}^{-1}*\mathcal{N}$ is also a singular $\mathcal{M}$-tensor and ${\text{ind}}_0(\mathcal{B})=1$.

Proof.

Using the isomorphism $\text{Ext}(·)$, this theorem is the tensor form of Lemmas 4.1 and 4.3 in [38]. □

Let $\mathcal{A}$ be a singular $\mathcal{M}$-tensor. By the Perron-Frobenius theorem [33] the eigen-tensor $\mathcal{X}$ of $\rho (\mathcal{A})$ is positive. It leads to a corollary.

Corollary 5.6.

Suppose $\mathcal{A}\in {\mathbb{R}}^{n^{2m}}$ is an irreducible singular $\mathcal{M}$-tensor, if $\mathcal{A}=\mathcal{M}-\mathcal{N}$ is a weak regular splitting. Then $\mathcal{B}=\mathcal{I}-{\mathcal{M}}^{-1}*\mathcal{N}$ is a singular $\mathcal{M}$-tensor and ${\text{ind}}_0(\mathcal{B})=1$.

Let ${\mathcal{V}}_m$ be the family of all the m elements subsets of $\mathcal{V}$. The strong m-connected relation between the ordered vertex set $\widehat{i}=(i_1,i_2,\dots ,i_m)$ forms an equivalent relationship on the ordered vertex set ${\mathcal{V}}_m$, splitting it into several parts $\mathcal{V}=(V_1,V_2,\dots ,V_c)$. Moreover, the accessibility by an m-path from one part to another forms an order on such partition. If V₁ has access to V₂ and vice versa, then V₁ and V₂ are strongly m-connected and therefore V ₁ = V ₂. If V₁ has access to V₂ and V₂ has access to V₃ then V₁ has access to V₃. We may assume V_k has access to $V_{k+1}$ for all k.

The 2m-th order n-dimensional tensor can be extend to an $n^m\times n^m$ matrix via the isomorphism $\text{Ext}(·)$. Suppose $\mathcal{A}$ is extended to matrix $E(\mathcal{A})$, then $\text{Ext}(V_{t_1})$ and $\text{Ext}(V_{t_2})$ can lead to a sub-matrix $\text{Ext}{(\mathcal{A})}_{t_1,t_2}=\text{Ext}{(\mathcal{A})}_{E(V_{t_1}),E(V_{t_2})}$ from $\text{Ext}(\mathcal{A})$. Suppose $${({\mathcal{A}}_{t_1,t_2})}_{\widehat{i},\widehat{j}}=\{\begin{array}{c}{a}_{\widehat{i},\widehat{j}}\hspace{1em}\widehat{i}\in V_{t_1}\text{and}\widehat{j}\in V_{t_2}\hfill \\ 0\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}\text{otherwise}.\hfill \end{array}$$

If t₁ = t₂ we simply denote them as ${\mathcal{A}}_t$ and $\text{Ext}{(\mathcal{A})}_t$. The eigenvalues of $\text{Ext}{(\mathcal{A})}_t$ and ${\mathcal{A}}_t$ are the same besides some 0 eigenvalues in ${\mathcal{A}}_t$. The 0 eigenvalues result from the indices that are not in V_t lead to a zero slice. When considering the eigenvalues or singularity of ${\mathcal{A}}_t$, 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 [37] to the tensor form. If λ is an eigenvalue of ${\mathcal{A}}_t$, we say V_t is a λ-class. A sequence of λ-class $V_{t_1},V_{t_2},\dots ,V_{t_c}$ such that $V_{t_i}$ has access to $V_{t_{i+1}}$ forms a λ-chain. Use the isomorphism $\text{Ext}(·)$, we can deduce the following theorem.

Theorem 5.7

(Rothblum’s index theorem for a nonnegative tensor). Let $\mathcal{P}\ge \mathcal{O}$ and $\rho =\rho (\mathcal{P})$ be its spectral radius. Then ${\text{ind}}_{\rho }(\mathcal{P})$ equals to the length of the longest λ-path

We check the isomorphism $\text{Ext}(·)$ which preserves eigenvalues with V_t corresponding to the set of vertices.

Theorem 5.8.

Suppose $\mathcal{A}\in {\mathbb{R}}^{n^{2m}}$ is a singular $\mathcal{M}$-tensor, $\mathcal{A}=\mathcal{M}-\mathcal{N}$ is a graph compatible weak-regular splitting, then

1. $\rho ({\mathcal{M}}^{-1}*\mathcal{N})=1$.

2. ${\text{mult}}_1({\mathcal{M}}^{-1}*\mathcal{N})\ge {\text{mult}}_0(\mathcal{A})$.

3. ${\text{ind}}_1({\mathcal{M}}^{-1}*\mathcal{N})\le {\text{ind}}_0(\mathcal{A})$.

These property also holds for the $\mathcal{M}$-splitting.

Proof.

By the partition, ${\mathcal{A}}_{t_1,t_2}=0$ for $t_1>t_2$. As the splitting is graph compatible, ${\mathcal{M}}_{t_1,t_2}=0$ for $t_1>t_2$, therefore ${\mathcal{N}}_{t_1,t_2}=0$ for $t_1>t_2$.

As $\mathcal{A}$ is a singular $\mathcal{M}$-tensor, there is at least one singular ${\mathcal{A}}_t$. For each singular $A_t$, 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 $\mathcal{M}$-tensor. Therefore ${(\mathcal{I}-{\mathcal{M}}^{-1}*\mathcal{N})}_t$ is also a singular $\mathcal{M}$-tensor and the multiplicity of the eigenvalue 0 is 1. For each nonsingular ${\mathcal{A}}_t$, by Theorem 5.5, ${(\mathcal{I}-{\mathcal{M}}^{-1}*\mathcal{N})}_t$ is a nonsingular $\mathcal{M}$-tensor. Therefore $\mathcal{I}-{\mathcal{M}}^{-1}*\mathcal{N}$ is a singular $\mathcal{M}$-tensor. Then $\rho ({\mathcal{M}}^{-1}*\mathcal{N})=1$. The first statement is proved.

Furthermore, every singular sub-tensor ${\mathcal{A}}_t$ adds 1 to the multiplicity of the eigenvalue 0 and also leads to a singular diagonal block inside $\mathcal{I}-{\mathcal{M}}^{-1}*\mathcal{N}$. For a singular diagonal block of $\mathcal{I}-{\mathcal{M}}^{-1}*\mathcal{N}$, the multiplicity of the eigenvalue 0 is equal to the multiplicity of the eigenvalue 1 in tensor ${\mathcal{M}}^{-1}*\mathcal{N}$. The second statement is proved.

Suppose ${\text{ind}}_1(\mathcal{T})=\gamma$. Let $(W_1,W_2,\dots ,W_d)$ be a partition for $\mathcal{T}={\mathcal{M}}^{-1}*\mathcal{N}$. Then $\mathcal{T}\ge \mathcal{O}$. By Rothblum’s index theorem of tensor form, there exists a chain $W_{i_1},W_{i_2},\dots ,W_{i_{\gamma }}$ for the eigenvalue 1. As the splitting is graph compatible, each $W_{i_q}$ is contained in a $V_{i_q}$ and $V_{i_q}$ corresponds to a singular ${\mathcal{A}}_{i_q}$. As $W_{i_{q-1}}$ has access to $W_{i_q}$ in $\Gamma (\mathcal{T})$, such access also holds in $\Gamma (\mathcal{A})$. Therefore $V_{i_{q-1}}$ has access to $V_{i_q}$.

If two $W_{i_q}$ is contained in the same $V_{i_q}$, then by Theorem 5.7, ${\text{ind}}_1(T_{i_q})>1$. Then ${\text{ind}}_1({(\mathcal{I}-{\mathcal{M}}^{-1}*\mathcal{N})}_{i_q})>1$, which is contrary to the fact that ${\text{ind}}_0{(\mathcal{I}-{\mathcal{M}}^{-1}*\mathcal{N})}_{i_q}=1$ for singular blocks. Thus two $W_{i_q}$ cannot be contained in the same V_j. Therefore ${\text{ind}}_1(\mathcal{A})\ge \gamma$. □

Acknowledgments

The authors would like to thank Professor Manjunatha Prasad Karantha and the referee for their detailed comments.

Additional information

Funding

The author Jiaqi Gu would like to acknowledge the support given by the National Natural Science Foundation of China under grant 12271108 and Innovation Program of Shanghai Municipal Education Commission. The author Yimin Wei would like to acknowledge the support given by the National Natural Science Foundation of China under grant 12271108 and Shanghai Municipal Science and Technology Commission under grant 23WZ2501400.