×

Rank of incidence matrix with applications to digraph reconstruction. (English) Zbl 1456.05097

Summary: The incidence matrix \(W_{t\, k}\) is defined as follow: Let \(V\) be a finite set, with \(v\) elements. Given non-negative integers \(t\), \(k\), \(W_{t\, k}\) is the \(\binom{v}{t}\) by \(\binom{v}{k}\) matrix of \(0\)’s and \(1\)’s, the rows of which are indexed by the \(t\)-element subsets \(T\) of \(V\), the columns are indexed by the \(k\)-element subsets \(K\) of \(V\), and where the entry \(W_{t\, k}(T,K)\) is \(1\) if \(T\subseteq K\) and is \(0\) otherwise.
R. M. Wilson [Eur. J. Comb. 11, No. 6, 609–615 (1990; Zbl 0747.05016)] proved that for \(t\leq\min (k, v-k)\), the rank of \(W_{t \, k}\) modulo a prime \(p\) is \(\sum^{t}_{i=0} \binom{v}{i} - \binom{v}{i-1}\) where \(p\) does not divide the binomial coefficient \(\binom{k-i}{t-i} \).
In this paper, we begin by giving an analytic expression of the rank of the matrix \(W_{t \, k}\) when \(t=t_0+t_1p+t_2p^2\), with \(t_0,t_1,t_2\in [0, p-1]\) and we characterize values of \(t\) and \(k\) such that \(\operatorname{dim}\mathrm{Ker}(^t W_{t\, k})\in\{0,1\}\). Next, using this result we generalize a result in the \((\leq 6)\)-reconstruction of digraphs due to G. Lopez [C. R. Acad. Sci., Paris, Sér. A 274, 1525–1528 (1972; Zbl 0237.04003); ibid., 275, 951–953 (1972; Zbl 0249.04002)].

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C20 Directed graphs (digraphs), tournaments
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
PDFBibTeX XMLCite
Full Text: DOI