1. Introduction
The class of associative algebras generated by idempotents has many interesting properties. For example, a simple algebra
${\cal A}$
over a field
${\mathbb F}$
with
${\mathrm {{char~}}{\mathbb F}\neq 2}$
belongs to this class if
${\cal A}$
contains at least one nontrivial idempotent. This follows from a more general result about invariant subalgebras due to Amitsur [Reference Amitsur1, Theorem 2]. A self-contained proof was given by Brešar [Reference Brešar2, Section 2]. Laffey [Reference Laffey11] showed that a noncommutative simple algebra generated by two idempotents is always isomorphic to the algebra of
$2\times 2$
matrices over a simple extension of the ground field.
The structure of not necessarily simple algebras generated by two idempotents was described by Weiss [Reference Weiss, Curto and Jørgensen19] and Rowen and Segev [Reference Rowen and Segev15]. Kawai [Reference Kawai6] proved that a commutative algebra over an algebraically closed field is generated by idempotents if and only if it is a homomorphic image of a group algebra with certain properties. Brešar [Reference Brešar3] showed that a finite-dimensional algebra is zero product determined if and only if it can be generated by idempotents. Hu and Xiao [Reference Hu and Xiao5] obtained a homological description of finite-dimensional algebras generated by idempotents. Algebras generated by two quadratic elements were described by Drensky et al. [Reference Drensky, Szigeti and van Wyk4]. Similar problems have been investigated successfully in functional analysis for Banach algebras including
$C^*$
-algebras (see [Reference Krupnik, Roch and Silbermann10, Reference Roch, Santos, Silbermann, Roch, Santos and Silbermann14, Reference Shchukin, Vatkina, Gaşpar, Timotin, Zsidó, Gohberg and Vasilescu16, Reference Weiss, Curto and Jørgensen19]).
If we know that an algebra is generated by a finite set of idempotents, it is a natural task to determine its minimum cardinality. This quantity will be denoted by
$\nu $
. Laffey [Reference Laffey11] proved that
$\nu \leq 3$
for the
${\mathbb F}$
-algebra of
$n\times n$
matrices
$M_n(D)$
, where D is a finite-dimensional division
${\mathbb F}$
-algebra and its centre
$Z(D)$
is a separable extension of the field
${\mathbb F}$
. Krupnik [Reference Krupnik9] calculated
$\nu $
precisely for
$M_n({\mathbb F})$
. Kelarev et al. [Reference Kelarev, van der Merwe and van Wyk7] determined
$\nu $
for the algebra of upper-triangular matrices over a commutative ring. This result was generalised in [Reference van der Merwe and van Wyk18] to complete block triangular matrix algebras over an infinite field.
Throughout the paper,
${\cal R}$
is a commutative associative ring with the identity
${1\neq 0}$
. A subalgebra
${\cal A}$
of the matrix algebra
$M_n({\cal R})$
is called a structural matrix algebra if it has a basis of some matrix units
$E_{ij}$
as an
${\cal R}$
-module and all diagonal matrix units
$\{E_{ii}\}_{i=1}^n$
belong to this basis. If additionally no two symmetric matrix units
$E_{ij}$
,
$E_{ji}$
are in this basis simultaneously,
${\cal A}$
is called an incidence algebra. Then the set of all such pairs
$(i,j)$
for which
$E_{ij}$
belongs to the basis is a partial order
$\boldsymbol {\preceq }$
on the set
${{\cal N} = \{1,\ldots ,n\}}$
. Conversely, for any partial order
$\boldsymbol {\preceq }$
on
${\cal N}$
, all possible
${\cal R}$
-linear combinations of the matrices
$\{E_{ij}\mid i\boldsymbol {\preceq } j\}$
constitute an incidence algebra
$$ \begin{align*}{{\cal A}_n(\boldsymbol{\preceq},{\cal R})}=\bigg\lbrace \sum_{i\boldsymbol{\preceq} j}r_{ij}E_{ij}: r_{ij}\in{\cal R}\bigg\rbrace \subseteq M_n({\cal R}).\end{align*} $$
For example, if one takes the standard linear order
$\leq $
, the corresponding incidence algebra will be the algebra of all upper-triangular matrices
$T_n({\cal R})$
. In contrast, if
${\boldsymbol {\preceq }}$
is the trivial partial order (equality), then
${\cal A}_n(=,{\cal R})$
coincides with the algebra of all diagonal matrices
$D_n({\cal R})$
.
According to [Reference Kelarev, van der Merwe and van Wyk7], the minimum number of idempotent generators
$\nu $
of
$T_n({\cal R})$
equals
$\lceil \log _2 n\rceil $
in almost all cases. The exceptional cases are
$n=2,3,4$
, when
${\nu = \lceil \log _2 n\rceil +1}$
. We will generalise this result to all incidence algebras of finite posets. In other words, the following problem will be considered.
Problem 1.1. Given an incidence algebra
${\cal A}$
of a finite poset over a unital commutative ring
${\cal R}$
, find the minimum number
$\nu $
of idempotent matrices which generate
${\cal A}$
as a unital
${\cal R}$
-algebra.
The solution to this problem is obtained in Theorem 5.6. It turns out that again
$\nu $
equals either
$\lceil \log _2 n\rceil $
or
$\lceil \log _2 n\rceil +1$
, but delimitation between these two cases is more complicated. It relies on embedding the Hasse diagram of the poset into the complement of a hypercube graph. In the particular case of
$\nu (T_n({\cal R}))$
, the choice between the two formulae can be interpreted in terms of the existence of a Hamiltonian path in a certain graph (see the proof of Corollary 5.7).
The paper is organised as follows. In Section 2, necessary definitions and known results are given. In Section 3, it is shown that given idempotent generators of an incidence algebra, the Hasse diagram of the poset can be embedded in the complement of a hypercube graph. Conversely, Section 4 is devoted to a construction of idempotent generators when the Hasse diagram is represented as a subgraph of the complement of a hypercube. In Section 5, the solution to Problem 1.1 is obtained in Theorem 5.6. To formulate this result, new types of graphs are introduced in Definition 5.3.
2. Preliminaries
Let
${\cal A}$
be an associative
${\cal R}$
-algebra with the identity
$1_{\cal A}$
. A subset
$S{~\subseteq ~}{\cal A}$
is said to generate
${\cal A}$
as a unital ring if any element
$a\in {\cal A}$
can be represented as a sum of some products of elements from the set
$S\cup \{1_{\cal A}\}$
, that is,
$a = \sum _{i=1}^n s_{i,1}\cdot s_{i,2}\cdot \,\cdots \,\cdot s_{i,k_i}$
, where
$s_{i,j}\in S\cup \{1_{\cal A}\}$
, some of the
$s_{i,j}$
may coincide and
$k_i\in {\mathbb N}$
. We denote
${\cal R} 1_{\cal A} = \{r\cdot 1_{\cal A}\mid r\in {\cal R}\}$
. A subset
$S{~\subseteq ~}{\cal A}$
generates
${\cal A}$
as a unital algebra if
${\cal A}$
can be generated by
${S\cup {\cal R} 1_{\cal A}}$
as a unital ring. Generators of incidence algebras over finite posets were described in [Reference Longstaff and Rosenthal13, Theorem] and [Reference Kolegov8, Theorem 1.1].
Consider a partial order
$\boldsymbol {\preceq }$
on
${\cal N}=\{1,\ldots ,n\}$
and a bijection
$\sigma :{\cal N}\rightarrow {\cal N}$
. Then we can introduce a new partial order
$\boldsymbol {\preceq }_\sigma $
given by
$i\boldsymbol {\preceq }_\sigma j$
whenever
$\sigma ^{-1}(i)\boldsymbol {\preceq }\sigma ^{-1}(j)$
. So the posets
$({\cal N},\boldsymbol {\preceq })$
and
$({\cal N}, \boldsymbol {\preceq }_\sigma )$
are isomorphic.
Proposition 2.1 [Reference Spiegel and O’Donnell17, Proposition 1.2.7], [Reference Kolegov8, Section 2].
For any incidence algebra
${{\cal A}_n(\boldsymbol {\preceq },{\cal R})}$
, there exists a bijection
$\sigma :{\cal N}\rightarrow {\cal N}$
such that
${{\cal A}_n(\boldsymbol {\preceq }_\sigma ,{\cal R})}{~\subseteq ~} T_n({\cal R})$
. Moreover,
${{\cal A}_n(\boldsymbol {\preceq }_\sigma ,{\cal R})} = P^{-1}{{\cal A}_n(\boldsymbol {\preceq },{\cal R})} P$
, where
$(P)_{ij} = 1$
if
$j = \sigma (i)$
and
$(P)_{ij} = 0$
otherwise.
If
$i\boldsymbol {\prec } j$
and there is no k such that
$i\boldsymbol {\prec } k\boldsymbol {\prec } j$
, then j is said to cover i. This relation will be denoted by
$i\boldsymbol {\prec :} j$
. The definition of an incidence algebra implies the following result.
Lemma 2.2. Let
$A,B\in {{\cal A}_n(\boldsymbol {\preceq },{\cal R})}$
and
$i\boldsymbol {\prec :}j$
. Then
$(AB)_{ij}=(A)_{ii}(B)_{ij}+(A)_{ij}(B)_{jj}$
.
For an incidence algebra
${\cal A}={{\cal A}_n(\boldsymbol {\preceq },{\cal R})}$
, we denote by
$$ \begin{align*}{\cal Z} ={\cal Z}({\cal A}) = \{A\in{\cal A}\mid (A)_{ii} = 0,~i=1,\ldots,n\},\end{align*} $$
the set of matrices with zero diagonals. By Proposition 2.1,
${\cal Z}$
is a two-sided ideal. Let
${\cal Z}^k$
be the set of all possible sums of products
$A_{i_1}\cdot \,\cdots \, \cdot A_{i_m}$
for any
$m\leq k$
and all (possibly repeating) matrices
$A_{i_j}\in {\cal Z}$
. We have
${\cal Z}^n = (O_n)$
since
$P^{-1} {\cal Z}({\cal A}) P{~\subseteq ~} {\cal Z}(T_n({\cal R}))$
by Proposition 2.1.
Consider the ideal
${\cal Z}^2$
. Lemma 2.2 implies that
$(A)_{ij} = 0$
for all
$i\boldsymbol {\prec :} j$
and any
${A\in {\cal Z}^2}$
. Conversely, for any
$i,j\in {\cal N}$
satisfying
$i\boldsymbol {\prec } j$
and
$i\boldsymbol {\not \prec :} j$
, one may find a chain
${i = i_1\boldsymbol {\prec :} i_2\boldsymbol {\prec :}\cdots \boldsymbol {\prec :} i_k = j}$
of length
$k\geq 3$
and so
$E_{ij} = E_{i_1 i_2}\cdot (E_{i_2 i_3}\cdot \,\cdots \,\cdot E_{i_{k-1}i_k})$
belongs to
${\cal Z}^2$
. It follows that
$$ \begin{align} {\cal Z}^2 = \{A\in{\cal Z}({\cal A})\mid (A)_{ij}=0 \text{ for all } i\boldsymbol{\prec:}j\}. \end{align} $$
The word ‘graph’ will mean an undirected graph without loops and multiple edges, that is, a pair
$G=(V,E)$
with sets of vertices V and edges E; each edge is a set of two distinct vertices. A graph is complete if any two of its vertices are joined by an edge. Given an arbitrary graph G and any complete subgraph
$G'$
, the set of vertices of
$G'$
is called a clique. Each clique with the maximum number of vertices is said to be a maximum clique and its cardinality is the clique number
$\omega = \omega (G)$
of the graph G.
The complement
$\overline {G} = (V, \overline {E})$
of G is the graph with the same set of vertices V such that for all
$x,y\in V$
, we have
$\{x,y\}\in \overline {E}$
if and only if
$\{x,y\}\not \in E$
. Thus,
$E\cap \overline {E}=\varnothing $
and
$(V,E\cup \overline {E})$
is a complete graph.
For a partial order
$\boldsymbol {\preceq }$
on
${\cal N} = \{1,\ldots ,n\}$
, the (undirected) Hasse diagram is the graph with the set of vertices
${\cal N}$
such that
$x,y\in {\cal N}$
are joined by an edge if and only if either
$x\boldsymbol {\prec :}y$
or
$y\boldsymbol {\prec :}x$
.
Given
$m\in {\mathbb N}$
, then
$\{0,1\}^m$
denotes the set of all possible
$2^m$
tuples of zeros and ones of length m. We will denote by
${\cal Q}_m$
the m-hypercube graph. Its set of vertices is
$\{0,1\}^m$
. Two tuples are joined by an edge if and only if they differ in precisely one coordinate. So two tuples are joined in
$\overline {{\cal Q}_m}$
if and only if they differ at least in two coordinates.
Proposition 2.3 (Folklore).
The graph
$\overline {{\cal Q}_m}$
has the following properties:
-
(1) each vertex of
$\overline {{\cal Q}_m}$
has degree
$2^{m}-m-1$
; -
(2) the clique number
$\omega (\overline {{\cal Q}_m}) = 2^{m-1}$
; -
(3) there are exactly two maximum cliques
$C_0, C_1$
in
$\overline {{\cal Q}_m}$
; -
(4) each vertex from
$C_0$
is joined precisely to
$2^{m-1}-m$
vertices from
$C_1$
and vice versa; -
(5) for
$m=1,2$
, the graph
$\overline {{\cal Q}_m}$
is disconnected; if
$m\geq 3$
, there exists a Hamiltonian cycle in
$\overline {{\cal Q}_m}$
, that is, a cycle that visits each vertex precisely once (except for the starting vertex, which it visits twice); -
(6) the graph
$\overline {{\cal Q}_m}$
is naturally isomorphic to a subgraph of
$\overline {{\cal Q}_{m+1}}$
.
Proof. (1) Any vertex of the m-hypercube has degree m.
(2)–(4) Let
$C_0$
and
$C_1$
be the sets of all tuples that contain even and odd numbers of ones, respectively. Then
$|C_0| = |C_1| = 2^{m-1}$
. Two tuples with the same parity of the number of ones are joined in
$\overline {{\cal Q}_m}$
and so
$C_0$
and
$C_1$
are indeed cliques.
Let
$\upsilon $
be a vertex in
$C_0$
, then
$\deg \upsilon - (|C_0| -1) = 2^{m}-m-1 - 2^{m-1}+1 = 2^{m-1}-m$
, that is,
$\upsilon $
is joined to
$2^{m-1}-m$
vertices from
$C_1$
. The symmetric property holds for any
$\upsilon \in C_1$
. This proves item (4).
Consider an arbitrary clique C in
$\overline {{\cal Q}_m}$
. The union
$C_0\cup C_1$
contains all vertices of the graph. If
$C{~\subseteq ~} C_0$
or
$C{~\subseteq ~} C_1$
, then clearly
$|C|\leq 2^{m-1}$
. Assume that
$C\cap C_0\neq \varnothing $
and
$C\cap C_1\neq \varnothing $
. Then
$|C|\leq 2^{m-1}-m$
according to item (4). Thus,
$C_0,C_1$
are maximum cliques. For the same reasons, they are the only maximum cliques in
$\overline {{\cal Q}_m}$
. This proves items (2) and (3).
(5) The graph
$\overline {{\cal Q}_1}$
consists of two isolated vertices, while
$\overline {{\cal Q}_2}$
is the union of two segments. Let
$m\geq 3$
. We set
$\upsilon = (0\ldots 0000)$
,
$\upsilon ' = (0\ldots 0110)$
,
$w = (0\ldots 0111)$
,
$w' = (0\ldots 0001)$
. A possible cycle starts at
$\upsilon $
, visits each vertex of
$C_0$
and finishes at
$\upsilon '$
. After that, it comes to
$w'$
, visits all vertices of
$C_1$
and finishes at w. Eventually, the cycle returns to
$\upsilon $
.
(6) An embedding sends a tuple
$(a_1\ldots a_m)$
to
$(a_1 \ldots a_m 0)$
for all
$a_i\in \{0,1\}$
.
3. A construction of an embedding of the Hasse diagram
Given idempotent matrices which generate an incidence algebra, it will be shown that the Hasse diagram of the poset is isomorphic to a subgraph of the complement of a hypercube. We assume first in the proof that the base ring
${\cal R}$
is a field and then we turn to the general case.
Lemma 3.1. Consider an incidence algebra
${\cal A} = {{\cal A}_n(\boldsymbol {\preceq },{\cal R})}$
. Let
${\cal A}$
be generated by distinct idempotent matrices
$A_1,\ldots ,A_u$
as a unital
${\cal R}$
-algebra for some
$u\in {\mathbb N}$
. Then the Hasse diagram of
$\boldsymbol {\preceq }$
is isomorphic to a subgraph of the complement
$\overline {{\cal Q}_m}$
of the m-hypercube for any
$m\geq u$
.
Proof
Case 1. Assume that
${\cal R} = {\mathbb F}$
is a field. If
$m=1$
, then
$u=1$
, and the linear span of the identity matrix
$I_n$
and
$A_1$
coincides with
${\cal A}$
. Hence,
$\dim {\cal A}\leq 2$
, and we have either
$n=1$
or
$n=2$
and
${\cal A} = D_2({\mathbb F})$
. In these cases, the Hasse diagram consists of one or two isolated points and so it can be embedded in
$\overline {{\cal Q}_1}$
. Henceforth, we shall assume that
$m\geq 2$
.
Consider the tuple of matrices
$(A_1,\ldots ,A_m)$
, where
$A_{u+1} = A_1,\ldots , A_m = A_1$
. Proposition 2.1 implies that there is no loss of generality in assuming that
${\cal A}\subseteq T_n({\cal R})$
and so all the matrices
$A_1,\ldots ,A_m$
are upper-triangular. Since they are idempotent, their diagonal entries must be idempotent elements of the field
${\mathbb F}$
. So the tuple
$((A_1)_{ii},\ldots , (A_m)_{ii})$
belongs to
$\{0,1\}^m$
for any
$i \in {\cal N}=\{1,\ldots ,n\}$
. Consider the map
$f:{\cal N}\longrightarrow \{0,1\}^m$
given by
$f(i)=((A_1)_{ii},\ldots , (A_m)_{ii})$
. Item
$1$
of [Reference Longstaff and Rosenthal13, Theorem] guarantees that f is injective.
We will show that f is an embedding of the Hasse diagram into the graph
$\overline {{\cal Q}_m}$
. Assume in contrast that there exists a pair
$i_*\boldsymbol {\prec :} j_*$
such that the tuples
$f(i_*)$
and
$f(j_*)$
differ exactly in one position. In other words, one can find
$k_*\in \{1,\ldots ,m\}$
such that
$(A_{k_*})_{i_*i_*}\neq (A_{k_*})_{j_*j_*}$
, but for any
$k\in \{1,\ldots ,m\}\setminus \{k_*\}$
, we have
$(A_k)_{i_*i_*} = (A_k)_{j_*j_*}$
.
Since
$A_k^2 = A_k$
and
$i_*\boldsymbol {\prec :}j_*$
, Lemma 2.2 implies
${(1-(A_k)_{i_*i_*} - (A_k)_{j_*j_*})\cdot (A_k)_{i_*j_*}=0}$
. When
$k\neq k_{*}$
, the entries
$(A_k)_{i_*i_*}$
and
$(A_k)_{j_*j_*}$
are equal and belong to
$\{0,1\}$
. Consequently,
$1-(A_k)_{i_*i_*} - (A_k)_{j_*j_*}\neq 0$
and we have
$(A_k)_{i_*j_*}=0$
for any
$k\neq k_{*}$
.
Item
$2$
of [Reference Longstaff and Rosenthal13, Theorem] implies that there exists B in the linear span
$\langle A_1,\ldots ,A_m\rangle$
such that
$(B)_{i_* j_*}\neq 0$
and
$(B)_{i_* i_*} = (B)_{j_*j_*}$
. We can write
$B = \lambda _1 A_1+\cdots +\lambda _m A_m$
for some
$\lambda _1,\ldots ,\lambda _m$
from
${\mathbb F}$
. Then at least one of the matrices
$A_1,\ldots ,A_m$
must have a nonzero
$i_*,j_*$
-entry. The only possibility is that
$(A_{k_{*}})_{i_*j_*}\neq 0$
and
$\lambda _{k_*}\neq 0$
. Then
$$ \begin{align*}(B)_{i_*i_*} - (B)_{j_*j_*} = \sum_{k=1}^m\lambda_k( (A_k)_{i_*i_*}-(A_k)_{j_*j_*}) = \lambda_{k_*} ((A_{k_*})_{i_*i_*} - (A_{k_*})_{j_*j_*} )\neq 0.\end{align*} $$
This contradicts the requirement that
$(B)_{i_*i_*} = (B)_{j_*j_*}$
.
Case 2. Let
${\cal R}$
be an arbitrary unital commutative ring. Consider a maximal ideal
${\mathfrak {m}}\lhd {\cal R}$
and the residue field
${\mathbb F} = {\cal R}/{\mathfrak {m}}$
. Let
$\pi :{\cal R}\rightarrow {\cal R}/{\mathfrak {m}}$
be the natural projection. We construct the surjective ring homomorphism
$\pi _n: {{\cal A}_n(\boldsymbol {\preceq },{\cal R})}\rightarrow {{\cal A}_n(\boldsymbol {\preceq },{\mathbb F})}$
given by
$(\pi _n(A))_{ij} = \pi ((A)_{ij})$
for all
$i,j=1,\ldots ,n$
. Note that
$\pi _n$
preserves scalar matrices, that is,
$\pi _n({\cal R} I_n) = {\mathbb F} I_n$
.
Consider the matrices
$\pi _n(A_1),\ldots ,\pi _n(A_u)$
. Though some of them may coincide, there is no loss of generality to assume that
$\pi _n(A_1),\ldots ,\pi _n(A_{u'})$
are all possible pairwise distinct matrices and
$u'\leq u$
. Since the set
$\{A_1,\ldots ,A_u\}\cup {\cal R} I_n$
generates
${{\cal A}_n(\boldsymbol {\preceq },{\cal R})}$
as a ring, the image
$\{\pi _n(A_1),\ldots ,\pi _n(A_{u'})\}\cup {\mathbb F} I_n$
generates
${\cal A}_n(\boldsymbol {\preceq },{\mathbb F})$
as a ring. Thus,
${{\cal A}_n(\boldsymbol {\preceq },{\mathbb F})}$
is generated by idempotents
$\pi _n(A_1),\ldots ,\pi _n(A_{u'})$
as a unital
${\mathbb F}$
-algebra. According to Case 1, the Hasse diagram of
$\boldsymbol {\preceq }$
is isomorphic to a subgraph of
$\overline {{\cal Q}_m}$
for all
$m\geq u'$
. In particular, we may take any
$m\geq u$
.
4. A construction of idempotent generators
The following lemma demonstrates how to obtain idempotent matrices that generate the incidence algebra when we have an embedding of the Hasse diagram into the complement of a hypercube.
Lemma 4.1. Let the set
${\cal N} = \{1,\ldots ,n\}$
be partially ordered by a relation
$\boldsymbol {\preceq }$
. Assume that the Hasse diagram of
$\boldsymbol {\preceq }$
is isomorphic to a subgraph of
$\overline {{\cal Q}_m}$
. Then there exists a natural number
$u\leq m$
such that the incidence algebra
${\cal A} = {\cal A}_n(\boldsymbol {\preceq },{\cal R})$
can be generated by some distinct idempotent matrices
$A_1,\ldots ,A_u$
.
Proof. Let
$f:{\cal N}\longrightarrow \{0,1\}^m$
be an embedding of the Hasse diagram into the graph
$\overline {{\cal Q}_m}$
. Given
$i\in {\cal N}$
, then
$f(i)=(a^{(i)}_1,\ldots , a^{(i)}_m)$
for some
$a^{(i)}_{k}\in \{0,1\}$
. The definition of
$\overline {{\cal Q}_m}$
implies that for any pair
$i\boldsymbol {\prec :} j$
, there exist indices
$\eta \neq \theta $
such that
$a^{(i)}_{\eta }\neq a^{(j)}_{\eta }$
and
${a^{(i)}_{\theta }\neq a^{(j)}_{\theta }}$
. So we may consider
$\eta = \eta (i,j)$
and
$\theta = \theta (i,j)$
as functions of pairs
$i\boldsymbol {\prec :}j$
.
Proposition 2.1 guarantees that there is no loss of generality in assuming that all matrices of
${\cal A}$
are upper-triangular. For any
$k=1,\ldots ,m$
, we introduce the matrix
$$ \begin{align*} (\widetilde{A}_k)_{ij}= \begin{cases} a^{(i)}_{k} & \mbox{if } i=j; \\ 1 & \mbox{if } i\boldsymbol{\prec:} j \mbox{ and } \eta(i,j)=k; \\ 0 & \mbox{otherwise}. \end{cases} \end{align*} $$
Let
$\widetilde {S}$
be the set of these matrices. Note that
$\widetilde {S}{~\subseteq ~} {\cal A}$
. We need to show that
$\widetilde {S}$
generates
${\cal A}$
as a unital
${\cal R}$
-algebra. Conditions A, B of [Reference Kolegov8, Theorem 1.1] must be checked.
Since the map f is an embedding, it is injective. So for any pair
$i\neq j$
, the tuples
$(a^{(i)}_1,\ldots , a^{(i)}_m)$
and
$(a^{(j)}_1,\ldots , a^{(j)}_m)$
are distinct, that is, there exists an index
$\xi =\xi (i,j)$
such that
$a^{(i)}_\xi \neq a^{(j)}_\xi $
. Therefore,
$(\widetilde {A}_\xi )_{ii} - (\widetilde {A}_\xi )_{jj} =\pm 1$
and Condition A of [Reference Kolegov8, Theorem 1.1] holds since
$1\in {\mathfrak {a}}_{ij}(\widetilde {S})$
.
Consider a pair
$i\boldsymbol {\prec :} j$
. Let
$\eta = \eta (i,j)$
and
$\theta = \theta (i,j)$
. Then
$$ \begin{align*}\begin{pmatrix} (\widetilde{A}_\eta)_{ii}& (\widetilde{A}_\eta)_{ij}\\ 0 & (\widetilde{A}_\eta)_{jj} \end{pmatrix} = \begin{pmatrix} x & 1 \\ 0 & 1-x \end{pmatrix}, \quad \begin{pmatrix} (\widetilde{A}_\theta)_{ii}& (\widetilde{A}_\theta)_{ij}\\ 0 & (\widetilde{A}_\theta)_{jj} \end{pmatrix} = \begin{pmatrix} y & 0 \\ 0 & 1-y \end{pmatrix}\end{align*} $$
for some
$x,y\in \{0,1\}{~\subseteq ~}{\cal R}$
. We set
$$ \begin{align*} \widetilde{B}=\begin{cases} \widetilde{A}_\eta+\widetilde{A}_\theta & \mbox{if } x\neq y, \\ \widetilde{A}_\eta- \widetilde{A}_\theta+I_n & \mbox{if } x=y. \end{cases} \end{align*} $$
Consequently,
$$ \begin{align*}\begin{pmatrix} (\widetilde{B})_{ii}& (\widetilde{B})_{ij}\\ 0 & (\widetilde{B})_{jj} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}.\end{align*} $$
Then Condition B of [Reference Kolegov8, Theorem 1.1] is satisfied since
$1\in {\mathfrak {b}}_{ij}(\widetilde {S})$
.
Thus, [Reference Kolegov8, Theorem 1.1] guarantees that the set
$\widetilde {S}$
generates
${\cal A}$
as a unital
${\cal R}$
-algebra. However, the matrices
$\widetilde {A}_1,\ldots , \widetilde {A}_m$
are not necessarily idempotent. We need to ‘slightly’ change their entries to make them idempotent generators.
Consider the ideal
${\cal Z}^2$
from (2.1). Let
$\pi :{\cal A}\rightarrow {\cal A}/{\cal Z}^2$
be the natural projection onto the quotient algebra
${\cal A}/{\cal Z}^2$
. We will prove that
$\pi (\widetilde {A}^2_k - \widetilde {A}_k )=0$
for any
$k = 1,\ldots ,m$
. Since the matrices are triangular and their diagonals contain only zeros and ones, we have
$(\widetilde {A}^2_k)_{ii} - (\widetilde {A}_k)_{ii} =0$
for all
$i\in {\cal N}$
. Fix a pair
$i\boldsymbol {\prec :} j$
. If
$(\widetilde {A}_k)_{ij} =0$
, then
$(\widetilde {A}^2_k)_{ij} =0$
by Lemma 2.2. In the case
$(\widetilde {A}_k)_{ij} =1$
, we have
$k = \eta (i,j)$
and so
$(\widetilde {A}_k)_{ii} \neq (\widetilde {A}_k)_{jj}$
. Then one of the entries
$(\widetilde {A}_k)_{ii}$
,
$(\widetilde {A}_k)_{jj}$
equals 1 and the other equals 0. By Lemma 2.2, it follows that
$(\widetilde {A}^2_k)_{ij} =1$
. Thus, we have shown that
$\widetilde {A}^2_k - \widetilde {A}_k \in {\cal Z}^2$
, which is equivalent to
$\pi (\widetilde {A}^2_k - \widetilde {A}_k )=0$
.
Since
$\pi $
is an algebra homomorphism, we obtain
$\pi (\widetilde {A}_k)^2 = \pi (\widetilde {A}_k)$
, that is, all the images
$\pi (\widetilde {A}_1),\ldots ,\pi (\widetilde {A}_m)$
are idempotents in the algebra
${\cal A}/{\cal Z}^2$
. It is known that idempotents can be lifted modulo a nil ideal [Reference Lambek12, Section 3.6, Proposition 1]. Hence, there exist matrices
$A_1,\ldots ,A_m$
from
${\cal A}$
such that
$A_k^2 = A_k$
and
$\pi (A_k )=\pi (\widetilde {A}_k)$
for all
$k=1,\ldots ,n$
. Let S denote the set of these matrices.
We will prove that S generates
${\cal A}$
as a unital
${\cal R}$
-algebra. Since
$A_k -\widetilde {A}_k\in {\cal Z}^2$
for any
$k=1,\ldots ,m$
, we have
$(A_k)_{ii} = (\widetilde {A}_k)_{ii}$
for all
$i\in {\cal N}$
and
$(A_k)_{ij} = (\widetilde {A}_k)_{ij}$
for all pairs
$i\boldsymbol {\prec :}j$
. Then
${\mathfrak {a}}_{ij}(S) = {\mathfrak {a}}_{ij}(\widetilde {S})={\cal R}$
and
${\mathfrak {b}}_{ij}(S) = {\mathfrak {b}}_{ij}(\widetilde {S})={\cal R}$
in the terms of [Reference Kolegov8, Theorem 1.1]. Therefore, S generates
${\cal A}$
as a unital
${\cal R}$
-algebra.
It remains to note that the matrices
$A_1,\ldots ,A_m$
are not necessarily pairwise distinct. So we may choose some
$u\in {\mathbb N}$
distinct matrices among
$A_1,\ldots ,A_m$
as required in the lemma.
5. The main result
In this section, we provide the solution to Problem 1.1 in Theorem 5.6. Before doing that, we need to unite the results from two previous sections in one theorem.
Theorem 5.1. Consider an incidence algebra
${\cal A} = {{\cal A}_n(\boldsymbol {\preceq },{\cal R})}$
. Then the Hasse diagram of
$\boldsymbol {\preceq }$
is isomorphic to a subgraph of the complement
$\overline {{\cal Q}_m}$
of an m-hypercube if and only if there exists
$u\in \{1,\ldots ,m\}$
such that
${\cal A}$
can be generated by some distinct idempotent matrices
$A_1,\ldots ,A_u$
.
Proof. The implication
$(\Rightarrow )$
is given by Lemma 4.1, while the inverse
$(\Leftarrow )$
follows from Lemma 3.1.
Hence, we need to consider subgraphs of
$\overline {{\cal Q}_m}$
. The following lemma imposes restrictions on the possible number of vertices in such a subgraph.
Lemma 5.2. Consider an arbitrary graph G on n vertices and the complement
$\overline {{\cal Q}_m}$
of an m-hypercube. If
$m< \lceil \log _2 n\rceil $
, there are no subgraphs of
$\overline {{\cal Q}_m}$
isomorphic to G. When
$m = \lceil \log _2 n\rceil +1$
, there exists a subgraph of
$\overline {{\cal Q}_m}$
isomorphic to G.
Proof. Assume that G is a subgraph of
$\overline {{\cal Q}_m}$
. Then
$\overline {{\cal Q}_m}$
must have at least n vertices, so
$2^m\geq n$
or
$m\geq \lceil \log _2 n\rceil $
.
Now let
$m = \lceil \log _2 n\rceil +1$
. Proposition 2.3(2) implies that the graph
$\overline {{\cal Q}_m}$
contains a clique of cardinality
$2^{m-1} = 2^{\lceil \log _2 n\rceil } \geq n $
. Hence, any graph on n vertices can be embedded in
$\overline {{\cal Q}_m}$
.
The previous lemma fails to cover only the case when
$m = \lceil \log _2 n\rceil $
. In fact,
$\overline {{\cal Q}_{\lceil \log _2 n\rceil }}$
can contain G or not. So we can divide all graphs into two disjoint classes.
Definition 5.3. A graph G on n vertices belongs to the zeroth idempotent class if it is isomorphic to a subgraph of the complement
$\overline {{\cal Q}_m}$
of the m-hypercube for
$m = \lceil \log _2 n\rceil $
. If a graph does not belong to the zeroth idempotent class, it is said to belong to the first idempotent class. The number of the class will be denoted by
${\mathrm {idem}}(G)$
. So we have
${\mathrm {idem}}(G)\in \{0,1\}$
.
The following example guarantees that for any
$m\in {\mathbb N}$
, there exists a graph on
$n=2^m$
vertices that belongs to the first idempotent class. Moreover, this graph is the Hasse diagram of some poset.
Example 5.4. If a graph G on n vertices has a vertex of degree greater than
${2^{ \lceil \log _2 n\rceil } - \lceil \log _2 n\rceil - 1}$
, then G belongs to the first class by virtue of Proposition 2.3(1). For instance, we may consider a partial order on the set
$\{1,\ldots ,2^m\}$
such that all elements
$2,3,\ldots , 2^m$
are pairwise incomparable and 1 is the least element. Then the Hasse diagram of this poset belongs to the first class since the vertex 1 has degree
$2^m -1>2^m-m-1$
.
The zeroth idempotent class is closed under the disjoint union of graphs on
$2^k$
vertices, but the first class is not.
Example 5.5. The disjoint union
$G_1+G_2$
of two arbitrary graphs
$G_1$
,
$G_2$
on
$2^k$
vertices always belongs to the zeroth idempotent class. Indeed, the total number of vertices of
$G_1+G_2$
equals
$n = 2^{k+1}$
and so
$ \lceil \log _2 n\rceil = k+1$
. Proposition 2.3(2)–(3) implies that the graph
$\overline {{\cal Q}_{ \lceil \log _2 n\rceil }}$
has two disjoint cliques
$C_0$
,
$C_1$
of cardinality
$2^k$
. Hence,
$G_1$
and
$G_2$
can be embedded in
$C_0$
and
$C_1$
, respectively.
The following theorem provides the solution to Problem 1.1.
Theorem 5.6. Consider an incidence algebra
${\cal A} = {{\cal A}_n(\boldsymbol {\preceq },{\cal R})}$
. Then the following quantities coincide.
-
(1) The minimum number
$\nu $
of idempotent matrices that generate
${\cal A}$
as a unital
${\cal R}$
-algebra. -
(2) The minimum
$m\in {\mathbb N}$
such that the Hasse diagram of
$\boldsymbol {\preceq }$
can be embedded in the complement
$\overline {{\cal Q}_m}$
of the m-hypercube. -
(3) The sum
$\lceil \log _2 n\rceil + {\mathrm {idem}}(\boldsymbol {\prec :})$
, where
${\mathrm {idem}}(\boldsymbol {\prec :})\in \{0,1\}$
is the number of the idempotent class of the Hasse diagram of
$\boldsymbol {\preceq }$
in terms of Definition 5.3.
Proof. Quantities (1) and (2) are equal by Theorem 5.1. Also, Lemma 5.2 implies that quantities (2) and (3) coincide.
As a consequence, we can provide another proof of item (i) of [Reference Kelarev, van der Merwe and van Wyk7, Theorem 6]. It turns out that idempotent generators of
$T_n({\cal R})$
are related to Hamiltonian paths in a graph.
Corollary 5.7 [Reference Kelarev, van der Merwe and van Wyk7, Kelarev et al.].
Let
$\nu $
be the minimum number of idempotent generators of the algebra
$T_n({\cal R})$
of all
$n\times n$
upper-triangular matrices. Then
${\nu = \lceil \log _2 n\rceil }$
if
$ n\geq 5$
and
$\nu = \lceil \log _2 n\rceil +1$
for
$n=2,3,4$
.
Proof. The algebra
$T_n({\cal R})$
is an incidence algebra over the standard linear order
$\leq $
on
$\{1,\ldots ,n\}$
. Then the (undirected) Hasse diagram of
$\leq $
is the graph with edges
$\{1,2\}$
,
$\{2,3\}$
,
$\ldots ,\ \{n-1,n\}$
. It can be embedded in
$\overline {{\cal Q}_{\lceil \log _2 n\rceil }}$
if and only if
$\overline {{\cal Q}_{\lceil \log _2 n\rceil }}$
contains a simple path on n vertices. Proposition 2.3(5) implies that
$\overline {{\cal Q}_{m}}$
has a Hamiltonian path whenever
$m\geq 3$
, that is,
$\lceil \log _2 n\rceil \geq 3$
, or
$n\geq 5$
. The graph
$\overline {{\cal Q}_{1}}$
does not have edges and
$\overline {{\cal Q}_{2}}$
does not contain a simple path on
$3$
vertices (and on
$4$
as well). It remains to apply Theorem 5.6.
Problem 5.8. Let
${\cal K}$
be a noncommutative associative ring with an identity. Given an incidence ring
${\cal A} ={\cal A}_n(\boldsymbol {\preceq },{\cal K})$
, find the minimum cardinality
$\nu $
of a set S of idempotent matrices such that its union with the set of scalar matrices
$S\cup {\cal K} I_n$
generates
${\cal A}$
as a unital ring.
Acknowledgement
The author is grateful to his scientific supervisor Professor O. V. Markova for valuable discussions during the preparation of the paper.
