# Expectation of the Site Frequency Spectrum

Alan R. Rogers Dept. of Anthropology, 260 Central Campus Dr, University of
Utah, Salt Lake City, UT 84112\<EMAIL_ADDRESS>Stephen P. Wooding
Dept. of Anthropology, University of California Merced, 5200 North Lake Road,
Merced, CA 95343.

The site frequency spectrum describes variation among a set of $n$ DNA
sequences. Its $i$’th entry ($i=1,2,\ldots,n-1$) is the number of nucleotide
sites at which the mutant allele is present in $i$ copies. Under selective
neutrality, random mating, and constant population size, the expected value of
the spectrum is well known but somewhat puzzling. Each additional sequence
added to a sample adds an entry to the end of the expected spectrum but does
not affect existing entries. This note reviews the reasons for this behavior.

In a sample of $n$ DNA sequences, a polymorphic nucleotide site can divide the
sample into 1 mutant and $n-1$ non-mutants, into 2 mutants and $n-2$ non-
mutants, and so on. The number of copies of the mutant must be at least 1 and
no more than $n-1$ if the site is polymorphic. The _site frequency spectrum_
describes the number of sites that fall into each of these $n-1$ categories.
It is widely used as a summary of variation among DNA sequences.

The expectation of the spectrum has a very simple form under random mating,
selective neutrality, and constant population size, provided that the mutation
rate is so low that we can ignore the possibility of multiple mutations at the
same site—the so-called “infinite sites” model of mutation [4]. The expected
spectrum for samples of sizes 2 through 5 looks like this:

Sample | Expected spectrum
---|---
size | (singletons, doubletons, $\ldots$)
2 | $\theta$
3 | $\theta,\quad\theta/2$
4 | $\theta,\quad\theta/2,\quad\theta/3$
5 | $\theta,\quad\theta/2,\quad\theta/3,\quad\theta/4$
Etcetera

Here, “singletons” are sites with one copy of the mutant allele, “doubletons”
are sites with two copies, and so on. $\theta=4Nu$, where $N$ is population
size and $u$ the mutation rate per sequence per generation. The expected
number of sites with $i$ copies of the mutant allele is $\theta/i$ [1, Eqn.
22]. It is remarkable that as we increase sample size, the number of mutants
in each category doesn’t change. We merely add a new category at the end. To
explore the cause of this behavior, we begin with a graphical argument.

0.75pt (.) ==0.5units ¡6.835cm, 1.75cm¿ x from 0.000000 to 1.463000, y from
-0.25 to 2.000000 0.000000 0.000000 1.330000 0.000000 / 0.000000 1.000000
0.330000 1.000000 / 0.000000 2.000000 0.330000 2.000000 / 0.330000 2.000000
0.330000 1.000000 / 0.330000 1.500000 1.330000 1.500000 / 1.330000 1.500000
1.330000 0.000000 / 1.330000 0.750000 1.463000 0.750000 / ¡5pt¿ [.2,.67] from
0.0947 -0.25 to 0 -0.25 ¡5pt¿ [.2,.67] from 0.2387 -0.25 to 0.325 -0.25 .67]
from 0.7633 -0.25 to 0.335 -0.25 ¡5pt¿ [.2,.67] from 0.9033 -0.25 to 1.33
-0.25 $2N$[c] at 0.8333 -0.25

Figure 1: Gene genealogy of a sample of size 3, with the expected length in
generations of each coalescent interval.

Figure 1 shows the gene genealogy of a sample of size 3, with branch lengths
equal to their expected values [2]. There are two coalescent intervals: a
recent one on the left, with three lines of descent, and an ancient one on the
right, with two. Imagine first that we could examine this sample at the end of
the ancient interval, just before the upper lineage bifurcates. Our tree would
have two branches, and the expected length of each is $2N$ generations. Thus,
we expect $2Nu=\theta/2$ mutations on each branch, and $\theta$ mutations
altogether, all of which are singletons.

At the time of the coalescent event, half of these singletons become
doubletons, and this is why we end up with $\theta/2$ doubletons at the left
edge of the graph. There are also new singletons, which arise via mutation
during the recent interval. How many? The expected length of this interval is
$2N/3$ generations, and there are 3 lines of descent, so the total branch
length within the interval is $2N$. Consequently, the recent interval will add
$\theta/2$ to the expected number of singletons—exactly the number that we
lost when the upper lineage bifurcated. At the end of the second interval, we
expect $\theta$ singletons and $\theta/2$ doubletons, just as in the table
above.

To carry this argument farther, we must make it algebraic, and our algebraic
argument paraphrases that of Hudson [3]. As in the graphical argument, we
census mutations at the recent (tipward) end of each coalescent interval. For
the $k$th interval (the one with $k$ lineages), let $s_{i,k}$ denote the
expected number of polymorphic sites at which the derived allele is present in
$i$ copies. There can be no polymorphic sites if there is only one lineage, so
$s_{i,1}=0$ for all $i$. Singletons require special treatment. Their expected
number obeys

$s_{1,k}=\frac{\theta}{k-1}+\left(1-\frac{1}{k-1}\right)s_{1,k-1}$ (1)

The first term on the right accounts for singleton mutations that arose within
the current ($k$th) interval. This is simply the number of new mutations, a
standard result from coalescent theory.111To derive the expression, note that
the expected duration of the interval is $4N/[k(k-1)]$. Multiply by $k$ to get
the total branch length and then by $u$ to get the expected number of
mutations. The second term is the contribution from the $s_{1,k-1}$ singletons
that existed during the $(k-1)$th interval. Of these, a fraction $1-1/(k-1)$
remain singletons because they lie on a lineage that did not bifurcate.

Consider now those mutations with $i>1$ copies at the end of interval $k$.
These can arise in two ways: either the mutation was present in $i-1$ copies
at the end of interval $k-1$, and one of the copies bifurcated, or else it was
present in $i$ copies, none of which bifurcated. We consider these cases
separately.

_Mutations that increased in number._ During the interval with $k-1$ lineages,
$s_{i-1,k-1}$ is the expected number of mutations present in $i-1$ copies. At
the end of this interval, a single random lineage bifurcates. Each lineage has
the same chance, $1/(k-1)$, of being the one that bifurcates, so a mutation
with $i-1$ copies has probability $(i-1)/(k-1)$ of including the lineage that
bifurcates. In this case, its number will increase from $i-1$ to $i$. Thus,
$\frac{i-1}{k-1}s_{i-1,k-1}$ is the contribution to $s_{i,k}$ from mutations
that increased in number.

_Mutations that did not increase._ During interval $k-1$, $s_{i,k-1}$ is the
expected number of mutations present in $i$ copies. With probability
$1-i/(k-1)$, none of these were on the lineage that bifurcated. Thus,
$(1-i/(k-1))s_{i,k-1}$ is the contribution to $s_{i,k}$ from mutations that
did not increase.

Summing these contributions,

$s_{i,k}=\frac{i-1}{k-1}s_{i-1,k-1}+\left(1-\frac{i}{k-1}\right)s_{i,k-1}$ (2)

for the case in which $i>1$.

Consider the sequence $s_{1,2}$, $s_{2,3}$, $s_{3,4}$, and so on. This is the
case of a “lucky” mutation whose count grows as fast as possible, because one
of its copies happens to bifurcate at the end of each coalescent interval. It
is of interest because it simplifies our equations. With $k=i+1$, the second
term in Eqns. 1 and 2 each disappear, leaving

$\displaystyle s_{1,2}$ $\displaystyle=$ $\displaystyle\theta$ $\displaystyle
s_{i,i+1}$ $\displaystyle=$ $\displaystyle\frac{i-1}{i}s_{i-1,i}\qquad\hbox{if
$i>1$}$

If you work your way through this sequence, you will discover that
$s_{i,i+1}=\theta/i$ for all $i$.

Now we are in a position to discover why the entries of the expected spectrum
do not change as we add DNA sequences to the sample—or in other words, why
$s_{i,k}$ does not depend on $k$. Rearrange Eqns. 1 and 2 as

$\displaystyle s_{1,k}$ $\displaystyle=$ $\displaystyle
s_{1,k-1}+\frac{\theta-s_{1,k-1}}{k-1}$ $\displaystyle s_{i,k}$
$\displaystyle=$ $\displaystyle
s_{i,k-1}+\frac{(i-1)s_{i-1,k-1}-is_{i,k-1}}{k-1}$

Using either equation, we can calculate $s_{i,i+2}$ from $s_{i,i+1}$, then
$s_{i,i+3}$ from $s_{i,i+2}$, and so on. At each step the second term
disappears, leaving $s_{i,k}=s_{i,k-1}$. This shows that $s_{i,k}$ does not
depend on $k$. Its value is given by the formula derived above for $k=i+1$:

$s_{i,k}=\theta/i$ (3)

for all $i$ and for all $k>i$, as shown by Fu [1, Eqn. 22].

## References

  * Fu [1995] Yunxin Fu.  Statistical properties of segregating sites.  Theoretical Population Biology, 48(2):172–197, October 1995.
  * Hudson [1990] Richard R. Hudson.  Gene genealogies and the coalescent process.  In Douglas Futuyma and Janis Antonovics, editors, Oxford Surveys in Evolutionary Biology, volume 7, pages 1–44. Oxford University Press, Oxford, 1990.
  * Hudson [2015] Richard R. Hudson.  A new proof of the expected frequency spectrum under the standard neutral model.  PLoS ONE, 10(1):e0118087, 2015.
  * Kimura [1969] Motoo Kimura.  The number of heterozygous nucleotide sites maintained in a finite population due to steady flux of mutation.  Genetics, 61:893–903, 1969.


* [224] Krista McCord.  Coupling Semi-Analytic Models and N-Body Simulations: A New Way of Making Galaxies and Stellar Halos.  PhD thesis, University of Alabama, United States, January 2017.
  * [225] Lam Hui and Nickolay Y. Gnedin.  Equation of state of the photoionized intergalactic medium.  MNRAS, 292(1):27–42, November 1997.
  * [226] M. McQuinn.  The Evolution of the Intergalactic Medium.  Annual Review of Astronomy and Astrophysics, 54:313–362, September 2016.
  * [227] Zarija Lukić, Casey W. Stark, Peter Nugent, Martin White, Avery A. Meiksin, and Ann Almgren.  The Lyman $\alpha$ forest in optically thin hydrodynamical simulations.  MNRAS, 446(4):3697–3724, February 2015.
  * [228] Graziano Rossi.  The Sejong Suite: Cosmological Hydrodynamical Simulations with Massive Neutrinos, Dark Radiation, and Warm Dark Matter.  ApJS, 249(2):19, August 2020.
  * [229] Michael Walther, Eric Armengaud, Corentin Ravoux, Nathalie Palanque-Delabrouille, Christophe Yèche, and Zarija Lukić.  Simulating intergalactic gas for desi-like small scale lyman-alpha forest observations.  Journal of Cosmology and Astroparticle Physics, 2021(04):059, Apr 2021.
  * [230] Ann Almgren, John Bell, Mike Lijewski, Zarija Lukic, and Ethan Van Andel.  Nyx: A Massively Parallel AMR Code for Computational Cosmology.  Astrophys. J., 765:39, 2013.
  * [231] Jean Sexton, Zarija Lukić, Ann Almgren, Chris Daley, Brian Friesen, Andrew Myers, and Weiqun Zhang.  Nyx: A massively parallel amr code for computational cosmology.  Journal of Open Source Software, 6(63):3068, 2021.
  * [232] R. Teyssier.  Cosmological hydrodynamics with adaptive mesh refinement. A new high resolution code called RAMSES.  A&A, 385:337–364, April 2002.
  * [233] Volker Springel.  The cosmological simulation code GADGET-2.  MNRAS, 364(4):1105–1134, December 2005.
  * [234] Keir K. Rogers, Hiranya V. Peiris, Andrew Pontzen, Simeon Bird, Licia Verde, and Andreu Font-Ribera.  Bayesian emulator optimisation for cosmology: application to the Lyman-alpha forest.  J. Cosmology Astropart. Phys., 2019(2):031, February 2019.
  * [235] Timur Takhtaganov, Zarija Lukić, Juliane Müller, and Dmitriy Morozov.  Cosmic Inference: Constraining Parameters with Observations and a Highly Limited Number of Simulations.  ApJ, 906(2):74, January 2021.
  * [236] Katrin Heitmann, David Higdon, Charles Nakhleh, and Salman Habib.  Cosmic Calibration.  ApJ, 646(1):L1–L4, July 2006.
  * [237] Christian Pedersen, Andreu Font-Ribera, Keir K. Rogers, Patrick McDonald, Hiranya V. Peiris, Andrew Pontzen, and Anže Slosar.  An emulator for the Lyman-$\alpha$ forest in beyond-$\Lambda$CDM cosmologies.  J. Cosmology Astropart. Phys., 2021(5):033, May 2021.
  * [238] J. Oñorbe, J. F. Hennawi, Z. Lukić, and M. Walther.  Constraining Reionization with the z $\sim$ 5-6 Ly$\alpha$ Forest Power Spectrum: The Outlook after Planck.  ApJ, 847(1):63, Sep 2017.
  * [239] J. Oñorbe, J. F. Hennawi, and Z. Lukić.  Self-consistent Modeling of Reionization in Cosmological Hydrodynamical Simulations.  ApJ, 837:106, March 2017.
  * [240] J. A. Kollmeier, J. Miralda-Escudé, R. Cen, and J. P. Ostriker.  Galactic Wind Effects on the Ly$\alpha$ Absorption in the Vicinity of Galaxies.  ApJ, 638:52–71, February 2006.
  * [241] V. Desjacques, M. G. Haehnelt, and A. Nusser.  The impact of galactic winds from Lyman-break galaxies on the intergalactic medium.  MNRAS, 367:L74–L78, March 2006.
  * [242] Matteo Viel, Joop Schaye, and C. M. Booth.  The impact of feedback from galaxy formation on the Lyman $\alpha$ transmitted flux.  MNRAS, 429(2):1734–1746, February 2013.
  * [243] Solène Chabanier, Frédéric Bournaud, Yohan Dubois, Nathalie Palanque-Delabrouille, Christophe Yèche, Eric Armengaud, Sébastien Peirani, and Ricarda Beckmann.  The impact of AGN feedback on the 1D power spectra from the Ly $\alpha$ forest using the Horizon-AGN suite of simulations.  MNRAS, 495(2):1825–1840, June 2020.
  * [244] Paulo Montero-Camacho and Yi Mao.  Extracting the astrophysics of reionization from the Ly$\alpha$ forest power spectrum: a first forecast.  MNRAS, 508(1):1262–1279, November 2021.


# Sina at FigNews 2024:
Multilingual Datasets Annotated with Bias and Propaganda

Lina Duaibes Birzeit University<EMAIL_ADDRESS>Areej Jaber
Palestine Technical University-Khadoorie<EMAIL_ADDRESS>Mustafa Jarrar
Birzeit University<EMAIL_ADDRESS>
Ahmad Qadi 7amleh Center<EMAIL_ADDRESS>Mais Qandeel ÖREBRO University
<EMAIL_ADDRESS>
###### Abstract

The proliferation of bias and propaganda on social media is an increasingly
significant concern, leading to the development of techniques for automatic
detection. This article presents a multilingual corpus of $12,000$ Facebook
posts fully annotated for bias and propaganda. The corpus was created as part
of the FigNews $2024$ Shared Task on News Media Narratives for framing the
Israeli War on Gaza. It covers various events during the War from October $7$,
$2023$ to January $31$, $2024$. The corpus comprises $12,000$ posts in five
languages (Arabic, Hebrew, English, French, and Hindi), with $2,400$ posts for
each language. The annotation process involved $10$ graduate students
specializing in Law. The Inter-Annotator Agreement (IAA) was used to evaluate
the annotations of the corpus, with an average IAA of $80.8\%$ for bias and
$70.15\%$ for propaganda annotations. Our team was ranked among the best-
performing teams in both Bias and Propaganda subtasks. The corpus is open-
source and available at https://sina.birzeit.edu/fada

utf8

Sina at FigNews 2024:
Multilingual Datasets Annotated with Bias and Propaganda

Lina Duaibes Birzeit University<EMAIL_ADDRESS>Areej Jaber
Palestine Technical University-Khadoorie<EMAIL_ADDRESS>Mustafa Jarrar
Birzeit University<EMAIL_ADDRESS>Ahmad Qadi 7amleh Center
<EMAIL_ADDRESS>Mais Qandeel ÖREBRO University<EMAIL_ADDRESS>

##  1 Introduction

Since October $7$, social media has been flooded with posts, articles, images,
and videos related to the Israeli War on Gaza. Such posts are often divided by
hate, bias, and fake news either in favor of or against one of the parties or
by remaining neutral, see e.g., "Framing the Israeli War on Gaza" is a shared
task on news media narratives Zaghouani et al. (2024), which is part of the
$2$nd ArabicNLP conference. The task aims to create a multilingual corpus that
unravels the layers of bias and propaganda within news articles in various
languages.

Such shared tasks and datathons are crucial in the NLP community to foster
collaboration and advance research in specific areas. Previous efforts, such
as SemEval-$2020$ Task $11$ Martino et al. (2020) and TSHP-$17$ Rashkin et al.
(2017) have provided valuable resources for propaganda detection in news
articles. The dual focus of FigNews on bias and propaganda is a novel approach
that addresses the evolving nature of misinformation on social media
platforms. The detection of propaganda on social media is crucial Darwish et
al. (2021), as it can polarize public sentiment, foster violent extremism and
hate speech, and eventually erode democracies and diminish trust in democratic
procedures Abuaiadah et al. (2017). Notably, only a few corpora have been
recently built to address these issues. Recent work by (Hamad et al., 2023)
involved establishing a Hebrew dataset comprising $15,881$ tweets for
detecting offensive language. This dataset was manually annotated with four
labels: hate, abusive, violence, and pornographic. Their work focused on
detecting hate speech in Hebrew tweets and implemented in SinaTools Hammouda
et al. (2024). Additionally, the WojoodNER Shared Task 2024 offered a new NER
dataset related to the Israeli War on Gaza called WojoodGaza Jarrar et al.
(2024). Other notable works include TSHP-$17$ (Rashkin et al., 2017), QProp
(Barrón-Cedeno et al., 2019), and PTC (Da San Martino et al., 2019). TSHP-$17$
and QProp are document-level corpora, while PTC is a sentence-level corpus.
While SemEval-$2020$ (Martino et al., 2020) Task $11$ is similar to FigNews
(Zaghouani et al., 2024) in its objective, they differ in their data sources
and focus areas.

This paper describes our participation in the FigNews. Our contributions are:

  * •

Annotated Corpus ($12K$ FB posts) for bias and propaganda, in $5$ languages.

  * •

Annotation guidelines ensuring consistency and accuracy.

Remark: The corpus presented in this article does not cover the genocide,
ethnic cleansing, or starvation events as they mostly happened after
collecting the corpus.

The article is organized as follows: Section 2 describes the methodology, 3
presents our team composition and training; Section 3 presents our
participation and results; Section 5 analyzes some errors, and Section 6
concludes the paper.

##  2 Annotation Methodology

The objective of the task is to address the complex landscape of social media
discourse related to the Israeli War on Gaza $2023$-$2024$. The task
organizers provided participants with $15$k posts from verified Facebook
accounts, selected between October $6$, $2023$, and January $31$, $2024$,
using "Gaza" as a query keyword across $5$ languages: Arabic, Hebrew, English,
French, and Hindi. The dataset consists of $15$ batches, each containing
$1000$ posts.

|  | Biased | Propaganda
---|---|---|---
| Cohen’s kappa | F1_score_weighted | Cohen’s kappa | F1_score_weighted
Annotators’ pair | All | Binary | All | Binary | All | Binary | All | Binary
| 6 | 0.57 | 0.57 | 0.79 | 0.79 | 0.76 | 0.85 | 0.85 | 0.98
| 4 | 0.76 | 0.77 | 0.53 | 0.56 | 0.33 | 0.25 | 0.58 | 0.93
| 8 | 0.29 | 0.28 | 0.64 | 0.65 | 0.11 | 1 | 0.28 | 1
1 | 2 | 0.64 | 0.64 | 0.82 | 0.85 | 0.72 | 0.62 | 0.8 | 0.91
| 10 | 0.8 | 0.78 | 0.86 | 0.9 | 0.67 | 1 | 0.77 | 1
| 4 | 0.51 | 0.55 | 0.75 | 0.79 | 0.81 | 1 | 0.87 | 1
| 6 | 0.89 | 0.93 | 0.96 | 0.98 | 0.37 | 0.78 | 0.59 | 0.97
3 | 8 | 0.97 | 1 | 0.98 | 1 | 0.79 | 0.96 | 0.85 | 0.98
| 10 | 0.3 | 0.38 | 0.59 | 0.77 | 0.07 | 0.44 | 0.32 | 0.83
| 2 | 0.79 | 0.81 | 0.87 | 0.92 | 0.79 | 0.86 | 0.785 | 0.93
| 4 | 0.58 | 0.72 | 0.79 | 0.9 | 0.82 | 0.98 | 0.75 | 0.95
9 | 6 | -0.11 | -0.09 | 0.54 | 0.59 | 0.18 | 0.57 | 0.48 | 0.85
| 8 | 0.94 | 0.97 | 0.98 | 0.98 | 0.93 | 1 | 0.95 | 1
| 10 | 0.47 | 0.49 | 0.74 | 0.76 | 0.93 | 1 | 0.95 | 1
| 2 | 1 | 1 | 1 | 1 | 0.85 | 0.93 | 0.91 | 0.97
7 | 4 | 1 | 1 | 1 | 1 | 0.81 | 0.91 | 0.89 | 0.98
| 8 | 0.51 | 0.63 | 0.72 | 0.83 | 0.15 | 0 | 0.49 | 93
| 10 | 0.87 | 0.85 | 0.95 | 0.95 | 0.92 | 1 | 0.95 | 1
| 2 | 0.52 | 0.55 | 0.77 | 0.85 | 0.46 | 0.54 | 0.49 | 0.8
5 | 6 | 0.39 | 0.45 | 0.65 | 0.75 | 0.05 | 0 | 0.34 | 0.91
Average | 0.808 | 0.8515 | 0.623 | 0.6535 | 0.7015 | 0.9475 | 0.5725 | 0.733
Table 1: IAA for bias and propaganda annotations.

###  2.1 Annotation Guidelines

Our understanding of "bias" is based on the work done by the United Nations
Committee on the Elimination of Racial Discrimination and the European
Commission against Racism and Intolerance European External Action Service
(n.d.). We define the notations ‘bias’ and ‘propaganda’ based on the UN and EU
accounts, as:

Bias: is generally understood as an inclination or prejudice towards or
against a particular person or group, often in a way considered to be unfair.
In other words, it is an unreasonable preference or dislike that prompts
someone to behave in a discriminatory way, often based on unfair judgment.
This bias is typically based on prohibited grounds of discrimination such as
race, religion, language, nationality, ethnicity, social background, gender,
and others.

Classifications of Bias: we adopted the same classes provided in the Shared
Task: (1) Biased against Palestine,(2) Biased against Israel, (3) Biased
against others, (4) Biased against both Israel and Palestine, (5) Not
Applicable, (6) Unclear, and (7) Unbiased. We also introduced a new feature
called "Type of Bias", which can be either: (a) $Explicit$ (تحيز صريح>) if it
is obvious and evident in the post, (b) $Implicit$ (تحيز ضمني>) if it is clear
but not evident in the post, and (c) $Vague$ (تحيز مبهم>) in case of indirect
and ambiguous bias. This feature is important from a methodological viewpoint
as it encourages the annotators to think more during classification. If a post
contains biased content but not in a direct way it can be accounted as
implicit.
Propaganda: misleading ideas or statements that can distort the truth or omit
facts to promote a specific political or social agenda. These ideas are
typically published by media outlets. For example, propaganda can take the
forms of exaggeration, minimization, spreading doubts, name-calling, labeling,
or intentional vagueness. All these forms have the common intention to spread
false information and obscure facts.

Classifications of Propaganda: We adopted the four classes provided in the
Shared Task: (i) Propaganda, (ii) Not propaganda, (iii) Not Applicable, and
(iv) Unclear.

Additionally, we added a new column to classify Propaganda into three types:
(1) Propaganda must be deleted: if it contains evident harmful content that
poses risks to the safety and security of individuals or groups; (2)
Propaganda may be deleted: if we cannot easily judge whether it is propaganda,
depending on a specific context; and (3) Propaganda not to be deleted: if it
is not clear and lacks harmful consequences and therefore does not warrant
deletion.

Remark: Since the data was collected from Facebook posts some cases contain
quoted content (e.g. an unbiased post quoting biased content). It was
established in the guidelines that a post should not be classified as bias or
propaganda based on its quotation, but rather on the post itself.

An Example of the guidelines mentioned earlier regarding quoted content is as
follows: “Hamas and Islamic Jihad spare no effort to exploit religious
institutions for terrorist purposes,” the IDF said in a statement. This post
is annotated as unbiased because it is a direct quote and does not include any
additional commentary or interpretation.

###  2.2 Inter-Annotator Agreement (IAA)

To evaluate the quality of our annotations, we used the $F1$-score and Cohen’s
Kappa Cohen (1968) to compute the agreement between the annotators. The
results are shown in Table 1.

The task organizers allocated 100 posts ($10\%$) from each batch for IAA,
including $20$ posts randomly selected from each language. Overall, we
annotated $12,000$ posts, resulting in an IAA dataset of $1,200$ posts. These
were distributed among our $10$ annotators following this scheme: (1) each
annotator received $240$ posts, (2) each post was annotated by two different
annotators, and (3) the $240$ posts assigned to each annotator were
distributed among four other annotators. Consequently, each pair of annotators
had $60$ posts in common.

All vs. Binary IAA: to evaluate whether a (dis)agreement was dominated by a
certain class, we mapped all labels into binary categories: ($Bias$ or
$NotBias$ $and$ $others$) and ($Propaganda$ or $NotPropaganda$ $and$
$others$). Table 1 demonstrates no class dominance because All and Binary
evaluations are close to each other.

Looking at all Cohen’s scores in Table 1, the average is $0.808$ for bias,
which is a "very good" agreement, and $0.7015$ for propaganda, which is a
"good" agreement overall. Agreement on propaganda was more challenging but the
results are enhanced when it is considered as a binary.

##  3 Team Composition and Training

Team composition: We assembled a team of $10$ Master’s students specializing
in Law at Birzeit University, comprising $7$ females and $3$ males. All team
members are native Arabic speakers with a good command of English.

Training phase: We began by selecting $200$ posts to train all students in
annotation. After training, each student was assigned $1,200$ posts for
annotation.

Ensuring consistency We held three workshops to ensure consistency to discuss
guidelines, address challenges, and resolve disparities.The first workshop
involved an expert who reviewed the annotations and added comments for the
annotators to address. In the second workshop, the annotators met with the
expert to discuss his comments on the posts. In the final workshop, after
reviewing their annotations compared to the expert’s, they discussed the
points of agreement and disagreement with him.

Subtask | Track | 1st Place |  2nd Place | 3rd Place
---|---|---|---|---
Bias | Guidelines | NLPColab |  Eagles | Narrative Navigators
Bias | IAA Quality | NLPColab |  JusticeLeague | Sina
Bias | Quantity | DRAGON |  NLPColab | Sina
Bias | Consistency | The Lexicon Ladies |  NLPColab | Narrative Navigators
Propaganda | Guidelines | NLPColab |  Bias Bluff Busters | Sina
Propaganda | IAA Quality | NLPColab |  Sina | The CyberEquity Lab
Propaganda | Quantity | NLPColab |  Sina | The CyberEquity Lab
Propaganda | Consistency | NLPColab |  Bias Bluff Busters | Sahara Pioneers/The CyberEquity Lab
Table 2: FIGNEWS 2024 shared task results.

###  3.1 Annotation process

Annotation Phase: The dataset consisted of $12$ batches, comprising $10,800$
posts from the Main sheet, and $1200$ posts from the IAA sheet. The annotation
was carried out in two phases:

  1. 1.

Phase One: We distributed Batch01 and Batch02, each with $180$ posts, among
team members. To ensure consistency with the guidelines, an expert reviewed
all student annotations for these batches and provided feedback.

  2. 2.

Phase Two: we assigned each annotator $450$ posts from two different batches.
This step allowed us to complete the annotation of all $12$ batches (i.e.
$12k$ posts).

Set quality standards

To set quality standards among annotators, after the annotation process was
complete, each pair of annotators who had annotated the same data held
meetings to review the selected posts they disagreed on. They discussed their
differences, and if they reached an agreement, they would change the label
accordingly. If they could not agree, they kept the original label.

##  4 Task Participation and Results

###  4.1 Results

Table 2 displays the final results provided by the shared task organizers. Our
Sina team achieved the third and second place in the IAA Quality and Quantity
tracks for the Bias and Propaganda subtasks, respectively. In addition to
third place in Propaganda Guidelines.

Table 3 and Table 4 illustrate the distribution of the bias classes and types
of bias across languages respectively. Table 3 shows that about $27\%$ of the
posts are biased against Palestine and $63\%$ of the posts are unbiased. Most
of the bias against Palestine originated from French posts. Table 4 gives more
statistics about the types of bias. As shown in this table, most of the posts
annotated as $Explicit$ bias are in Hebrew.

For propaganda results, Table 5 illustrates the distributions of propaganda
classes across languages, which shows that $31$% of the posts ($3333$) are
annotated as "Propaganda", and $66\%$ ($7084$) are "Not Propaganda". The
majority of the propaganda originated from French posts. Table 6 illustrates
the distribution of the type of propaganda classes among languages. As shown
in the table posts that were classified as propaganda must be deleted were in
French with 348 posts.

Class | Ar | En | He | Fr | Hi | Total
---|---|---|---|---|---|---
Biased Against Palestine | 466 | 514 | 595 | 807 | 534 | 2916
Biased Against Israel | 94 | 79 | 23 | 19 | 70 | 285
Biased against Both | 6 | 7 | 11 | 6 | 14 | 44
Biased against others | 42 | 28 | 53 | 39 | 49 | 211
Unbiased | 1371 | 1486 | 1369 | 1212 | 1386 | 6824
Not applicable | 49 | 7 | 17 | 20 | 25 | 118
Unclear | 132 | 39 | 92 | 57 | 82 | 402
Total | 2160 | 2160 | 2160 | 2160 | 2160 | 10800
Table 3: Distribution of bias classes across languages Type of Bias | Ar | En | He | Fr | Hi | Total
---|---|---|---|---|---|---
$Explicit$ (تحيز صريح>) | 394 | 336 | 563 | 412 | 388 | 2093
$Implicit$ (تحيز ضمني>) | 199 | 217 | 265 | 236 | 269 | 1186
$Vague$ (تحيز مبهم>) | 36 | 37 | 59 | 52 | 27 | 211
Table 4: Types of Bias Class | Ar | En | He | Fr | Hi | Total
---|---|---|---|---|---|---
Propaganda | 524 | 679 | 648 | 809 | 673 | 3333
Not propaganda | 1484 | 1443 | 1447 | 1297 | 1413 | 7084
Not applicable | 48 | 11 | 17 | 16 | 24 | 116
Unclear | 104 | 27 | 48 | 38 | 50 | 267
Total | 2160 | 2160 | 2160 | 2160 | 2160 | 10800
Table 5: Distribution of propaganda subtask classes across languages Class | Ar | En | He | Fr | Hi | Total
---|---|---|---|---|---|---
Propaganda Must be deleted | 192 | 191 | 266 | 348 | 277 | 1274
Propaganda May be deleted | 524 | 488 | 382 | 461 | 396 | 2059
Propaganda not to be deleted | 451 | 422 | 565 | 648 | 436 | 2522
Table 6: Types of Propaganda classes.

##  5 Error Analysis and Discussion

Despite training and supervision, errors may arise from subjective
interpretation, ambiguous guidelines, or complex content. We explored the
errors and noted:

  1. 1.

False positives in bias annotations occurred when annotators marked neutral
content as biased. For instance, the post: "Israel launched attacks on Syria
on Nov $10$ in response to a drone strike on Eilat. The IDF claimed it
attacked an organization responsible for the drone. Watch for more details."
This news excerpt is informative and not biased.

  2. 2.

Misclassification of propaganda: Some content was wrongly labeled as "must be
deleted" propaganda despite lacking direct harmful implications. For example:
"BREAKING: Israeli forces are causing massive destruction in Gaza, in response
to a terrorist attack by Hamas. Image source: Middle East Eye post." While it
is propaganda, it shouldn’t be classified as "must be deleted."

##  6 Conclusion

This article presents our contribution to the FigNews $2024$, where we
annotated a multilingual corpus of $12,000$ Facebook posts for bias and
propaganda across five languages. We extended the annotation guidelines for
better consistency and accuracy, providing a foundation for future work in
detecting bias in social media. Our plans include expanding the corpus to
cover more critical events of the war and leveraging neural and large Language
models to automatically detect bias and propaganda on social media posts.

## Ethical Considerations

Given the sensitive nature of the topics and media narratives related to the
Israel War on Gaza, our annotators, who are lawyers, have undergone extensive
training to ensure careful and fair judgments. They meticulously review both
Arabic and English translations to avoid any bias that might arise from
machine translation.

## Limitations

We recognize the limitations in our annotation process. This is because of the
subjective nature of identifying bias and propaganda in social media posts,
and the sensitivity of the datasets involved.

## Acknowledgments

We would like to acknowledge the contributions of Nejira Softic during the
formulation of the guidelines. We would like to also thank the Master’s
students specializing in Law and IT at Birzeit University for their help in
annotating the datasets, especially Maram Shour, Belal Abu Zaina, Bayan Abu
Alawi, Zainah Abughosh, Aya Al Dimasy, Doaa Abozena, Waad Alsheikh, Qassam Abu
Hakmeh, Aseel Mustafa, Basel Awwad, Omar To’Mallah, and Dyala Fakhouri, and as
well as Prof. Reem Al-Botmeh for her support during the course. Also thanks to
Palestine Technical University - Kadoorie for its support.

## References

  * Abuaiadah et al. (2017) Diab Abuaiadah, Dileep Rajendran, and Mustafa Jarrar. 2017.  Clustering Arabic Tweets for Sentiment Analysis.  In _Proceedings of the 2017 IEEE/ACS 14th International Conference on Computer Systems and Applications_ , pages 499–506. IEEE Computer Society.
  * Barrón-Cedeno et al. (2019) Alberto Barrón-Cedeno, Israa Jaradat, Giovanni Da San Martino, and Preslav Nakov. 2019.  Proppy: Organizing the news based on their propagandistic content.  _Information Processing & Management_, 56(5):1849–1864.
  * Cohen (1968) Jacob Cohen. 1968.  Weighted kappa: Nominal scale agreement provision for scaled disagreement or partial credit.  _Psychological Bulletin_ , 70(4):213.
  * Da San Martino et al. (2019) Giovanni Da San Martino, Yu Seunghak, Alberto Barrón-Cedeno, Rostislav Petrov, Preslav Nakov, et al. 2019.  Fine-grained analysis of propaganda in news article.  In _Proceedings of the 2019 EMNLP-IJCNLP Conference_ , pages 5636–5646. ACL.
  * Darwish et al. (2021) Kareem Darwish, Nizar Habash, Mourad Abbas, Hend Al-Khalifa, Huseein T. Al-Natsheh, Houda Bouamor, Karim Bouzoubaa, Violetta Cavalli-Sforza, Samhaa R. El-Beltagy, Wassim El-Hajj, Mustafa Jarrar, and Hamdy Mubarak. 2021.  A Panoramic survey of Natural Language Processing in the Arab Worlds.  _Commun. ACM_ , 64(4):72–81.
  * European External Action Service (n.d.) European External Action Service. n.d.  Human rights guidelines on freedom of expression online and offline.  https://www.eeas.europa.eu/sites/default/files/11_hr_guidelines_external_action_en.pdf.
  * Hamad et al. (2023) Nagham Hamad, Mustafa Jarrar, Mohammed Khalilia, and Nadim Nashif. 2023.  Offensive Hebrew Corpus and Detection using BERT.  In _Proceedings of the 20th ACS/IEEE International Conference on Computer Systems and Applications (AICCSA)_. IEEE.
  * Hammouda et al. (2024) Tymaa Hammouda, Mustafa Jarrar, and Mohammed Khalilia. 2024.  SinaTools: Open Source Toolkit for Arabic Natural Language Understanding.  In _Proceedings of the 2024 AI in Computational Linguistics (ACLING 2024)_ , Procedia Computer Science, Dubai. ELSEVIER.
  * Jarrar et al. (2024) Mustafa Jarrar, Nagham Hamad, Mohammed Khalilia, Bashar Talafha, AbdelRahim Elmadany, and Muhammad Abdul-Mageed. 2024.  WojoodNER 2024: The Second Arabic Named Entity Recognition Shared Task.  In _Proceedings of the Second Arabic Natural Language Processing Conference (ArabicNLP 2024)_ , Bangkok, Thailand. Association for Computational Linguistics.
  * Martino et al. (2020) G. Martino, Alberto Barrón-Cedeno, Henning Wachsmuth, Rostislav Petrov, and Preslav Nakov. 2020.  Semeval-2020 task 11: Detection of propaganda techniques in news articles.  _arXiv preprint arXiv:2009.02696_.
  * Rashkin et al. (2017) Hannah Rashkin, Eunsol Choi, Jin Yea Jang, Svitlana Volkova, and Yejin Choi. 2017.  Truth of varying shades: Analyzing language in fake news and political fact-checking.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 2931–2937. Association for Computational Linguistics.
  * Zaghouani et al. (2024) Wajdi Zaghouani, Mustafa Jarrar, Nizar Habash, Houda Bouamor, Imed Zitouni, Mona Diab, Samhaa R. El-Beltagy, and Muhammed AbuOdeh, editors. 2024.  _The FIGNEWS Shared Task on News Media Narratives_. Association for Computational Linguistics, Bangkok, Thailand.


# Moore-Penrose inverses of incidence matrices

Ali Azimi  Department of Mathematics and Applied Mathematics, Xiamen
University Malaysia, 43900, Sepang, Selangor Darul Ehsan, Malaysia
<EMAIL_ADDRESS><EMAIL_ADDRESS>,  R. B. Bapat  Indian Statistical
Institute, New Delhi, 110016, India<EMAIL_ADDRESS>and  M. Farrokhi D. G
Research Center for Basic Sciences and Modern Technologies (RBST), Institute
for Advanced Studies in Basic Sciences (IASBS), Zanjan 45137-66731, Iran
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

We present explicit formulas for Moore-Penrose inverses of some families of
set inclusion matrices arising from sets, vector spaces, and designs.

###### Key words and phrases:

Moore-Penrose inverse, incidence matrices, vector space, design

###### 2020 Mathematics Subject Classification:

Primary 05B20, 15A09; Secondary 05A30, 15A03.

The first author was supported by a Xiamen University Malaysia Research Fund
(Grant No. XMUMRF/2023-C11/IMAT/0023).

##  1\. Introduction

The incidence algebra $\mathcal{A}_{\mathcal{P}}$ of a locally finite poset
$\mathcal{P}$ is the associative algebra of all real-valued functions on
$\mathcal{P}\times\mathcal{P}$ that vanish on pairs $(p,q)$ with
$p\not\preccurlyeq q$. The addition being the ordinary sum of functions while
the multiplication $f*g$ of two elements $f,g$ of $\mathcal{A}_{\mathcal{P}}$
is defined as

$(f*g)(x,y)=\sum_{x\leq z\leq y}f(x,y)g(y,z).$

The zeta function $\zeta_{\mathcal{P}}$ of $\mathcal{P}$ (or
$\mathcal{A}_{\mathcal{P}}$) is the constant function
$\zeta_{\mathcal{P}}(x,y)=1$ on all $(x,y)$ satisfying $x\preccurlyeq y$. The
zeta function $\zeta_{\mathcal{P}}$ is invertible in the algebra
$\mathcal{A}_{\mathcal{P}}$. The inverse of $\zeta_{\mathcal{P}}$ is called
the Möbius function $\mu_{\mathcal{P}}$ of $\mathcal{P}$ generalizing the
classical Möbius function from number theory as well as inclusion-exclusion
principle from set theory. Möbius function of posets has studied since 1935 by
Weisner [18, 19] and Hall [9] for the lattice of subgroups of finite groups,
and later, in a general setting, by Rota [15] in 1964.

The incidence matrix $\mathcal{I}_{\mathcal{P}}$ of $\mathcal{P}$ is the $0-1$
matrix whose rows and columns are indexed by elements of $\mathcal{P}$ with
$(p,q)$ entry being $1$ if $p\preccurlyeq q$ and $0$ otherwise. The matrix
$\mathcal{I}_{\mathcal{P}}$ is actually the matrix representation of the zeta
function of $\mathcal{P}$. Accordingly, $\mathcal{I}_{\mathcal{P}}$ is
invertible and its inverse is the matrix representation of the Möbius function
of $\mathcal{P}$.

Beside incidence matrices $\mathcal{I}_{\mathcal{P}}$ of posets, their
submatrices, we still call incidence matrices, are also of particular interest
when studying relationships between two classes of objects that appear
naturally in various contexts like design theory, coding theory, algebraic
graph theory, representation theory, finite geometry, etc., see for instance
[3, 6, 10, 20, 21]. Set inclusion incidence matrices arising from subsets of a
set or subspaces of a vertex space are typical and most accessible examples of
incidence matrices having many applications in combinatorial contexts, in
particular design theory and extremal set theory [4, 8, 20, 21].

Given a set $S$ with $n$ elements and $0\leq r\leq c\leq n$, the set inclusion
incidence matrix $M=M(n;r,c)$ of $S$ is an $\binom{n}{r}\times\binom{n}{c}$
matrix defined as follows: the rows and columns of $M$ are indexed by
$r$-subsets and $c$-subsets of $S$, respectively, with $(R,C)$-entry equal to
$\delta_{R\subseteq C}$, where

$\delta_{R\subseteq C}:=\begin{cases}1,&R\subseteq C,\\\ 0,&R\nsubseteq
C\end{cases}$

is the Kronecker delta. The set inclusion matrix $M(n;r,c)$ of a vector space
$V$ of dimension $n$ over a finite field with $q$ elements is defined
analogously with rows and columns are indexed by $r$-dimensional and
$s$-dimensional subspaces of $V$, respectively. In this case, $M(n;r,c)$ is an
$\binom{n}{r}_{q}\times\binom{n}{c}_{q}$ matrix with $\binom{n}{i}_{q}$ being
the Gaussian binomial coefficient. The above definitions can be extended to
set inclusion matrices of sub-algebras of any algebraic structures as well.

A generalized inverse of an $m\times n$ matrix $A$ is an $n\times m$ matrix
$G$ satisfying $AGA=A$. The Moore-Penrose inverse of $A$, denoted by $A^{+}$,
is a generalized inverse of $A$ satisfying the following three more equations:

$A^{+}AA^{+}=A^{+},\quad(AA^{+})^{T}=AA^{+},\quad(A^{+}A)^{T}=A^{+}A,$

where $M^{T}$ denotes the transpose of a matrix $M$ (see [13, 14]). It is
known that any two Moore-Penrose inverses of a matrix are equal and that any
complex matrix has a Moore-Penrose inverse (see [5, 11] for basic properties
of Moore-Penrose inverses). Notice that Moore-Penrose inverses need not exist
over any field.

Wilson [21] studies set inclusion matrices and gives a formula for their rank
over fields of prime characteristics. Extending the results of Wilson, Bapat
[1] gives implicit formulas for the Moore-Penrose inverse of set inclusion
matrices over fields of characteristic zero. Moreover, a necessary and
sufficient condition for these matrices to admit Moore-Penrose inverses over
fields of prime characteristics as well as an implicit formula for their
Moore-Penrose inverses (when exist) is offered.

The aim of this paper is to give explicit combinatorial formulas for Moore-
Penrose inverses of several classes of incidence matrices. In Section 2, we
introduce set inclusion incidence matrices and give their Moore-Penrose
inverses. Likewise, in Section 3, we introduces set includion incidence
matrices arising from vector spaces and give their Moore-Penrose inverses by
extending the results of Section 2. Using information on designs, we also give
a simple formula for Moore-Penrose inverses of incidence matrices of designs
in Section 4.

##  2\. Set inclusion incidence matrices

Let $r$, $c$, and $n$ be non-negative integers satisfying $0\leq r\leq c\leq
n$. The set inclusion incidence matrix $M=M(n;r,c)$ is an
$\binom{n}{r}\times\binom{n}{c}$ matrix defined as follows: the rows and
columns of $M$ are indexed by $r$-subsets and $c$-subsets of
$[n]:=\\{1,\ldots,n\\}$, respectively, with $(R,C)$-entry equal to
$\delta_{R\subseteq C}$. Let $M^{*}$ be the matrix whose rows and columns are
indexed by $c$-subsets and $r$-subsets of $[n]$, respectively, and its
$(C,R)$-entry is given by

$M^{*}_{C,R}=(-1)^{r-i}\frac{\binom{c-i-1}{r-i}}{\binom{N-r}{c-r}\binom{N-c}{r-i}},$

where $N=\max\\{n,r+c\\}$ and $i=|R\cap C|$. We show that $M^{*}$ is the
Moore-Penrose inverse of $M$. Indeed, $M^{*}$ has more interesting properties
described in the next lemma. To this end, we apply the following result of
Ruiz.

######  Proposition 2.1 ([16]).

Let $n\geq 0$ and $p(x)$ be a polynomial of degree less than $n$. Then

$\sum_{i=0}^{n}(-1)^{i}\binom{n}{i}p(i)=0.$

######  Lemma 2.2.

With the above notation, we have

  * (i)

$MM^{*}=I$ if $n\geq r+c$.

  * (ii)

$M^{*}M=I$ if $n\leq r+c$.

###### Proof.

(i) Let $R$ and $R^{\prime}$ be $r$-subsets of $[n]$ and put $k:=|R\cap
R^{\prime}|$. A simple verification shows that

$(MM^{*})_{R,R^{\prime}}=\sum_{i=k}^{r}(-1)^{r-i}\frac{\binom{r-k}{i-k}\binom{n-2r+k}{c-r-i+k}\binom{c-i-1}{r-i}}{\binom{n-r}{c-r}\binom{n-c}{r-i}}.$

If $R=R^{\prime}$, then $k=r$ and $(MM^{*})_{R,R^{\prime}}=1$. Now, assume
that $R\neq R^{\prime}$, i.e. $k<r$. Then

$\displaystyle(MM^{*})_{R,R^{\prime}}$
$\displaystyle=\frac{(c-r)(-1)^{r}}{(r-k)\binom{n-r}{r-k}}\sum_{i=k}^{r}(-1)^{i}\binom{c-i-1}{r-k-1}\binom{r-k}{i-k}$
$\displaystyle=\frac{(c-r)(-1)^{r-k}}{(r-k)\binom{n-r}{r-k}}\sum_{j=0}^{r-k}(-1)^{j}\binom{c-k-j-1}{r-k-1}\binom{r-k}{j}=0$

by Proposition 2.1 for $\binom{c-k-j-1}{r-k-1}$ is a polynomial of order less
than $r-k$ in $j$.

(ii) Let $C$ and $C^{\prime}$ be $c$-subsets of $[n]$ and put $k:=|C\cap
C^{\prime}|$. Since $n\leq r+c$, we have $N=r+c$ and $2c-n\leq k\leq c$. A
simple verification shows that

$(M^{*}M)_{C,C^{\prime}}=\sum_{i=\max\\{0,r+k-c\\}}^{\min\\{k,r\\}}(-1)^{r-i}\frac{\binom{k}{i}\binom{c-k}{r-i}\binom{c-i-1}{r-i}}{\binom{c}{r}\binom{r}{i}}.$

If $C=C^{\prime}$, then $k=c$ and $(M^{*}M)_{C,C^{\prime}}=1$. Now, suppose
that $C\neq C^{\prime}$, i.e. $k<c$. Then

$\displaystyle(M^{*}M)_{C,C^{\prime}}$
$\displaystyle=\frac{(c-r)(-1)^{r}}{(c-k)\binom{c}{k}}\sum_{i=\max\left\\{0,k+r-c\right\\}}^{\min\left\\{k,r\right\\}}(-1)^{i}\binom{c-i-1}{c-k-1}\binom{c-k}{r-i}$
$\displaystyle=\frac{c-r}{(c-k)\binom{c}{k}}\sum_{j=\max\left\\{0,r-k\right\\}}^{\min\left\\{r,c-k\right\\}}(-1)^{j}\binom{c-r+j-1}{c-k-1}\binom{c-k}{j}.$

From $2c-k=|C\cup C^{\prime}|\leq n\leq r+c$, we get $c-k\leq r$ so that
$\min\\{r,c-k\\}=c-k$. Also, $\binom{c-r+j-1}{c-k-1}=0$ when $j<r-k$. Thus

$(M^{*}M)_{C,C^{\prime}}=\frac{c-r}{(c-k)\binom{c}{k}}\sum_{j=0}^{c-k}(-1)^{j}\binom{c-r+j-1}{c-k-1}\binom{c-k}{j}=0$

by Proposition 2.1 for $\binom{c-r+j-1}{c-k-1}$ is a polynomial of degree less
than $c-k$ in $j$. ∎

######  Theorem 2.3.

$M^{+}=M^{*}$.

###### Proof.

First observe that $MM^{*}$ and $M^{*}M$ are symmetric for any
$(R,R^{\prime})$-entry of $MM^{*}$ and $(C,C^{\prime})$-entry of $M^{*}M$
depends only on the size of intersections $R\cap R^{\prime}$ and $C\cap
C^{\prime}$, respectively. On the other hand, by Lemma 3.5, either $MM^{*}=I$
or $M^{*}M=I$. Therefore $MM^{*}M=M$ and $M^{*}MM^{*}=M^{*}$ so that
$M^{*}=M^{+}$ is the Moore-Penrose inverse of $M$. ∎

Bapat [1] gives necessary and sufficient conditions for $M$ to have a Moore-
Penrose inverse over fields of prime characteristics, and gives an implicit
formula for the Moore-Penrose inverse when it exists. It is evident that
$M^{*}$ is a Moore-Penrose inverse of $M$ over a field of characteristic $p$
when denominators of the given entries are non-zero. Hence, $M^{*}$ yields an
explicit formula for the Moore-Penrose inverse of $M$ over a field of
characteristic $p$ provided that $p$ does not divides
$\binom{N-r}{c-r}\binom{N-c}{0}\cdots\binom{N-c}{r}$, for instance for
$p>\max\\{n-r,c\\}$.

##  3\. Vector space inclusion incidence matrices

Let $r$, $c$, and $n$ be non-negative integers satisfying $0\leq r\leq c\leq
n$ and $q$ be a prime power. The vector space inclusion incidence matrix
$M=M(n,q;r,c)$ is an $\binom{n}{r}_{q}\times\binom{n}{c}_{q}$ matrix defined
as follows: the rows and columns of $M$ are indexed by $r$–dimensional
subspaces and $c$-dimensional subspaces of $GF(q)^{n}$, respectively, with
$(R,C)$-entry equal to $\delta_{R\subseteq C}$. Let $M^{*}$ be the matrix
whose rows and columns are indexed by $c$-dimensional subspaces and
$r$-dimensional subspaces of $GF(q)^{n}$, respectively, and its $(C,R)$-entry
is given by

$M^{*}_{C,R}=(-1)^{r-i}\frac{\binom{c-i-1}{r-i}_{q}}{\binom{N-r}{c-r}_{q}\binom{N-c}{r-i}_{q}}\cdot\frac{1}{q^{(c-r)(r-i)+\binom{r-i}{2}}},$

where $N=\max\\{n,r+c\\}$ and $i=\dim(R\cap C)$. As in the previous section,
we aim to show that $M^{*}$ is the Moore-Penrose inverse of $M$. To this end,
we need to recall some notation and prove some preliminary lemmas.

In what follows, for a non-negative integer $n$ and prime power $q$, $[n]_{q}$
and $[n]_{q}!$ stand for the $q$-integer $(q^{n}-1)/(q-1)$ and the
$q$-factorial $[n]_{q}\cdots[1]_{q}$, respectively. Also, for $0\leq m\leq n$,
the $q$-binomial $[n]_{q}!/[m]_{q}![n-m]_{q}!$ is denoted by
$\binom{n}{m}_{q}$. Note that the $q$-binomial $\binom{n}{m}_{q}$ is defined
to be zero if the condition $0\leq m\leq n$ does not hold.

######  Lemma 3.1.

Let $V$ be a vector space of dimension $n$ over a finite field with $q$
elements and $0\leq k\leq i\leq r\leq c\leq n-r$. Let $R$ and $R^{\prime}$ be
subspaces of $V$ of dimension $r$ with a $k$-dimensional intersection. Then
the number of subspaces $C\supseteq R$ of $V$ of dimension $c$ such that
$C\cap R^{\prime}$ is $i$-dimensional is equal to

$\binom{r-k}{i-k}_{q}\binom{n-2k+r}{c-r-i+k}_{q}q^{(c-r-i+k)(r-i)}.$

###### Proof.

Since $C\supseteq R$ we can work in $V/R$ and assume without loss of
generality that $R=0$. Then $C\cap R^{\prime}$ has dimension $i-k$. Since
$R^{\prime}$ has dimension $r-k$ there are $\binom{r-k}{i-k}$ choices for
$C\cap R^{\prime}$. Passing to the quotient $V/C\cap R^{\prime}$, we can
further assume that $C\cap R^{\prime}=0$. Then $V$, $C$, and $R^{\prime}$ have
dimensions $n-r-i+k$, $c-r-i+k$, and $r-i$, respectively, with $C\cap
R^{\prime}=0$. The number of subspaces $C$ of $V$ with these properties is
equal to

$\binom{n-2k+r}{c-r-i+k}_{q}q^{(c-r-i+k)(r-i)}$

(see [7, Lemma 2.6]), from which the result follows. ∎

######  Lemma 3.2.

Let $V$ be a vector space of dimension $n$ over a finite field with $q$
elements and $0\leq i\leq k\leq r\leq c$. Let $C$ and $C^{\prime}$ be
subspaces of $V$ of dimension $c$ with a $k$-dimensional intersection. Then
the number of subspaces $R\supseteq C^{\prime}$ of $V$ of dimension $r$ such
that $R\cap C$ is $i$-dimensional is equal to

$\binom{k}{i}_{q}\binom{c-k}{r-i}_{q}q^{(r-i)(k-i)}.$

###### Proof.

First observe that there are $\binom{k}{i}$ choices for $R\cap C$ as $R\cap C$
is an $i$-dimensional subspace of $C\cap C^{\prime}$ of dimension $k$. Passing
to the quotient $V/R\cap C$, we can assume without loss of generality that
$R\cap C=0$. Then $R$, $C\cap C^{\prime}$, and $C^{\prime}$, have dimensions
$r-i$, $k-i$, and $c-i$, respectively, with $R\cap(C\cap C^{\prime})=0$. The
number of subspaces $R$ of $V$ with these properties is equal to

$\binom{c-k}{r-i}_{q}q^{(r-i)(k-i)}$

(see [7, Lemma 2.6]), from which the result follows. ∎

In order to obtain a $q$-analogue of Proposition 2.1, we need to use Gauss’
binomial formula.

######  Proposition 3.3 (Gauss’ binomial formula [12, 5.5]).

Let $x$, $a$, and $q$ be real numbers and $n\geq 1$ be a positive integer.
Then

$(x+a)(x+qa)\cdots(x+q^{n-1}a)=\sum_{i=0}^{n}\binom{n}{i}_{q}q^{\binom{i}{2}}a^{i}x^{n-i}.$

######  Corollary 3.4.

Let $n$ be a positive integer. Then

$\sum_{i=0}^{n}(-1)^{i}\binom{n}{i}_{q}\cdot\frac{1}{q^{i(n-i)+\binom{i}{2}}}\cdot
p_{m}(q^{i})=0$

for all polynomials $p_{m}(x)$ of degree $0\leq m<n$.

###### Proof.

The result follows by replacing $x$ by $-q^{m}a$ ($0\leq m<n$) in Gauss’
binomial formula and assuming that $p_{m}(x)=x^{m}$. ∎

Now, we can proceed to show that $M^{*}$ is actually the Moore-Penrose inverse
of $M$ by showing that the results of Lemma 3.5 remain unchanged in the case
of vector space inclusion incidence matrices.

######  Lemma 3.5.

With the notation above, we have

  * (i)

$MM^{*}=I$ if $n\geq r+c$;

  * (ii)

$M^{*}M=I$ if $n\leq r+c$.

###### Proof.

(i) Let $R$ and $R^{\prime}$ be subspaces of $GF(q)^{n}$ of dimension $r$ and
put $k:=\dim(R\cap R^{\prime})$. A simple verification shows that

$(MM^{*})_{R,R^{\prime}}=\sum_{i=k}^{r}(-1)^{r-i}\frac{\binom{r-k}{i-k}_{q}\binom{n-2r+k}{c-r-i+k}_{q}\binom{c-i-1}{r-i}_{q}}{\binom{n-r}{c-r}_{q}\binom{n-c}{r-i}_{q}}\cdot\frac{1}{q^{(i-k)(r-i)+\binom{r-i}{2}}}.$

If $R=R^{\prime}$, then $k=r$ and $(MM^{*})_{R,R^{\prime}}=1$. Now, assume
that $R\neq R^{\prime}$, i.e. $k<r$. Then

$\displaystyle(MM^{*})_{R,R^{\prime}}$
$\displaystyle=\frac{[c-r]_{q}(-1)^{r}}{[r-k]_{q}\binom{n-r}{r-k}_{q}}\sum_{i=k}^{r}(-1)^{i}\binom{c-i-1}{r-k-1}_{q}\binom{r-k}{i-k}_{q}\cdot\frac{1}{q^{(i-k)(r-i)+\binom{r-i}{2}}}$
$\displaystyle=\frac{[c-r]_{q}(-1)^{r-k}}{[r-k]_{q}\binom{n-r}{r-k}_{q}}\sum_{j=0}^{r-k}(-1)^{j}\binom{c-k-j-1}{r-k-1}_{q}\binom{r-k}{j}_{q}\cdot\frac{1}{q^{j(r-k-j)+\binom{r-k-j}{2}}}$
$\displaystyle=\frac{[c-r]_{q}(-1)^{r-k}}{[r-k]_{q}\binom{n-r}{r-k}_{q}}\sum_{l=0}^{r-k}(-1)^{l}\binom{c-r+l-1}{r-k-1}_{q}\binom{r-k}{l}_{q}\cdot\frac{1}{q^{l(r-k-l)+\binom{l}{2}}}=0$

by Corollary 3.4 for $\binom{c-r+l-1}{r-k-1}_{q}$ is a polynomial of order
less than $r-k$ in $q^{l}$.

(ii) Let $C$ and $C^{\prime}$ be subspaces of $GF(q)^{n}$ of dimension $c$ and
put $k:=\dim(C\cap C^{\prime})$. Since $n\leq r+c$, we have $N=r+c$ and
$2c-n\leq k\leq c$. A simple verification shows that

$(M^{*}M)_{C,C^{\prime}}=\sum_{i=\max\\{0,r+k-c\\}}^{\min\\{k,r\\}}(-1)^{r-i}\frac{\binom{k}{i}_{q}\binom{c-k}{r-i}_{q}\binom{c-i-1}{r-i}_{q}}{\binom{c}{r}_{q}\binom{r}{i}_{q}}\cdot\frac{1}{q^{(c-r-k+i)(r-i)+\binom{r-i}{2}}}.$

If $C=C^{\prime}$, then $k=c$ and $(M^{*}M)_{C,C^{\prime}}=1$. Now, suppose
that $C\neq C^{\prime}$, i.e. $k<c$. Then

$\displaystyle(M^{*}M)_{C,C^{\prime}}$
$\displaystyle=\frac{[c-r]_{q}(-1)^{r}}{[c-k]_{q}\binom{c}{k}_{q}}\sum_{i=\max\left\\{0,k+r-c\right\\}}^{\min\left\\{k,r\right\\}}(-1)^{i}\binom{c-i-1}{c-k-1}_{q}\binom{c-k}{r-i}_{q}\cdot\frac{1}{q^{(c-r-k+i)(r-i)+\binom{r-i}{2}}}$
$\displaystyle=\frac{[c-r]_{q}}{[c-k]_{q}\binom{c}{k}_{q}}\sum_{j=\max\left\\{0,r-k\right\\}}^{\min\left\\{r,c-k\right\\}}(-1)^{j}\binom{c-r+j-1}{c-k-1}_{q}\binom{c-k}{j}_{q}\cdot\frac{1}{q^{(c-k-j)j+\binom{j}{2}}}.$

From $2c-k=\dim(C+C^{\prime})\leq n\leq r+c$, we get $c-k\leq r$ so that
$\min\\{r,c-k\\}=c-k$. Also, $\binom{c-r+j-1}{c-k-1}=0$ when $j<r-k$. Thus

$(M^{*}M)_{C,C^{\prime}}=\frac{[c-r]_{q}}{[c-k]_{q}\binom{c}{k}_{q}}\sum_{j=0}^{c-k}(-1)^{j}\binom{c-r+j-1}{c-k-1}_{q}\binom{c-k}{j}_{q}\cdot\frac{1}{q^{(c-k-j)j+\binom{j}{2}}}=0$

by Corollary 3.4 for $\binom{c-r+j-1}{c-k-1}$ is a polynomial of degree less
than $c-k$ in $q^{j}$. ∎

Utilizing the same line of proof as in Theorem 3.6 we can prove the following.

######  Theorem 3.6.

$M^{+}=M^{*}$.

As in the previous section, $M^{*}$ yields an explicit formula for the Moore-
Penrose inverse of $M$ over a field of characteristic $p$ provided that $p$
does not divides
$\binom{N-r}{c-r}_{q}\binom{N-c}{0}_{q}\cdots\binom{N-c}{r}_{q}q$, for
instance for any $p>\max\\{n-r,c\\}$ not dividing $q$.

##  4\. $t$-Design inclusion incidence matrices

A $t-(v,k,\lambda)$ design $\mathcal{D}$ is a collection of blocks as
$k$-subsets of a $v$-element set, say $[v]$, such that every $t$-subset of
$[v]$ belongs to $\lambda$ blocks. It is known that every $t-(v,k,\lambda)$
design is an $s-(v,k,\lambda_{s})$, where

$\lambda_{s}=\lambda\cdot\frac{\binom{v-s}{t-s}}{\binom{k-s}{t-s}}$

for all $0\leq s\leq t$. Let $b:=\lambda\binom{v}{t}/\binom{k}{t}$ be the
number of blocks in $\mathcal{D}$. For any $0\leq s\leq t$, let
$M_{s}:=M_{s}(t,v,k,\lambda)$ be the $\binom{v}{s}\times b$ matrix defined as
follows: rows and columns of $M$ are indexed by $s$-subsets of $[v]$ and
blocks, respectively, with $(R,C)$-entry equal to $\delta_{R\subseteq C}$. It
is a well-known result that
$M_{1}M_{1}^{T}=(\lambda_{1}-\lambda_{2})I+\lambda_{2}J$, where $I$ and $J$
are the identity matrix and the matrix of all $1$’s with appropriate sizes,
respectively. Using this fact, we can simply compute the Moore-Penrose inverse
of the point-block incidence matrix $M_{1}$ of block designs.

######  Proposition 4.1.

We have $M_{1}^{+}=M_{1}^{T}((\lambda_{1}-\lambda_{2})I+\lambda_{2}J)^{-1}$.
More precisely,

$(M_{1}^{+})_{B,u}=\begin{cases}\frac{1}{\lambda_{1}},&u\in B,\\\
-\frac{1}{\lambda_{1}}\cdot\frac{k-1}{v-k},&u\notin B.\end{cases}$

###### Proof.

We know from [2, Lemma 4.4] that the $n\times n$ matrix $xI+yJ$ is an
invertible matrix if and only if $x(x+ny)\neq 0$, from which it follows that
$X:=(\lambda_{1}-\lambda_{2})I+\lambda_{2}J$ is an invertible matrix. Since
$M_{1}(M_{1}^{T}X^{-1})=I$ we observe that

$M_{1}(M_{1}^{T}X^{-1})M_{1}=M_{1}\quad\text{and}\quad(M_{1}^{T}X^{-1})M_{1}(M_{1}^{T}X^{-1})=M_{1}^{T}X^{-1}.$

On the other hand, $(M_{1}^{T}X^{-1})M_{1}$ is symmetric as $X$ is a symmetric
matrix. Thus $M_{1}^{T}X^{-1}=M_{1}^{+}$. Now, we compute the entries of
$M_{1}^{+}$. Let $u$ be a point and $B$ be a block. First observe that the
inverse of an invertible matrix of the form $xI+yJ$ is equal to
$\frac{1}{x}I-\frac{y}{x(x+ny)}J$. For $u\notin B$, we have

$\displaystyle(M_{1}^{+})_{B,u}$
$\displaystyle=(M_{1}^{T}X^{-1})_{B,u}=\sum_{v\in B}(X^{-1})_{v,u}$
$\displaystyle=-\frac{k\lambda_{2}}{(\lambda_{1}-\lambda_{2})(\lambda_{1}-\lambda_{2}+v\lambda_{2})}=-\frac{1}{\lambda_{1}}\cdot\frac{k-1}{v-k}$

as $\lambda_{2}=(k-1)/(v-1)\lambda_{1}$. Also, for $u\in B$, we get

$\displaystyle(M_{1}^{+})_{B,u}$
$\displaystyle=(M_{1}^{T}X^{-1})_{B,u}=\sum_{v\in B}(X^{-1})_{v,u}$
$\displaystyle=\frac{1}{\lambda_{1}-\lambda_{2}}-\frac{k\lambda_{2}}{(\lambda_{1}-\lambda_{2})(\lambda_{1}-\lambda_{2}+b\lambda_{2})}$
$\displaystyle=\frac{1}{\lambda_{1}-\lambda_{2}}-\frac{1}{\lambda_{1}}\cdot\frac{k-1}{v-k}=\frac{1}{\lambda_{1}},$

as required ∎

Unexpectedly, the Moore-Penrose inverse of matrices $M_{s}$ when $s\geq 2$ not
only depends on the parameters $t$, $v$, $k$, $\lambda$, but also depends on
the internal structure of the designs. Indeed, a computer search reveals that
for every set of small parameters $t$, $v$, $k$, $\lambda$ for which all block
designs are classified (see design theory database [17]) the matrix
$M_{s}^{+}$ of any design receive uniquely determined set of entries with few
exceptions.

## References

  * [1] R. B. Bapat, Moore-Penrose inverse of set inclusion matrices, Linear Algebra Appl. 318 (2000), 35–44.
  * [2] R. B. Bapat, Graphs and Matrices, Second Edition, Universitext, Springer, London; Hindustan Book Agency, New Delhi, 2014.
  * [3] M. Bardoe and P. Sin, The permutation modules for $GL(n+1,F_{q})$ acting on $P^{n}(F_{q})$ and $F^{n-1}_{q}$, J. London Math. Soc. 61 (2000), 58–80.
  * [4] T. Beth, D. Jungnickel, and H. Lenz, Design Theory, Cambridge University Press, Cambridge, MA, 1993.
  * [5] S. L. Campbell and C. D. Meyer, Generalized Inverses of Linear Transformations, Pitman, London, 1979.
  * [6] D. B. Chandler, P. Sin, and Q. Xiang, The invariant factors of the incidence matrices of points and subspaces in $PG(n,q)$ and $AG(n,q)$, Trans. Amer. Math. Soc. 358 (2006), 4935–4957.
  * [7] M. Farrokhi D. G., Factorization numbers of finite abelian groups, Int. J. Group Theory, 2(2) (2013), 1–8.
  * [8] P. Frankl, Intersection theorems and mod $p$ rank of inclusion matrices, J. Combin. Theory Ser. A 54 (1990) 85–94.
  * [9] P. Hall, The Eulerian functions of a group, Quarterly J. Math. 7(1) (1936), 134–151.
  * [10] N. Hamada, The rank of the incidence matrix of points and $d$-flats in finite geometries, J. Sci. Hiroshima Univ. Ser. A-I Math. 32 (1968), 381–396.
  * [11] A. Ben-Israel and T. N. E. Greville, Generalized Inverses: Theory and Applications, Second Edition, CMS Books in Mathematics, Springer, 2003.
  * [12] V. Kac and P. Cheung, Quantum Calculus, Universitext, Springer-Verlag, New York, 2002.
  * [13] E. Moore, On the reciprocal of the general algebraic matrix, Bull. Amer. Math. Soc. 26 (1920), 394–395.
  * [14] R. Penrose, A generalized inverse for matrices, Proc. Cambridge Philos. Soc. 51 (1955), 406–413.
  * [15] G. Rota, On the foundations of combinatorial theory I, Theory of Möbius functions, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1964), 340–368.
  * [16] S. M. Ruiz, An algebraic identity leading to Wilson’s theorem, Math. Gaz. 80 (1996), 579–582.
  * [17] L. H. Soicher, Design Theory Database, http://www.maths.qmul.ac.uk/~lsoicher/designtheory.org/database/t-designs/
  * [18] L. Weisner, Abstract theory of inversion of finite series, Trans. Amer. Math. Soc. 38(3) (1935), 474–484.
  * [19] L. Weisner, Some properties of prime-power groups, Trans. Amer. Math. Soc. 38(3) (1935), 485–492.
  * [20] R. M. Wilson, Incidence matrices of $t$-designs, Linear Algebra Appl. 46 (1982) 73–82.
  * [21] R. M. Wilson, A diagonal form for the incidence matrices of $t$-subsets vs. $k$-subsets, European J. Combinatorics 11 (1990), 609–615.