# UTNLP at SemEval-2021 Task 5: A Comparative Analysis of Toxic Span Detection
using Attention-based, Named Entity Recognition, and Ensemble Models

Alireza Salemi, Nazanin Sabri, Emad Kebriaei, Behnam Bahrak, Azadeh Shakery
School of Electrical and Computer Engineering, College of Engineering
University of Tehran, Tehran, Iran
<EMAIL_ADDRESS>
###### Abstract

Detecting which parts of a sentence contribute to that sentence’s
toxicity—rather than providing a sentence-level verdict of hatefulness—would
increase the interpretability of models and allow human moderators to better
understand the outputs of the system. This paper presents our team’s, UTNLP,
methodology and results in the SemEval-2021 shared task 5 on toxic spans
detection. We test multiple models and contextual embeddings and report the
best setting out of all. The experiments start with keyword-based models and
are followed by attention-based, named entity-based, transformers-based, and
ensemble models. Our best approach, an ensemble model, achieves an F1 of 0.684
in the competition’s evaluation phase.

##  1 Introduction

When social media platforms were first introduced, they allowed users to post
content on any topic they wished, without restricting the type of content they
were allowed to put out. This absence of restrictions, along with the
anonymity of users through these platforms Pinsonneault and Heppel (1997);
Mondal et al. (2017), resulted in the spread of offensive language and hate
speech online. While one might think there are only a small number of users
who produce these types of hateful content, it has been shown that if social
media platforms are left unmoderated, over time, the language of the community
as a whole will change such that it highly correlates with the speech of
hateful users rather than non-hateful ones Mathew et al. (2020). Given the
huge number of social media postings every day, manual moderation of these
platforms is not a possibility. As a result, many researchers began to study
automatic hate speech detection.
Most studies on hate speech detection only provide labels at the sentence
level, showing whether the construct as a whole is toxic or not. But these
types of models, offer little explanation as to why the class was predicted,
making it hard for human moderators to interpret the results Pavlopoulos et
al. .
In an attempt to solve the aforementioned issue, we took part in SemEval-2021
shared task 5 Pavlopoulos et al. (2021), where we aim to detect which spans of
a sentence cause it to become toxic. Our contributions are as follows: We
begin our experimentation by evaluating a random baseline. Next, we test
keyword-based methods, trying to find if toxic spans often include words that
are known as hateful or negative in available word lists. We then test
attention-based models, building on the hypothesis that what the attention
model learns to focus on when detecting toxic speech, are the toxic spans.
Afterwards, we look at the issue as a named entity recognition problem, by
considering _toxic_ as a named entity category. Finally, we fine tune T5-base
and explore the possibility of looking at the task as a text-to-text problem.
We compare different neural network architectures and embeddings, and report
the model with the best performance. Additionally, we experiment with some
hand-crafted features and evaluate their effectiveness in detecting toxic
spans. Our best result, an ensemble of named-entity-based models, achieves an
F1 of 0.684.

##  2 Related Work

In this section we provide a brief overview of studies on hate and toxic
speech detection, followed by work on span detection in different sub-fields.

###  2.1 Hate Speech

Hate speech is defined as “any communication that disparages a person or a
group on the basis of some characteristic such as race, color, ethnicity,
gender, sexual orientation, nationality, religion, or other characteristics”
Nockleby (2000). However, no clear distinction between toxic and hateful
speech has been provided in the scientific literature D’sa et al. (2019).
There are quite a few surveys on the topic of hate speech detection. Schmidt
and Wiegand (2017), describes available methods, features, and models for such
a task. Another survey conducted in 2018 Fortuna and Nunes (2018), offers
another view of the current state of the field, as well as suggesting ways in
which hate speech detection could advance further. Other surveys on the topic
published in 2020 include: Naseem et al. (2020) which examines the impact of
pre-processing on the performance of hate speech models. Corpora and resources
for the task are studied in Poletto et al. (2020). Additionally, throughout
the years, many shared tasks have been organized to help propel studies in the
field Vu et al. (2020); Bosco et al. (2018); Basile et al. (2019). In addition
to the classification of hate speech, significant effort has been put into the
analysis of the target of hate Silva et al. (2016); ElSherief et al. (2018).
Although numerous models have been tested, Gröndahl et al. (2018) argues that
when it comes to hate speech detection, the model is less important than the
labeling criteria and the type of data. In confirmation of the importance of
labeling, Arango et al. (2019) also finds that models trained on annotations
done by experts outperform systems trained on amateur annotations.

###  2.2 Span Detection

Named entity recognition (NER), code-switching detection, quotation detection,
and key-phrase extraction are among many tasks that involve span
identification.
Chen et al. (2020) employs SpanBERT Joshi et al. (2020) accompanied by a
sequence tagging model to detect erroneous spans, proceeding to use detected
spans to perform error correction. The combination of conditional random
fields (CRF) Lafferty et al. (2001) and attention mechanisms Vaswani et al.
(2017) are explored in Xu et al. (2020) to explore aspect sentiment
classification. The study finds that the use of multiple CRFs (to some limit)
does improve performance. In Papay et al. (2020) the authors look into systems
to predict the performance of span identification tasks. To do so, BIO labels
are used, and it is found that BERT Devlin et al. (2018) helps when there is
little data, while CRF is of great help in hard cases. In addition, the
frequency of spans is found to help while length hurts the performance of the
model. Furthermore, LSTMs Hochreiter and Schmidhuber (1997) are reported to
require large amounts of data to learn. Tang et al. (2019) explores using
fine-tuned BERT with attention models to extract keywords, showing how such
models could enable the text classification model to be human interpretable.

##  3 Data

In this section, we will provide a brief description of the datasets utilized
in this study. We will begin with our main dataset in which span-level
toxicity has been labeled (3.1), next we look at other datasets that were used
to better train our models, namely the hate word list that was used (3.2.1)
and the sentence-level hate speech data (3.2.2).

###  3.1 Main Task Dataset: Toxic Spans

The main dataset used in this study is that of the SemEval 2021, Toxic Span
detection task Pavlopoulos et al. ; Borkan et al. (2019a). In this dataset,
which was built upon Civil Comments Borkan et al. (2019b), toxic word
sequences (for sentences in the English language) have been labeled. In other
words, labels are indexes of characters that are toxic in each sentence. There
are a total of 8,629 sentences in the dataset, 8,101 of which include at least
one annotated toxic span, and the rest have none. Sentences are on average 35
words long. The word-length of the toxic spans varies from one to 176 words.
Toxic spans are, on average, 2.29 words long.
There are some issues with regard to the quality of the annotations in the
dataset. Table 1 shows some examples of annotated comments in the dataset.
While the first sentence is satisfactorily annotated, the second and third
examples display issues with the labels in the dataset. More concretely, in
the second example we can see that the indexes result in poorly separated and
broken up words. Additionally, the anotated words are not toxic. In the third
example we see that some of the words which do have a toxic connotation are
not included in the annotation. While these examples are not extremely common
in the dataset, these types of issues make automatic detection of such spans
much more difficult.

Table 1: Examples of comments and the annotated toxic spans in the dataset Text | Toxic Spans
---|---
what load you trump chumps just do not have any idea how to |
deal with reality you have terrible judgment and pick exceptionally |
idiotic arrogant leaders trump admitted he fired comey to stop |
the russia investigation man is he stupid. | [’idiotic’, ’man is he stupid’]
except for one thing they are liars they only care about being thugs | [’r one th’]
what harm have you ever heard of someone getting attacked |
by bear while taking dump in the woods please does just owning gun make |
someone paranoid and pu55y at the same time | [’harm’]

###  3.2 Datasets Used for Training

To better train our models, we made use of several auxiliary datasets.

####  3.2.1 Word-list Dataset

One of the methods tested in this study is based on word-matching. In other
words, we check whether each word in the sentence is among hateful words and
if so predict its label to be toxic. While this method is rather simple and we
acknowledge that not all hate words are toxic and they could simply be used as
a joke, we consider this method as a good first step to help us better
understand the task at hand. As a result we need to use a list of hate words.
For that purpose, we used a list of 1,616 unique hate words found on Kaggle
nicapotato .

####  3.2.2 Hate Speech Dataset

To be able to train our attention-based models (4.1) we needed to have
sentence-level annotated data. Thus we used the Civil Comments dataset Jigsaw-
Conversation-AI . The fact that this dataset and our main dataset have the
same domain is the reason why this specific dataset was selected. In this
dataset, each sentence is labeled with a number between 0 and 1, representing
how hateful the text is. We consider sentences with scores above 0.5 to be
hateful, and consider the rest as non-hateful. We then create a balanced
sample of 289,298 sentences to train our model. The average length of
sentences in this dataset is 48.12 words which is slightly longer than the
sentences in the main dataset (3.1).

##  4 Methodology

In this study we have tested and compared various models to perform toxic span
detection. In this section we will go over the structure and hyperparameters
of these models. The codes of all models are publicly available on
GitHub111https://github.com/alirezasalemi7/SemEval2021-Toxic-Spans-Detection.

###  4.1 Attention-based Methods

We begin with the intuition that if a model with an attention layer is trained
to detect hate speech at the sentence-level, the words the attention layer
would learn to place importance on, would be the hateful words and spans.
Consequently, we create a model made up of the following three layers:
(1) BERT-Base (Uncased) Layer which encodes our input texts.
(2) Attention Layer which is meant to be used for the aforementioned purposes
(3) Dense Layers which connect the attention outputs to two output nodes,
detecting if the text is hateful or not.
To train this model we have two training stages:

  * •

Sentence-level classification of hate speech

  * •

Span-level detection of toxic spans

First we perform pre-processing by removing all punctuations (except those in
the middle of words such as a$$hole), and lower-casing all words.
Next, the aforementioned model is designed. The BERT-Base (Uncased) layer has
an input size of 400 tokens (clipping the input at 400 tokens and dropping the
rest). The outputs of this layer are embedding vectors with a hidden size of
768 corresponding to the 400 input tokens. The second layer is an attention
layer (attention matrix size = 4096) with a Relu activation function. Our last
layers are two fully connected layers (4096 nodes) with dropout of 0.1. There
are two neurons in the final layer, the objective of which is to detect
whether the sentence is an instance of hate speech or not. The model is
trained for 10 epochs with the Adam optimizer and a learning rate of 0.001. We
freeze the weights of the BERT layer during this training process as we find
through experimentation that fine-tuning BERT in this stage results in lower
performance of our model in the toxic span detection task.
Once the model has been trained, we input our sentence and if our sentence-
level detector predicts the sentence to be non-hateful we move on and produce
a blank output as our toxic span. If, however, the model detects the sentence
to be hateful, we extract the attention values and calculate the attention
score of each word. If a word is made up of multiple subwords, we average the
values of all subwords. After the attention scores have been calculated we use
rule-based and machine learning models to label spans as toxic. These models
are explained in Table 2. We begin by rule based models, selecting a
percentage of spans with attention scores above a certain threshold (shown in
Figure 2). Additionally, we test different machine learning models with
various sets of features. Our results are shown in Section 5.3.

###  4.2 Named Entity-based Methods

Our second intuition is to look at this problem as one similar to NER. As
such, our toxic span label can be looked at as another NER label. We
considered toxic, non-toxit and padding as labels and applied CRF to this NER
task. The padding label was added to reduce the model bias toward the non-
toxic class.
Our model is depicted in Figure 1. We train the model for 2 epochs with a
learning rate of $3\times 10^{-5}$. In contrast to the previous method, the
embedding layer is fine-tuned during our training process. Our tests on these
models are shown in Section 5.4.

Figure 1: The architecture of the named entity-based models. (a) displays a
version of the model in which the two dense layers in (b) have been replaced
by an LSTM layer. The results of both versions are shown in Table 3.

###  4.3 Ensemble Models

Finally, we test two methods of combining the outputs of various models in
order to achieve a better performance on the task. As previously mentioned,
the expected outputs of the task are numerical indexes of the parts of the
string which are believed to be toxic. Consequently, the first method of
mixing could be voting, where if the majority of the models vote for one
index, the index is included in the final selection. The second method is
based on calculating the intersection of outputted indexes of all three
models. In other words, only adding an index if it is detected by all three
models. The results are shown in Section 5.6.

##  5 Results

In this section we will report the results of the models introduced in the
previous section (4) on the toxic span detection task. Per the competition
evaluation instructions, for all models the F1 score is reported.

###  5.1 Random Baseline

To help us better understand the complexity of the task at hand, we start with
a random baseline. In this method, we first split each sentence into words
(using NLTK’s functions) and then randomly label each word as toxic or not. We
observe that this baseline F1-score for the task is 0.17.

###  5.2 Keyword-based

The second simple method we test is a word-matching one. Our intuition is that
toxic spans will likely include hateful or negative words. Thus we begin with
a list of hate words and label any word found on the list as toxic and label
the rest as nontoxic. This method results in an F1-score of 0.332 which is
almost twice that of the random baseline, showing that while not all hate
words are toxic and not all toxic spans are hate words, there is still a
considerable amount of overlap. We further test if most words in toxic spans
will have a negative sentiment value. Thus we repeat the same method, this
time labeling anything with a negative sentiment as toxic. To detect the
sentiment score of each word we use TextBlob Loria (2018). We see that this
method achieves an F1 of 0.378, outperforming the aforementioned technique.
Finally we mix the two methods (labeling both hate words and words with
negative sentiment as toxic), and achieve an F1-score of 0.418.

###  5.3 Attention-based

As mentioned in Section 4, the intuition behind the attention-based model is
that the model which learns to detect hate speech, would learn to pay more
attention to the hateful spans in the text. Consequently, we test this idea in
Table 2. We can see that the rule-based attention selection method outperforms
other span selection techniques. To select the best set of rules for the
model, we test both the percentage of top-words (with respect to attention)
which we consider for selection, and the threshold we place on the minimum
value of attention which is considered. As shown in Figure 2, we can see that
the top 75% of attention scores with a threshold of $10^{-4}$ is the best set
of hyper-parameters for the task.

Figure 2: The effects of placing various thresholds on the minimum value of
attention scores allowed to be selected and the percentage of top scores that
have been selected on the F1-score of the toxic span detection task. Each plot
displays one threshold value, and the x-axis in each plot is the percentile of
scores we select and the y-axis is the F1 value achieved by this combination
of threshold and percentile. Table 2: Results of the attention-based models,
the model structure is BERT + Attention + Dense and we have tested out
different span selection rules

Model | Hate Speech Detection | Toxic Span Detection
---|---|---
Span Selection Rules | Accuracy | Precision | Recall | F1 | F1 | F1 (Competition Evaluation)
R1 a |  |  |  |  | 0.601 | 0.609
R2 b |  |  |  |  | 0.601 | -
R3 c | 0.85 | 0.85 | 0.85 | 0.85 | 0.496 | -
Decision Tree d |  |  |  |  | 0.360 | -
Neural Network e |  |  |  |  | 0.354 | -

  * a

R1: selecting words with top 75% of attention scores with threshold $10^{-4}$
and then removing stop-words

  * b

R2: R1 + removing positive sentiment words among the top 75%

  * c

R3: R2 + adding all hate words (using the hate word list) in the sentence
regardless of attention scores

  * d

Decision Tree: the input features of the model are: 1-attention score of word,
2-part of speech of the word, 3-sentiment of word 4-whether the word is a hate
word or not (0/1)

  * e

Neural Network: the features inputted to the model are 1-attention score of
word, 2-part of speech of the word, 3-sentiment of word, 4-whether the word is
a hate word or not (0/1) - categorical features (e.g. POS) are modeled as
learnable embeddings.

Upon analysis of the results of the attention-based model, we find that the
model performs well on the detection of single word spans (detecting 78% of
single-word spans in the evaluation dataset) but does not detect multi-word
spans well (only detecting 16% of such spans completely). This is because the
distribution of attention scores are observed to be such that there is a large
focus on one word and other words receive little attention values.
We further set up another experiment where we assumed that the true sentence-
level labels were given. The model then predicted the toxic spans given these
true labels achieving an F1 of 0.808. This shows that if the sentence-level
classifier performed better, our model would have been able to get higher
performance. Thus, more focus should be placed on obtaining higher accuracy in
the sentence-level classification task.

###  5.4 Named Entity-based

Table 3, displays the results of our named entity based models. We can see
that LSTM layers do not improve performance, and among various embeddings,
RoBERTa outperforms the others in our 5-fold cross validation testings.
However, BERT achieves better results in the competition’s evaluation phase.

Table 3: Results of the named-entity based models evaluated using 5-fold cross-validation Embedding | Layers | F1 (train) | F1 (test) | F1 (Competition Evaluation)
---|---|---|---|---
BERT | CRF | 0.702 | 0.648 | 0.67
RoBERTa | CRF | 0.682 | 0.652 | 0.66
Electra | CRF | 0.687 | 0.646 | 0.65
BERT | LSTM + CRF | 0.668 | 0.62 | -
RoBERTa | LSTM + CRF | 0.669 | 0.647 | -
Electra | LSTM + CRF | 0.678 | 0.641 | -

###  5.5 Google’s T5

Another model we test is Google’s T5 Raffel et al. (2019). To test the T5
model, we use hugging-face’s T5-base model222We were not able to test a larger
version of the model due to system constraints and frame our problem as one
where the context is the Tweet text and the answer is the text of the toxic
spans to be detected. Our model achieves an F1 of 0.635 in the evaluation
phase of the competition.

###  5.6 Ensemble Models

As described in section 4.3, we tested intersecting and using a voting scheme
for the model outputs. More precisely, we perform these methods on the outputs
of the following named entity based models:

  * (1)

BERT + CRF

  * (2)

Electra + CRF

  * (3)

RoBERTa + CRF

We find that the competition evaluation F1 reaches 0.681 when we use voting of
indexes, and 0.684 when the indexes are intersected. As can be seen both
methods outperform all individual models.

##  6 Conclusion

In this study we presented and compared various methods for toxic span
detection. We examined the problem from various points of views reporting our
results using each model. Our best system, an ensemble model, achieved an F1
of 0.684 in the SemEval-2021 Task 5 evaluation phase. Among the named-entity-
based models, BERT+CRF performs best achieving an F1 of 0.67. Our attention-
based model achieved an F1 of 0.609 in the competition’s evaluation phase.
Future work could focus on the improvement of the sentence-level detection in
our attention scheme, as we showed improvement in that regard would improve
this task’s performance.

## References

  * Arango et al. (2019) Aymé Arango, Jorge Pérez, and Barbara Poblete. 2019.  Hate speech detection is not as easy as you may think: A closer look at model validation.  In _Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval_ , pages 45–54.
  * Basile et al. (2019) Valerio Basile, Cristina Bosco, Elisabetta Fersini, Nozza Debora, Viviana Patti, Francisco Manuel Rangel Pardo, Paolo Rosso, Manuela Sanguinetti, et al. 2019.  Semeval-2019 task 5: Multilingual detection of hate speech against immigrants and women in twitter.  In _13th International Workshop on Semantic Evaluation_ , pages 54–63. Association for Computational Linguistics.
  * Borkan et al. (2019a) Daniel Borkan, Lucas Dixon, Jeffrey Sorensen, Nithum Thain, and Lucy Vasserman. 2019a.  Nuanced metrics for measuring unintended bias with real data for text classification.  In _Companion Proceedings of The 2019 World Wide Web Conference_ , pages 491–500.
  * Borkan et al. (2019b) Daniel Borkan, Lucas Dixon, Jeffrey Sorensen, Nithum Thain, and Lucy Vasserman. 2019b.  Nuanced metrics for measuring unintended bias with real data for text classification.  _CoRR_ , abs/1903.04561.
  * Bosco et al. (2018) Cristina Bosco, Dell’Orletta Felice, Fabio Poletto, Manuela Sanguinetti, and Tesconi Maurizio. 2018.  Overview of the evalita 2018 hate speech detection task.  In _EVALITA 2018-Sixth Evaluation Campaign of Natural Language Processing and Speech Tools for Italian_ , volume 2263, pages 1–9. CEUR.
  * Chen et al. (2020) Mengyun Chen, Tao Ge, Xingxing Zhang, Furu Wei, and Ming Zhou. 2020.  Improving the efficiency of grammatical error correction with erroneous span detection and correction.  _arXiv preprint arXiv:2010.03260_.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * D’sa et al. (2019) Ashwin Geet D’sa, Irina Illina, and Dominique Fohr. 2019.  Towards non-toxic landscapes: Automatic toxic comment detection using dnn.  _arXiv preprint arXiv:1911.08395_.
  * ElSherief et al. (2018) Mai ElSherief, Vivek Kulkarni, Dana Nguyen, William Yang Wang, and Elizabeth Belding. 2018.  Hate lingo: A target-based linguistic analysis of hate speech in social media.  _arXiv preprint arXiv:1804.04257_.
  * Fortuna and Nunes (2018) Paula Fortuna and Sérgio Nunes. 2018.  A survey on automatic detection of hate speech in text.  _ACM Computing Surveys (CSUR)_ , 51(4):1–30.
  * Gröndahl et al. (2018) Tommi Gröndahl, Luca Pajola, Mika Juuti, Mauro Conti, and N Asokan. 2018.  All you need is” love” evading hate speech detection.  In _Proceedings of the 11th ACM Workshop on Artificial Intelligence and Security_ , pages 2–12.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long short-term memory.  _Neural computation_ , 9(8):1735–1780.
  * (13) Jigsaw-Conversation-AI.  _Detect toxicity across a diverse range of conversations_.  https://cutt.ly/XhOYKPR.
  * Joshi et al. (2020) Mandar Joshi, Danqi Chen, Yinhan Liu, Daniel S Weld, Luke Zettlemoyer, and Omer Levy. 2020.  Spanbert: Improving pre-training by representing and predicting spans.  _Transactions of the Association for Computational Linguistics_ , 8:64–77.
  * Lafferty et al. (2001) John Lafferty, Andrew McCallum, and Fernando CN Pereira. 2001.  Conditional random fields: Probabilistic models for segmenting and labeling sequence data.
  * Loria (2018) Steven Loria. 2018.  textblob documentation.  _Release 0.15_ , 2.
  * Mathew et al. (2020) Binny Mathew, Anurag Illendula, Punyajoy Saha, Soumya Sarkar, Pawan Goyal, and Animesh Mukherjee. 2020.  Hate begets hate: A temporal study of hate speech.  _Proceedings of the ACM on Human-Computer Interaction_ , 4(CSCW2):1–24.
  * Mondal et al. (2017) Mainack Mondal, Leandro Araújo Silva, and Fabrício Benevenuto. 2017.  A measurement study of hate speech in social media.  In _Proceedings of the 28th acm conference on hypertext and social media_ , pages 85–94.
  * Naseem et al. (2020) Usman Naseem, Imran Razzak, and Peter W Eklund. 2020.  A survey of pre-processing techniques to improve short-text quality: a case study on hate speech detection on twitter.  _Multimedia Tools and Applications_ , pages 1–28.
  * (20) nicapotato.  _Bad Bad Words_.  https://www.kaggle.com/nicapotato/bad-bad-words.
  * Nockleby (2000) JT Nockleby. 2000.  ‘hate speech in encyclopedia of the american constitution.
  * Papay et al. (2020) Sean Papay, Roman Klinger, and Sebastian Padó. 2020.  Dissecting span identification tasks with performance prediction.  _arXiv preprint arXiv:2010.02587_.
  * (23) John Pavlopoulos, Ion Androutsopoulos, Jeffrey Sorensen, and Léo Laugier.  _Toxic Spans Detection_.  https://sites.google.com/view/toxicspans.
  * Pavlopoulos et al. (2021) John Pavlopoulos, Léo Laugier, Jeffrey Sorensen, and Ion Androutsopoulos. 2021\.  Semeval-2021 task 5: Toxic spans detection (to appear).  In _Proceedings of the 15th International Workshop on Semantic Evaluation_.
  * Pinsonneault and Heppel (1997) Alain Pinsonneault and Nelson Heppel. 1997.  Anonymity in group support systems research: A new conceptualization, measure, and contingency framework.  _Journal of Management Information Systems_ , 14(3):89–108.
  * Poletto et al. (2020) Fabio Poletto, Valerio Basile, Manuela Sanguinetti, Cristina Bosco, and Viviana Patti. 2020.  Resources and benchmark corpora for hate speech detection: a systematic review.  _Language Resources and Evaluation_ , pages 1–47.
  * Raffel et al. (2019) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2019.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _arXiv preprint arXiv:1910.10683_.
  * Schmidt and Wiegand (2017) Anna Schmidt and Michael Wiegand. 2017.  A survey on hate speech detection using natural language processing.  In _Proceedings of the Fifth International workshop on natural language processing for social media_ , pages 1–10.
  * Silva et al. (2016) Leandro Silva, Mainack Mondal, Denzil Correa, Fabrício Benevenuto, and Ingmar Weber. 2016.  Analyzing the targets of hate in online social media.  _arXiv preprint arXiv:1603.07709_.
  * Tang et al. (2019) Matthew Tang, Priyanka Gandhi, Md Ahsanul Kabir, Christopher Zou, Jordyn Blakey, and Xiao Luo. 2019.  Progress notes classification and keyword extraction using attention-based deep learning models with bert.  _arXiv preprint arXiv:1910.05786_.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _Advances in neural information processing systems_ , 30:5998–6008.
  * Vu et al. (2020) Xuan-Son Vu, Thanh Vu, Mai-Vu Tran, Thanh Le-Cong, and Huyen Nguyen. 2020.  Hsd shared task in vlsp campaign 2019: Hate speech detection for social good.  _arXiv preprint arXiv:2007.06493_.
  * Xu et al. (2020) Lu Xu, Lidong Bing, Wei Lu, and Fei Huang. 2020.  Aspect sentiment classification with aspect-specific opinion spans.  _arXiv preprint arXiv:2010.02696_.


Smaller Gershgorin disks for multiple eigenvalues for complex matrices

Imre Bárány1 and József Solymosi2

1Alfréd Rényi Institute of Mathematics, Budapest

2University of British Columbia, Vancouver and Obuda University, Budapest

###### Abstract.

Extending an earlier result for real matrices we show that multiple
eigenvalues of a complex matrix lie in a reduced Gershgorin disk. One
consequence is a slightly better estimate in the real case. Another one is a
geometric application. Further results of a similar type are given for normal
and almost symmetric matrices.

##  1\. Introduction

Gershgorin’s classic result [10] has been a major tool to estimate the
eigenvalues of an $n\times n$ (complex) matrix $A=(a_{i,j})_{i,j=1}^{n}$ for
the last 90 years. It says that if $\lambda$ is an eigenvalue of $A$, then
there is $i\in[n]:=\\{1,\ldots,n\\}$ such that

$|a_{i,i}-\lambda|\leqslant\sum_{j\neq i}|a_{i,j}|.$

In other words $\lambda$ lies in the Gershgorin disk $D(a_{i,i},R_{i})$ in the
complex plane for some $i\in[n],$ where $a_{i,i}$ is the centre, and
$R_{i}=\sum_{j\neq i}|a_{i,j}|$ is the radius of the disk. Equivalently, every
eigenvalue $\lambda$ of $A$ satisfies

(1.1) $\lambda\in\bigcup_{i=1}^{n}D(a_{i,i},R_{i}).$

In other words $\lambda\notin\bigcup_{i=1}^{n}D(a_{i,i},R_{i})$ implies that
${\rm rank}(A-\lambda I)=n,$ where $I$ stands for the $n\times n$ unit matrix.

In particular, if

(1.2) $|a_{i,i}|>\sum_{j\neq i}|a_{i,j}|\mbox{ for every }i\in[n],$

then $0\notin\bigcup_{i=1}^{n}D(a_{i,i},R_{i})$ and so the matrix is not
singular. Matrices satisfying (1.2) are called diagonally dominant matrices.
This is a classical application of Gershgorin’s theorem: diagonally dominant
matrices have full rank, that is, zero is not an eigenvalue because no
Gershgorin disk contains the origin. There are various generalizations of
Gershgorin’s theorem see for instance Alon [2] and Alon and Solymosi [3] that
imply this case of diagonally dominant matrices.

Under some special conditions, the Gershgorin bound has recently been improved
by Bárány and Solymosi [5] followed by Hall and Marsli [11]. Assume $A$ is an
$n\times n$ real matrix and let $t_{i}$ denote the median of the numbers
$a_{i,1},\ldots,a_{i,i-1},0,a_{i,i+1},\ldots,a_{i,n}$ (here $a_{i,i}$ is
replaced by $0$) and set $r_{i}=|t_{i}|+\sum_{j\neq i}|a_{i,j}-t_{i}|.$ It is
easy to see (check Section 3 for an argument) that both $t_{i}$ and $r_{i}$
can be determined explicitly.

The following result is implicit in [5]; see the inequality in the last lines
of page 3 there. A detailed proof appears in Hall and Marsli [11].

######  Theorem 1.1.

Assume $\lambda$ is an eigenvalue of the real matrix $A$ whose geometric
multiplicity is at least 2. Then $\lambda\in\bigcup_{1}^{n}D(a_{i,i},r_{i}).$

A similar result was proved much earlier, in 1954, by Ky Fan and Hoffman [7].
They again require geometric multiplicity, but allow (geometric) multiplicity
higher than $2$ and the corresponding radius is given in different terms. They
say that it was Hadamard who discovered the basic case of Gershgorin’s
theorem, namely that condition (1.1) implies ${\rm rank}\,A=n$, .

The main aim of this paper is to extend Theorem 1.1 to complex matrices and,
simultaneously, to get rid of the condition on “geometric multiplicity”. The
proof uses Gershgorin’s original theorem and is fairly simple. It also gives a
stronger result (Corollary 1.3 below) in the real case. Another target is the
extension of Theorem 1.1 in the real case by replacing the smaller Gershgorin
disks with slightly larger disks when the underlying matrix is normal, and
when it is almost symmetric. This is carried out in Sections 5 and 6.

Here comes the statement in the complex case.

######  Theorem 1.2.

Let $A$ be an $n\times n$ complex matrix and $\lambda$ be a complex number. If
there are $c_{i}\in\mathbb{C}$ satisfying the inequality

(1.3) $|a_{i,i}-c_{i}-\lambda|>\sum_{i\neq j}|a_{i,j}-c_{i}|\mbox{ for all
}i\in[n],$

then ${\rm rank}\,(A-\lambda I)\geqslant n-1.$

The relation to Gershgorin disks can be seen as follows. Fix the numbers
$c_{i}$ satisfying (1.3) (if they exist) and define $\rho_{i}=\sum_{i\neq
j}|a_{i,j}-c_{i}|$ for $i\in[n].$ Theorem 1.2 states then, in a form analogous
to (1.1), that if $\lambda$ is an eigenvalue of $A$ with multiplicity at least
two, then $\lambda\in\bigcup_{1}^{n}D(a_{i,i}-c_{i},\rho_{i})$. Note that in
this formulation there is no need for any condition on geometric multiplicity.

Checking whether condition (1.3) holds is fairly easy in the real case as we
shall see in Section 3. The complex case is more complex and we give some
comments on it at the end of Section 3.

Choosing the optimal $c_{i}$ often reduces the radius of the Gershgorin disk
for eigenvalues with a multiplicity of at least two. The $n\times n$ all one
matrix, $J_{n},$ shows that higher multiplicity might not guarantee a smaller
radius in Theorem 1.1 because the zero eigenvalue of $J_{n}$ has multiplicity
$n-1$ in $J_{n}$ and still, it lies on the boundary of the disk with radius
$r_{i}=1$ with center $a_{i,i}=1.$

Assume now that $A$ is a real $n\times n$ matrix. For all $i\in[n]$ let
$t_{i}^{*}$ denote the median of the numbers
$a_{i,1},\ldots,a_{i,i-1},a_{i,i+1},\ldots,a_{i,n}$ and set
$r_{i}^{*}=\sum_{j\neq i}|a_{i,j}-t_{i}^{*}|.$ Theorem 1.2 when applied to the
real matrix $A$ gives the following result.

######  Corollary 1.3.

Assume $A$ is a real $n\times n$ matrix. If
$\lambda\notin\bigcup_{1}^{n}D(a_{i,i},r_{i}^{*})$, then ${\rm
rank}\,(A-\lambda I)\geqslant n-1$. In other words, if $\lambda$ is an
eigenvalue of $A$ with multiplicity two or more, then
$\lambda\in\bigcup_{1}^{n}D(a_{i,i},r_{i}^{*})$.

This is a stronger version of Theorem 1.1 in the sense that $\lambda$ is a
usual (algebraic) eigenvalue of $A.$ At the same time the $t_{i}^{*}$ (and
then $r_{i}^{*}$) given here are slightly different from the $t_{i}$ in
Theorem 1.1 because $t_{i}$ is the median of $n$ numbers
$0,a_{i,1},\ldots,a_{i,n}$, where $a_{i,i}$ is missing while $t_{i}^{*}$ is
the median of $n-1$ numbers $a_{i,1},\ldots,a_{i,n}$ ($a_{i,i}$ is missing
again). However, Corollary 1.3 is stronger than Theorem 1.1 in this sense as
well because $r_{i}^{*}\leqslant r_{i}$.

In general, bounding the rank is important in linear algebra, such bounds have
various applications in different parts of mathematics. There are nice
examples of applications to combinatorics in Alon’s classical papers [1, 2]
that provide rank bounds for real matrices where the diagonal elements are
larger than other entries in their row, but not large enough for a direct
application of Gershgorin’s theorem.

##  2\. Proof of Theorem 1.2

We begin with a simple reduction. When $\lambda=0$ Theorem 1.2 takes the
following form.

######  Lemma 2.1.

Let $A$ be an $n\times n$ complex matrix. Assume there are numbers
$c_{i}\in\mathbb{C}$ satisfying the inequality

(2.1) $|a_{i,i}-c_{i}|>\sum_{i\neq j}|a_{i,j}-c_{i}|,$

for all $i\in[n]$. Then ${\rm rank}\,A\geqslant n-1.$ ∎

The lemma implies the general case by applying it to the matrix $A-\lambda I.$
Indeed, the diagonal entries of this matrix are $a_{i,i}-\lambda$ and the off-
diagonal ones are simply $a_{i,j}$ so condition (1.3) for $A$ is the same as
condition (2.1) for $A-\lambda I.$

The proof of the lemma is simple and uses diagonally dominant matrices. Let
$C$ be the matrix whose every entry in row $i$ is $c_{i}$ for $i\in[n]$ and
set $D=A-C.$ Condition (2.1) says exactly that $D$ is a diagonally dominant
matrix. The original Gershgorin theorem shows then that ${\rm rank}\,D=n.$ As
${\rm rank}\,A\geqslant{\rm rank}\,D-1=n-1,$ the result follows. ∎

We note that when condition (1.3) holds for $c_{i}=0$ we get back Gershgorin’s
circle theorem because then $C$ is the zero matrix that has rank zero.

Remark. One can go one step further. Define $C$ as above (with parameters
$c_{i}$) and let $E$ be the $n\times n$ complex matrix with every entry in its
$j$th column equal to $e_{j}$. We define $D=A-C-E$, so the entry $i,j$ of $D$
is $a_{i,j}-c_{i}-e_{j}$. Again, if the parameters $c_{i},e_{j}$ can be chosen
so that $D$ is diagonally dominated, then ${\rm rank}\,A\geqslant d-2.$

##  3\. The real case

For the application of Theorem 1.2 one has to decide if suitable $c_{i}$
values exist or not. This is fairly easy for real matrices as explained below.

Assume $A$ is a real $n\times n$ matrix and let
$b_{i,1}\leqslant\ldots\leqslant b_{i,n-1}$ be the increasing rearrangement of
the $n-1$ numbers $a_{i,1},\ldots,a_{i,n}$ where $a_{i,i}$ is missing. The
function $f(t)=\sum_{i\neq j}|a_{i,j}-t|$ is piecewise linear and convex. It
attains its minimum at the median of the numbers $b_{i,j}$. This median is the
single point $t_{i}^{*}:=b_{i,n/2}$ when $n$ is even and can be taken for any
point of the interval $J:=[b_{i,(n-1)/2},b_{i,(n+1)/2}]$ when $n$ is odd. We
remark that in this case, $r_{i}^{*}$ is the same no matter what $t\in J$ is
chosen for the median.

######  Claim 3.1.

In the real case condition (1.3) is satisfied by some $c_{i}$ if and only if
it is satisfied by $c_{i}=t_{i}^{*}$ when $n$ is even and by one of the
endpoints of $J$ when $n$ is odd.

Proof. One direction is easy: there is nothing to check when (1.3) is
satisfied at $c_{i}=t_{i}^{*}$ or when it is satisfied by one of the endpoints
of $J$.

Figure 1. The functions $f(t),g(t)$ and $|a_{i,i}-\lambda-t|$.

For the other direction assume first that $n$ is even and that condition (1.3)
is not satisfied at $t_{i}^{*}$, that is $|a_{i,i}-t_{i}^{*}-\lambda|\leqslant
f(t_{i}^{*})$. The function $g(t)=|t-t_{i}^{*}|+f(t_{i}^{*})$ is a translated
copy of the function $t\to|t|$ and $|a_{i,i}-t-\lambda|\leqslant g(t)$ for all
$t$ follows from $|a_{i,i}-t_{i}^{*}-\lambda|\leqslant f(t_{i}^{*})$. Moreover
$g(t)$ has slope $+1$ for $t>t_{i}^{*}$ and slope $-1$ for $t<t_{i}^{*}$,
while the slope of $f(t)$ is at least $1$ for $t>t_{i}^{*}$ and and at most
$-1$ for $t<t_{i}^{*}$; see Figure 1 left. Then $g(t)\leqslant f(t)$ for all
$t\in\mathbb{R}$ because $g(t_{i}^{*})=f(t_{i}^{*})$ and
$|a_{i,i}-\lambda-t|\leqslant f(t)$ for all $t$ follows.

The case of odd $n$ is similar. For simpler notation set $J=[t^{-},t^{+}]$ and
$t_{0}=\frac{1}{2}(t^{-}+t^{+})$. Suppose that (1.3) is not satisfied at
$t=t^{-}$ and at $t=t^{+}$. Observe that $f(t^{-})=f(t^{+}).$ Setting
$g(t)=|t-t_{0}|+f(t^{+})-\frac{1}{2}(t^{+}-t^{-})$ we see that
$g(t^{-})=f(t^{-})$ and $g(t^{+})=f(t^{+})$, see Figure 1 right. Then
$|a_{i,i}-\lambda-t|\leqslant g(t)$ for all $t$ because this inequality holds
for $t=t^{+}$ and $t=t^{-}$. Next one shows that $g(t)\leqslant f(t)$ for all
$t\in\mathbb{R}$. This holds because for $t>t^{+}$ the slope of $g(t)$ is $1$
and the slope of $f(t)$ is at least one and for $t<t^{-}$ the slope of $g(t)$
is $-1$ and that of $f(t)$ is at most $-1$. Moreover $f(t)$ is the constant
$f(t^{+})=f(t^{-})$ for $t\in J$, and there $g(t)$ is below this constant.∎

So in the real case in order to check whether condition (1.3) holds and for
finding the suitable $c_{i}$s one has to compare the minimum of $f(t)$ with
the value of $|a_{i,i}-\lambda-t|$ at one or two well-defined points.

Finding $c_{i}$ in the complex case is a different task. We have to decide if
the function $t\to|a_{i,i}-t|$ is below the function $t\to\sum_{i\neq
j}|a_{i,j}-t|$ for all complex numbers $t$ or not. One can check if this holds
when $t=a_{i,j}$ for all $j\in[n]$. At every other $t\in\mathbb{C}$ both
functions are differentiable so one could, in principle, decide if the maximum
of the function

$|a_{i,i}-t|-\sum_{i\neq j}|a_{i,j}-t|$

is positive for any fixed $i\in[n]$ or not. As the real case indicates, a good
candidate for $c_{i}$ is where the function $f(t)=\sum_{j\neq i}|a_{i,j}-t|$
attains its minimum on $t\in\mathbb{C}$. This point can be determined by
convex programming. We remark without proof that $\arg\min f(t)$ is a single
point unless all the points $a_{i,j}$ ($j\neq i$) are collinear. The latter
case is covered by Claim 3.1.

##  4\. An example

We show a geometric application of Lemma 2.1 which is similar to an example of
Alon [2] and of Bukh and Cox [4]. The unit $\ell_{1}$-ball in $\mathbb{R}^{d}$
is the convex hull of the $2d$ points $\pm e_{i},$ i.e., the collection of
$x\in\mathbb{R}^{d}$ such that $\|x\|_{1}\leq 1.$ Here $e_{i}$ denotes the
vector with a 1 in the $i$th coordinate and 0’s elsewhere. The Euclidean
distance between $e_{i}$ and $-e_{i}$ is $2$ (for all $i$), and the distance
between two other vertices is exactly$\sqrt{2}.$ What happens if we relax the
distance constraints a bit? What is the maximum number of point pairs,
$(p_{i},q_{i})$ in $\mathbb{R}^{d},$ to be denoted by $k,$ such that
$(p_{i}-q_{i})^{2}=4$ for every $i\in[k]$ and for every pair
$i,j\in[k],\;i\neq j$ we have

$|(p_{i}-q_{j})^{2}-{2}|\leq\varepsilon,\;|(p_{i}-p_{j})^{2}-{2}|\leq\varepsilon,\;|(q_{i}-q_{j})^{2}-{2}|\leq\varepsilon.$

The answer is that there are at most two extra point pairs if $\varepsilon$ is
small enough. More precisely

######  Claim 4.1.

If $\varepsilon<2/(3d+5)$, then $k\leq d+2.$

Proof. Assume that $k>d+2$ and consider the first $d+3$ pairs $(p_{i},q_{i}).$
The $(d+2)\times(d+2)$ matrix $M$ is defined by the dot products
$m_{i,j}=(p_{i}-p_{1})\cdot(q_{j}-p_{1}),$ for all $2\leq i,j\leq d+3.$ The
rank of $M$ is at most $d.$ The identity
$(p_{i}-p_{1})^{2}+(q_{j}-p_{1})^{2}-(p_{i}-q_{j})^{2}=2(p_{i}-p_{1})\cdot(q_{j}-p_{1})$
(the cosine theorem in trigonometry) and the conditions imply that

$(2-\varepsilon)+(2-\varepsilon)-(2+\varepsilon)\leqslant
2(p_{i}-p_{1})\cdot(q_{j}-p_{1})\leqslant(2+\varepsilon)+(2+\varepsilon)-(2-\varepsilon).$

Consequently

$|m_{i,j}-1|\leqslant\frac{3}{2}\varepsilon\mbox{ for }i\neq j\mbox{ and
}|m_{i,i}-1|\geqslant 1-\varepsilon\mbox{ for }2\leqslant i\leqslant d+3.$

We check that Lemma 2.1 applies now with $c_{i}=1$ for all $i=2,3,\ldots,d+3$.
Indeed $|m_{i,i}-c_{i}|\geqslant 1-\varepsilon$ and $\sum_{j\neq
i}|m_{i,j}-c_{i}|\leqslant(d+1)\frac{3}{2}\varepsilon$ when $i\neq j.$ Thus
the inequality $|m_{i,i}-c_{i}|>\sum_{j\neq i}|m_{i,j}-c_{i}|$ follows from
the condition $\varepsilon<2/(3d+5)$ via a simple computation. By Lemma 2.1,
${\rm rank}\,M\geqslant d+2-1=d+1,$ contradicting the fact that ${\rm
rank}\,M\leqslant d.$∎

The following construction shows that the result in Claim 4.1 is close to
being sharp. Let us choose a $d$ such that there is a Hadamard matrix, $H_{n}$
of order $n=d+2.$ The row vectors of $H_{n}$ and $-H_{n}$ form a scaled and
rotated $\ell_{1}$ ball in $\mathbb{R}^{n}.$ The pointset we are going to
consider in $\mathbb{R}^{d}$ consists of the projection of the $2n$ row
vectors $\pm\frac{1}{\sqrt{d}}H_{n}$ by deleting the last two coordinates of
every row. The squared distance between non-antipodal points is between
$2-4/d$ and $2+4/d$ while the distance between the $d+2$ antipodal points is
exactly 2.

One can relax the condition $(p_{i}-q_{i})^{2}=4$ to
$|(p_{i}-q_{i})^{2}-4|\leq\varepsilon$. In this case, the proof goes along the
same steps as above and gives that for $\varepsilon<2/(3d+6)$ the maximal
number of such $p_{i},q_{i}$ pairs is at most $d+2$. We omit the details.

##  5\. Normal Matrices

Here we show that if two eigenvalues of a real and normal matrix are close,
then both of them lie in a smaller Gershgorin disk. A matrix is normal if its
eigenvectors belonging to distinct eigenvalues are orthogonal. For instance, a
symmetric and real matrix is always normal.

######  Theorem 5.1.

Assume $\lambda$ and $\mu$ are distinct eigenvalues of a real and normal
$n\times n$ matrix $A$, $n\geqslant 3$. Then both $\lambda$ and $\mu$ lie in
the disk $D(a_{i,i},\rho_{i})$ for some $i\in[n]$ where
$\rho_{i}=r_{i}+\sqrt{n}|\lambda-\mu|$.

Proof. Let $A$ be a normal, real, $n\times n,$ matrix. Let
$v=(v_{1},\ldots,v_{n})$ resp. $w=(w_{1},\ldots,w_{n})$ be the eigenvectors
corresponding to $\lambda$ and $\mu$, the coordinates
$v_{i},w_{j}\in\mathbb{C}$. As $n\geqslant 3$ there are
$\alpha,\beta\in\mathbb{C},$ such that

$\sum_{i=1}^{n}\alpha v_{i}+\beta w_{i}=0,$

and the largest coordinate is one, i.e. $\alpha v_{i}+\beta w_{i}=1$, and
$|\alpha v_{j}+\beta w_{j}|\leq 1$ for any $j\in[n].$

Let $t=\alpha v+\beta w$. Then $At=\mu\alpha v+\lambda\beta w$ and

$a_{i,1}t_{1}+a_{i,2}t_{2}\ldots+a_{i,i}+\ldots+a_{i,n}t_{n}=\mu\alpha{v}_{i}+\lambda\beta{w}_{i}=\mu+(\lambda-\mu)\beta{w}_{i}$

because $t_{i}=1$. Set
$S=a_{i,1}t_{1}+a_{i,2}t_{2}\ldots+a_{i,i}+\ldots+a_{i,n}t_{n}-a_{i,i}$. Then

$|\mu-a_{i,i}|\leqslant|S|+|\lambda-\mu||\beta w_{i}|.$

Bounding $S$ comes from Theorem 2 in [5] and, in a slightly more general form,
from Lemma 2.4 of [11] in the form of the following fact.

######  Lemma 5.2.

$|S|\leqslant r_{i}$.

The proof is the same as in [5] and we present it at the end of this section.

We bound the error term $|\beta w_{i}|$ using that $A$ is normal. The two
eigenvectors are orthogonal, so we have

$n\geq|t|^{2}=|\alpha v|^{2}+|\beta w|^{2},$

which implies that $|\beta w_{i}|\leq\sqrt{n}.$∎

The proof of Lemma 5.2 is simple.

$\displaystyle S$ $\displaystyle=$ $\displaystyle
a_{i,1}t_{1}+\ldots+a_{i,i-1}t_{i-1}+0t_{i}+a_{i,i+1}t_{i+1}+\ldots+a_{i,n}t_{n}$
$\displaystyle=$ $\displaystyle(a_{i,1}-x)t_{1}+\ldots+(a_{i,i-1}-x)t_{i-1}+$
$\displaystyle+(0-x)t_{i}+(a_{i,i+1}-x)t_{i+1}+\ldots+(a_{i,n}-x)t_{n}$

for every $x\in\mathbb{R}$ because $\sum t_{i}=0$. As $|t_{i}|\leqslant 1$ for
all $i\in[n]$ this implies that

$|S|\leqslant|a_{i,1}-x|+\ldots+|a_{i,i-1}-x|+|0-x|+|a_{i,i+1}-x|+\ldots+|a_{i,n}-x|.$

The function $x\to|a_{i,1}-x|+\ldots+|a_{i,n}-x|$ is the sum of convex
functions and, as we have seen, its minimum is reached on the median, $t_{i}$,
of the numbers $a_{i,1},\ldots,a_{i,i-1},0,a_{i,i+1},\ldots,a_{i,n}$ and
equals $r_{i}.$∎

##  6\. Almost Symmetric Matrices

This section extends the previous results to almost symmetric real matrices.

There are different ways to define almost symmetric matrices. They appear in
various contexts in applied linear algebra. For example in [6] and [8] a
nearly symmetric matrix is defined as a matrix in which the overwhelming
majority of entries are symmetric about its diagonal. In other examples, an
almost symmetric matrix $M$ is given as $M=S+E$ where $S$ is a symmetric
matrix and $E$ is a small error or “noise”. We can’t repeat the arguments on
Theorem 5.1 because even small changes can make the eigenvectors far from
being orthogonal, like in the example below.

$M=\left[\begin{array}[]{cc}1&\varepsilon\\\ 0&1+\varepsilon\\\
\end{array}\right]$

We will not give a formal definition of what an almost symmetric matrix is.
Instead we introduce a parameter, $\Delta(A),$ measuring the symmetry of a
matrix $A$:

$\Delta(A)=\max_{i\in[n]}\left|\sum_{j=1}^{n}(a_{i,j}-a_{j,i})\right|.$

In this definition the pairs $a_{i,j}$ and $a_{j,i}$ can be far from each
other, the parameter $\Delta(A)$ is the maximum difference between the sum of
the entries in row $i$ and that of the entries in column $i$. For instance
$\Delta(A)=0$ for a doubly stochastic matrix $A$.

With this new matrix parameter, we generalize Theorem 5.1 to arbitrary real
matrices. We are going to use the well-known fact that an eigenvector of a
real matrix $A$ which belongs to the eigenvalue $\lambda$ is orthogonal to any
eigenvector of $A^{T}$ which belongs to a different eigenvalue $\mu.$

######  Theorem 6.1.

Assume that $A=\\{a_{i,j}\\}_{i,j=1}^{n}$ is a real matrix and $n\geqslant 3$.
If $\lambda$ and $\mu$ are two distinct eigenvalues of $A,$ then there is
$i\in[n]$ such that both $\lambda$ and $\mu$ lie in the disk
$D(a_{i,i},\rho_{i})$ where $\rho_{i}=r_{i}+\sqrt{n}(\Delta+|\lambda-\mu|)$
where $r_{i}$ is the same as before.

Proof. Let $v$ be the eigenvector of $\lambda$ in $A$ and $w$ be the
eigenvector of $\mu$ in $A^{T}.$ The two vectors are orthogonal, so they are
linearly independent. Then there are $\alpha,\beta\in\mathbb{C}$ such that the
coordinates of $\alpha v+\beta w$ add up to zero:

$\sum_{i=1}^{n}\alpha u_{i}+\beta w_{i}=0,$

and the largest norm coordinate (indexed by $i\in[n]$) is one. We assume again
that $\alpha v_{i}+\beta w_{i}=1$ and so $|\alpha v_{j}+\beta w_{j}|\leqslant
1$ for all $j\in[n].$ With these notations we have the system of equations

$A\alpha u+A^{T}\beta w=\lambda\alpha v+\mu\beta w=\lambda(\alpha v+\beta
w)+(\mu-\lambda)\beta w,$

Let us consider the $i$th row

$\alpha v_{1}a_{1,i}+\beta w_{1}a_{i,1}+\ldots+a_{i,i}+\ldots+\alpha
v_{j}a_{j,i}+\beta w_{j}a_{i,j}+\ldots=\lambda+(\mu-\lambda)\beta w_{i}.$

From this we have

$|\lambda-a_{i,i}|\ \leq\left|\sum_{j\neq i}^{n}(\alpha v_{j}+\beta
w_{j})a_{j,i}-\beta\sum_{j=1}^{n}w_{j}(a_{j,i}-a_{i,j})-(\mu-\lambda)\beta
w_{i}\right|$

Using the bound $|\beta w_{i}|\leq\sqrt{n}$ from the previous proof we have

$\displaystyle\begin{split}|\lambda-a_{i,i}|\ &\leq\left|\sum_{j\neq i}(\alpha
u_{j}+\beta
w_{j})a_{j,i}-\beta\sum_{j=1}^{n}w_{j}(a_{j,i}-a_{i,j})-(\mu-\lambda)\beta
w_{i}\right|\leq\\\ &\leq\left|\sum_{j\neq i}(\alpha u_{j}+\beta
w_{j})a_{j,i}\right|+\sqrt{n}\left|\sum_{j=1}^{n}(a_{j,i}-a_{i,j})\right|+\sqrt{n}|(\mu-\lambda)|\leq\\\
&\leq
r_{i}+\sqrt{n}\left(\Delta(A)+\left|\mu-\lambda\right|\right).\end{split}$

Here the estimate $\left|\sum_{j\neq i}(\alpha u_{j}+\beta
w_{j})a_{j,i}\right|\leqslant r_{i}$ is the same as in the proof of Theorem
5.1.∎

##  7\. Acknowledgements

Research of both authors was supported by a Hungarian National Research Grant
KKP grant no. 133819. Research of IB was supported in part by Hungarian
National Research grants no. 131529, 131696. Research of JS was supported in
part by an NSERC Discovery grant and OTKA K grant no.119528.

## References

  * [1] N. Alon, Problems and results in extremal combinatorics I, Discrete Mathematics, 273 (2003), 31–53.
  * [2] N. Alon, Perturbed identity matrices have high rank: Proof and applications, Combinatorics, Probability and Computing,18 (2009), 3–15.
  * [3] N. Alon, and J. Solymosi, Rank of matrices with entries from a multiplicative group, International Mathematics Research Notices, (2022) (to appear).
  * [4] B. Bukh, and C. Cox, Nearly orthogonal vectors and small antipodal spherical codes. Israel J. Math., 238 (2020), 359–-388.
  * [5] I. Bárány and J. Solymosi, Gershgorin Disks for Multiple Eigenvalues of Non-negative Matrices. In: Loebl M., Nešetřil J., Thomas R. (eds) A Journey Through Discrete Mathematics. Springer, Cham, (2017).
  * [6] A.H. Berliner and R. A. Brualdi, Nearly symmetric-indecomposable matrices, Linear and Multilinear Algebra, 63 (2015), 1468–1484.
  * [7] Ky Fan, and A. J. Hoffman, Lower bounds for the rank and location of the eigenvalues of a matrix. Contributions to the solution of systems of linear equations and the determination of eigenvalues, National Bureau of Standards Applied Mathematics Series, No. 39 (1954), 117–130.
  * [8] Hong Zheng, Sheng Guo Cheng, Quan Sheng Liu, A decomposition procedure for nearly symmetric matrices with applications to some nonlinear problems, Mechanics Research Communication, 37 (2010), 78–84.
  * [9] Lee DeVille, Optimizing Gershgorin for symmetric matrices, Linear Algebra and its Applications, 577 (2019), 360–383,
  * [10] S. Gershgorin, Über die Abgrenzung der Eigenwerte einer Matrix. Izv. Akad. Nauk. USSR Otd. Fiz.-Mat. Nauk, 6 (1931), 749–754.
  * [11] F. J. Hall and R. Marsli, On the location of eigenvalues of real matrices, Electron. J. Linear Algebra, 32 (2017), 357–364.