# The Anomalous Resonant Frequency Variation of Microwave
Superconducting Niobium Cavities Near $T_{c}$

D. Bafia<EMAIL_ADDRESS>Fermi National Accelerator Laboratory, Batavia,
Illinois 60510, USA  A. Grassellino  Fermi National Accelerator Laboratory,
Batavia, Illinois 60510, USA  M. Checchin  Fermi National Accelerator
Laboratory, Batavia, Illinois 60510, USA  J. F. Zasadzinski  Department of
Physics, Illinois Institute of Technology, Chicago, Illinois 60616, USA  A.
Romanenko  Fermi National Accelerator Laboratory, Batavia, Illinois 60510, USA

###### Abstract

Superconducting radio-frequency (SRF) niobium cavities are the modern means of
particle acceleration and an enabling technology for record coherence
superconducting quantum systems and ultra-sensitive searches for new physics.
Here, we report a systematic effect in Nb cavities indicative of improved
superconducting properties - an anomalous decrease (dip) in the resonant
frequency at temperatures just below the critical temperature
$T_{\mathrm{c}}$. The frequency dip magnitude correlates with cavity quality
factor, near-surface impurity distribution, and $T_{\mathrm{c}}$. It is also a
precursor of the peculiar decrease in the BCS surface impedance with
increasing RF current. A first demonstration of the coherence peak in the AC
conductivity in Nb SRF cavities is also presented and found to correlate with
a large frequency dip.

††preprint: APS/123-QED

Superconducting radio-frequency (SRF) niobium cavities are record-high quality
factor $Q_{0}>10^{10}-10^{11}$ man-made resonators that serve as the primary
continuous wave accelerating structures in modern particle accelerators [1],
longest coherence microwave quantum superconducting systems [2], and an ultra-
sensitive platform for dark sector and dark matter candidate searches [3, 4,
5, 6].

An important feature of SRF cavities is the commonly observed reduction of the
$Q_{0}$ (Q-slope) with the magnitude of the stored microwave field. Extensive
research over the past decades allowed uncovering and mitigating several such
field-dependent physical mechanisms in various regimes [1]. This most recently
includes proximity-coupled niobium nanohydrides [7] and their mitigation by
oxygen inward diffusion [8] and the reduction of two-level system driven
dissipation by oxide removal [9, 2].

This steady improvement has unveiled new SRF phenomena that remain poorly
understood, most notably the factor of four increase in $Q_{0}$ and the field-
dependent _increase_ in the quality factor of nitrogen doped [10] cavities. A
comparison to more standard surface treatments such as electropolishing (EP)
is shown in Fig. 1. The unusual effect, often called the anti-Q slope (top
curve of Fig. 1), stems from an anomalous decrease of the “BCS” component [11]
of the surface resistance with increasing field [10]. This effect challenges
our understanding; in essence, it is as if superconducting pairing strengthens
with increased RF field and current, an effect that is counterintuitive.
Material studies have highlighted its dependence on the near-surface
interstitial nitrogen concentration and distribution. For the microscopic
mechanism, one suggested possibility is the field-driven non-equilibrium
redistribution of thermally excited quasiparticles to higher energy levels.
Studies on cavities of different frequencies [12] provide support for this
possibility. Still, a systematic study of the effect of doping on
quasiparticle lifetimes and density of states as well as strong coupling
pairing effects in SRF cavities has not been reported and is critical for the
understanding of the effect.

While many studies have focused on the quality factor, here we report that the
cavity resonant frequency provides another valuable avenue for gaining insight
into the underlying physical phenomena, as its changes are directly connected
to the properties of the superconducting condensate. The inset of Fig. 1 shows
a correlation of cavity $Q_{0}$ at a field strength of 16 MV/m with the
magnitude of an anomalous frequency drop observed just below the critical
transition temperature $T_{c}$. Detailed examination of this unusual frequency
drop is presented here.

The AC complex conductivity $\sigma=\sigma_{1}+i\sigma_{2}$ enables further
insight on quasiparticles and superconducting carriers. For frequencies far
below the superconducting gap ($\hbar\omega\ll\Delta$), $\sigma_{1}$ exhibits
the coherence peak, a non-monotonic dependence of the quasiparticle
conductivity with temperature that arises due to coherence factors in BCS
theory [13] and is analogous to the Hebel-Slichter peak in nuclear spin
relaxation [14]. However, until now, this coherence peak has not been reported
in Nb SRF cavities. It will be shown that the height of the coherence peak
also correlates with the frequency drop. Taken together, these correlated
phenomena suggest that extrinsic factors have prevented the observation of
novel intrinsic RF properties of strong-coupled Nb. We comment later on
possible origins for the correlations among these unusual observations.

In this article, a systematic study is presented on a large number ($>$40) of
state-of-the-art bulk niobium SRF cavities revealing the anomalous decrease
(dip) in the cavity resonant frequency at temperatures just below
$T_{\mathrm{c}}$ in nitrogen doped cavities. In addition, we report other
(non-dip) characteristic temperature dependencies uniquely corresponding to
each of the other explored surface treatments that show strong correlation
with cavity performance and the anti-Q slope. The measured coherence peak in
the complex conductivity of bulk niobium SRF cavities is fit with a
phenomenological model incorporating a pair-breaking term in the BCS density
of states. The fits suggest that the coherence peak, along with the dip
phenomenon, high $Q_{0}$, and anti-Q slope, are signatures of improved
superconducting properties and occur when extrinsic pair-breaking effects are
minimized. Furthermore, an understanding of the frequency dip may be a key to
the microscopic origin of the anti-Q slope.

Figure 1: CW RF test results of Nb SRF cavities subjected to surface
treatments used in this study. Inset plots $Q_{0}$ at 16 MV/m at 2 K against
the measured dip magnitude of cavities subjected to either EP or various
N-doping surface treatments.

A large set of bulk niobium SRF cavities of TESLA [15] elliptical shape were
employed for our studies. The resonant frequencies of these cavities varied
from 650 MHz to 3.9 GHz, which allowed probing the low frequency limit of Nb.
All cavities went through a bulk electropolishing of 120 $\mu$m material
removal followed by different modern surface treatments on subsets of multiple
cavities in each. The treatments investigated included hydrogen degassing at
800∘C followed by additional 40 $\mu$m electropolishing, nitrogen doping [10]
with varying dopant concentrations, nitrogen infusion [16], 120∘C baking for
48 hours [17], and “modified” 75/120∘C baking [18, 19]. One of the nitrogen
doped cavities has been studied with a step-by-step material removal after
initial doping to directly probe the effect of gradual changes in interstitial
nitrogen concentration on cavity performance.

All cavities were first cooled down to 2 K where standard measurements [20] of
$Q_{0}$ as a function of the accelerating gradient $E_{\mathrm{acc}}$ have
been performed. Characteristic $Q_{0}(E_{\mathrm{acc}})$ curves are shown in
Fig. 1.

Measurements of the resonant frequency $f_{0}$ with temperature were performed
as follows. All cavities were equipped with resistance temperature detectors
(RTDs), placed in a helium dewar, and pre-cooled to 4.2 K. Heaters located at
the bottom were used to boil off the liquid helium and warm the dewar. This
procedure allowed for a warming rate of $<0.1$ K/min, ensuring thermalization
of the cavity, as confirmed by the RTD readings. Resonant frequency was
recorded with a vector network analyzer. Measurements persisted through the
niobium superconducting transition temperature at $\sim$9.2 K. After
measurements, the data was corrected to account for variations in dewar gas
pressure.

For each $f_{0}(T)$ dataset, an effective mean free path $\ell$ within the
cavity surface layer has been obtained by converting the measured frequency
shift with temperature near $T_{\mathrm{c}}$ into a shift in the magnetic
field penetration depth $\lambda(T)$ using Slater’s theorem [21] and fitting
based on the modified Halbritter routine [22], following the same technique
outlined in [23].

Overall, we have studied the frequency response of 41 cavities with various
impurity structures in the RF layer. Of these 41, we found a clear dip in the
resonant frequency just below the $T_{\mathrm{c}}$ in 22 N-doped cavities,
similar to the one shown in Fig. 2(b). For other treatments, we observed four
other characteristic behaviors, which we labeled “foot”, “bump”, “dip+bump”,
and “standard.” More details are provided in the Supplemental Material.

Figure 2: (a) CW RF measurements and (b) resonant frequency response with
temperature of a single 1.3 GHz Nb cavity after sequential removal of the
surface post nitrogen doping. The legend in (b) presents the fitted $\ell$ in
the RF layer after each step. Resonant frequency shift is reported relative to
the normal conducting value near 10 K. The parameter $\Delta f_{dip}$ is
called the dip magnitude and $T_{c}$ is the critical transition temperature.
(c) The dip magnitude and $T_{c}$ are plotted against the fitted $\ell$.
Horizontal error bars come from fitting while vertical error bars are smaller
than the data points. Solid and dashed lines show $e^{-\ell}$ and $-e^{-\ell}$
relationships, respectively.

To investigate the dependence of the dip on the nitrogen concentration, one
cavity subjected to 3/60 nitrogen doping underwent several sequential material
removal steps of the RF surface via EP, with RF measurements performed after
each step. The material removal allowed to gradually decrease the
concentration of N present in the RF layer, resulting in an increase in
$\ell$. After the combined 30 $\mu$m material removal, the cavity was bulk
electropolished and re-processed with the 2/6 N-doping surface treatment. The
$Q_{0}(E_{\mathrm{acc}})$ and $f_{0}(T)$ results along with the corresponding
material removal amounts and extracted $\ell$ values are presented in Fig. 2.

We observe that dilute and uniform concentrations of nitrogen (short $\ell$)
produce a characteristic increase in $Q_{0}$ at higher $E_{\mathrm{acc}}$, a
weak suppression in $T_{c}$, and an anomalous frequency dip just before
$T_{c}$. As nitrogen concentration gradually decreases with more material
removal, these behaviors are gradually diminished. The $Q_{0}$ behavior with
field approaches that of the typical EP cavity presented in Fig. 1. Meanwhile,
the dip magnitude diminishes as the transition temperature assumes the clean
niobium value. Subsequent bulk electropolishing and 2/6 doping, which is known
to produce a larger nitrogen concentration than 3/60 doping, shows a return of
the dip feature with a larger magnitude and lower $T_{\mathrm{c}}$.

Fig. 2(c) plots the dip magnitude and transition temperature against $\ell$.
The dip magnitude decreases strongly (close to exponentially) while the
transition temperature increases with increasing $\ell$ values. The $T_{c}$
varies by $\sim$120 mK throughout the course of the study, which is in good
agreement with previous work on the effects of nitrogen and oxygen on niobium
$T_{\mathrm{c}}$ [24]. Our findings clearly show that a frequency dip and
corresponding $T_{c}$ suppression occur in the presence of uniform and dilute
concentrations of N impurities and that the concentration of N serves as a
major parameter in determining the extent of the phenomena.

Figure 3: (a) Frequency response with temperature of four cavities, each with
different resonant frequency, processed to yield an identical nitrogen
concentration in the RF layer. Inset shows the response over a larger range of
temperatures. (b) Left-hand axis shows the dip magnitude plotted against the
fundamental resonant frequency for each cavity. The right-hand axis plots the
degree of anti-Q slope of each cavity, as defined in the text. Dashed and
solid lines show linear fits.

To study the effect of resonant frequency on the dip, four niobium cavities
with $f_{0}$=650 MHz, 1.3 GHz, 2.6 GHz, and 3.9 GHz were subjected to the same
N-doping surface treatment, producing an identical impurity structure in each
cavity. The results are shown in Fig. 3(a). We observe that resonant frequency
is linearly related with the dip magnitude, as shown in Fig. 3(b).
Furthermore, the degree of anti-Q slope, defined here as the slope from 2 MV/m
to 15 MV/m of the $Q_{0}(E_{\text{acc}})$ curve normalized to the value at 2
MV/m, also exhibits a linear trend with the resonant frequency. A similar
dependence of the anti-Q slope is shown in [12] where it is hypothesized that
such behavior may be driven by non-equilibrium superconductivity. This
correlation suggests that the frequency dip is a fundamental property that is
directly related to the anti-Q slope phenomenon of N-doped cavities.

To gain insight on the conditions under which different frequency features
near $T_{c}$ occur, we measured the AC complex conductivity of two niobium
cavities: i) the cavity presented in Fig. 2(a) with $\ell=550\pm 120$ nm which
showed the standard feature near $T_{c}$ and ii) a nitrogen doped cavity that
exhibited the prominent dip. The transition temperature of the latter cavity
was 9.04 K; using Fig. 2(c), the extrapolated $\ell$ was about 70 nm.
Normalized values of $\sigma_{1}$ and $\sigma_{2}$ have been obtained from
$Q_{0}(T)$ and $f_{0}(T)$ data using the method discussed by Trunin [25]. We
accounted for anomalous skin effects by using theory from Reuter and
Sondheimer [26]. This method required the measurement of the surface impedance
for $2<T<10$ K using the methods laid out in [27]. The calculated
conductivities are presented in Fig. 4. As the technique used to measure the
surface impedance sums over the inner surface, these curves represent the
average cavity response. Details on the technique are given in the
Supplemental Material.

Figure 4: Real and imaginary parts of the AC conductivity normalized to the
normal conducting value $\sigma_{n}$ of two 1.3 GHz cavities treated with EP
or N-doping. Error bars for the test post N-doping are dominated by
measurement uncertainty while those shown post EP are dominated by error in
the fitted $\ell$ value. Dashed and solid lines show fits.

From Fig. 4, we observe that both the EP and N-doped cavities exhibit the so-
called coherence peak, with the maxima at $\sim$0.9 $T/T_{c}$ differing in
amplitude. This suggests a variation in the quasiparticle behavior within the
RF layer due to distinct impurity distributions.

The dashed and solid curves in Fig. 4 are calculated using a modified version
of the Mattis-Bardeen (MB) conductivity with the Dynes inelastic scattering,
or depairing rate parameter $\Gamma$ [28] built in. This phenomenological
model, which is further discussed in the Supplemental Materials, gives a
measure of pair-breaking in the RF surface by introducing subgap quasiparticle
states and reproduces some of the salient features discussed in more rigorous
theories at low $\Gamma/\Delta_{0}$ values [29, 30, 31].

We find that both $\sigma_{1}$ and $\sigma_{2}$ of the EP cavity are best
modelled with an average superconducting gap $\Delta_{0}=1.5$ meV and an
inelastic scattering parameter $\Gamma/\Delta_{0}$ = 0.025. The N-doped cavity
is instead better fitted with a larger average superconducting gap
$\Delta_{0}=1.6$ meV and a lower level of pair-breaking ($\Gamma/\Delta_{0}$ =
0.0058). Recent work by Herman [32] has fitted this conductivity data with an
alternative theory that also considers the Dynes parameter. The fits produced
in that work are in qualitative agreement with the observations made using the
present phenomenological model. Notice that the stronger coherence peak occurs
for the cavity with the shorter $\ell$. This follows Anderson’s theorem in
that elastic scattering has no effect on superconductivity. But higher elastic
scattering is indicative of N interstitials that are mitigating depairing
processes.

These values are consistent with point contact tunneling spectroscopy (PCTS)
studies by Groll et al. on similarly treated cavity cutouts [33]. The N-doped
samples in those studies show more homogeneous $\Delta_{0}$ values and lower
levels of $\Gamma/\Delta_{0}$ than those that come from EP cavities [34]. This
gives one possible cause for the difference in gap values obtained from the
fits shown in Fig. 4; electropolished cavities contain localized defective
regions that bring down the average superconducting gap. The lower level of
pair-breaking observed in Fig. 4 for the N-doped cavity is likely due to the
absence (or lower volume fraction) of proximity coupled nanohydrides and
magnetic moments within the interface. This is consistent with the fact that
N-doped cavities do not exhibit the high field $Q$ drop caused by the
proximity breakdown of hydrides at high fields [10, 7].

These observations imply that superconducting niobium which contains a minimal
level of depairing processes in the RF layer exhibits both the anti-Q slope
and the frequency dip.

While a full microscopic model for the frequency dip has not yet been
realized, there remain several candidates. One possibility is current
redistribution which may cause an increase in the surface impedance [35].
Another alternative is that the phenomenon stems directly from MB theory [36].
Additionally, the AC susceptibility has been shown to exhibit similar
phenomena near $T_{c}$ that lead to the paramagnetic Meissner effect [37] or
when considering anisotropic effects in the AC response of the Meissner state
[38].

Although we focus primarily on the “dip” and “standard” features, it is likely
that the three other frequency features near $T_{c}$ follow some relationship
with $\ell$, $\Gamma/\Delta_{0}$, and $\Delta_{0}$ as well. This will be a
topic of future study.

In summary, we have presented systematic studies of an anomalous resonant
frequency behavior near $T_{c}$ of bulk niobium SRF cavities that correlates
directly with $Q_{0}(E_{\mathrm{acc}})$ and the novel anti-Q-slope state.
Thus, an understanding of the frequency dip may shed new light on details of
the surface superconductivity. Furthermore, the first observation of the
coherence peak in these structures was presented and it was shown that the
strength of this peak correlates with reduced pairbreaking in the surface
layer. This latter effect implies that a dilute concentration of N
interstitials prevents the formation of surface irregularities (e.g. hydrides,
magnetic oxides) that cause depairing, allowing intrinsic properties to be
revealed. These findings open a new avenue for understanding the underlying
fundamental physics behind the increase of the SRF cavity $Q_{0}$ with field
in nitrogen doped cavities. In particular, the proposed non-equilibrium
redistribution of quasiparticle states may rely on the low inelastic
scattering (or recombination) rates measured here. Thus, while the high
$Q_{0}$ values of these N-doped cavities are of technological interest for a
host of accelerator applications, it may also be pointing to novel
superconductivity in Nb under these intense fields of microwave photons.

The authors would like to acknowledge O. Melnychuk and D. A. Sergatskov for
technical support during measurements. Work supported by the Fermi National
Accelerator Laboratory, managed and operated by Fermi Research Alliance, LLC
under Contract No. DE-AC02-07CH11359 with the U.S. Department of Energy.

## References

  * Padamsee [2014] H. S. Padamsee, Annu. Rev. Nucl. Part. Sci. 64, 175 (2014).
  * Romanenko  _et al._ [2020] A. Romanenko, R. Pilipenko, S. Zorzetti, D. Frolov, M. Awida, S. Belomestnykh, S. Posen, and A. Grassellino, Phys. Rev. Appl. 13, 034032 (2020).
  * Janish  _et al._ [2019] R. Janish, V. Narayan, S. Rajendran, and P. Riggins, Phys. Rev. D 100, 015036 (2019).
  * Bogorad  _et al._ [2019] Z. Bogorad, A. Hook, Y. Kahn, and Y. Soreq, Phys. Rev. Lett. 123, 021801 (2019).
  * Berlin  _et al._ [2020] A. Berlin, R. T. D’Agnolo, S. A. R. Ellis, C. Nantista, J. Neilson, P. Schuster, S. Tantawi, N. Toro, and K. Zhou, J. High Energy Phys. 2020, 88 (2020).
  * [6] C. Gao and R. Harnik, ArXiv:2011.01350.
  * Romanenko  _et al._ [2013] A. Romanenko, F. Barkov, L. D. Cooley, and A. Grassellino, Supercond. Sci. and Technol. 26, 035003 (2013).
  * Romanenko  _et al._ [2019] A. Romanenko, Y. Trenikhina, M. Martinello, D. Bafia, and A. Grassellino, in  _Proceedings of the 19th International Conference on RF Superconductivity_ (HZDR, Dresden, Germany, 2019) p. 866.
  * Romanenko and Schuster [2017] A. Romanenko and D. I. Schuster, Phys. Rev. Lett. 119, 264801 (2017).
  * Grassellino  _et al._ [2013] A. Grassellino, A. Romanenko, D. Sergatskov, O. Melnychuk, Y. Trenikhina, A. Crawford, A. Rowe, M. Wong, T. Khabiboulline, and F. Barkov, Supercond. Sci. and Technol. 26, 102001 (2013).
  * Mattis and Bardeen [1958] D. C. Mattis and J. Bardeen, Phys. Rev. 111, 412 (1958).
  * Martinello  _et al._ [2018] M. Martinello, M. Checchin, A. Romanenko, A. Grassellino, S. Aderhold, S. K. Chandrasekeran, O. Melnychuk, S. Posen, and D. A. Sergatskov, Phys. Rev. Lett. 121, 224801 (2018).
  * Bardeen  _et al._ [1957] J. Bardeen, L. N. Cooper, and J. R. Schrieffer, Phys. Rev. 108, 1175 (1957).
  * Hebel and Slichter [1959] L. C. Hebel and C. P. Slichter, Phys. Rev. 113, 1504 (1959).
  * Aune et al. [2000] B. Aune et al., Phys. Rev. ST Accel. Beams 3, 092001 (2000).
  * Grassellino  _et al._ [2017] A. Grassellino, A. Romanenko, Y. Trenikhina, M. Checchin, M. Martinello, O. S. Melnychuk, S. Chandrasekaran, D. A. Sergatskov, S. Posen, A. C. Crawford, S. Aderhold, and D. Bice, Supercond. Sci. Technol. 30, 094004 (2017).
  * Padamsee [2009] H. Padamsee,  _RF Superconductivity: Volume II: Science, Technology and Applications_ (Wiley-VCH Verlag GmbH and Co., KGaA, Weinheim, 2009).
  * [18] A. Grassellino, A. Romanenko, D. Bice, O. Melnychuk, A. C. Crawford, S. Chandrasekaran, Z. Sung, D. A. Sergatskov, M. Checchin, S. Posen, M. Martinello, and G. Wu, ArXiv:1806.09824.
  * Bafia  _et al._ [2019] D. Bafia, A. Grassellino, O. Melnychuk, A. Romanenko, Z.-H. Sung, and J. Zasadzinski, in  _Proceedings of the 19th International Conference on RF Superconductivity_ (HZDR, Dresden, Germany, 2019) p. 586.
  * Melnychuk  _et al._ [2014] O. Melnychuk, A. Grassellino, and A. Romanenko, Rev. Sci. Instrum. 85, 124705 (2014).
  * Slater [1946] J. C. Slater, Rev. Mod. Phys. 18, 441 (1946).
  * Halbritter [1970] J. Halbritter, Institut für Experimentelle Kernphysik (IEKP), Report No. KFK-Extern 03/70-06 (1970).
  * Martinello  _et al._ [2016] M. Martinello, A. Grassellino, M. Checchin, A. Romanenko, O. Melnychuk, D. A. Sergatskov, S. Posen, and J. F. Zasadzinski, Appl. Phys. Lett. 109, 062601 (2016).
  * DeSorbo [1963] W. DeSorbo, Phys. Rev. 132, 107 (1963).
  * Trunin  _et al._ [1997] M. R. Trunin, A. A. Zhukov, and A. T. Sokolov, Zh. Eksp. Teor. Fiz. 111, 696 (1997).
  * Reuter and Sondheimer [1948] G. E. H. Reuter and E. H. Sondheimer, Proc. Roy. Soc. London Ser. A 195, 336 (1948).
  * Bafia [2020] D. Bafia, Ph.D. thesis, Illinois Institute of Technology (2020).
  * Dynes  _et al._ [1978] R. C. Dynes, V. Narayanamurti, and J. P. Garno, Phys. Rev. Lett. 41, 1509 (1978).
  * Kubo and Gurevich [2019] T. Kubo and A. Gurevich, Phys. Rev. B 100, 064522 (2019).
  * Kubo [2020] T. Kubo, Phys. Rev. Research 2, 013302 (2020).
  * Herman and Hlubina [2017] F. Herman and R. Hlubina, Phys. Rev. B 96, 014509 (2017).
  * Herman [2021] F. Herman, in  _Proceedings of the 20th International Conference on RF Superconductivity_ (2021) THPFDV010.
  * [33] N. R. Groll, G. Ciovati, A. Grassellino, A. Romanenko, J. F. Zasadzinski, and T. Proslier, ArXiv:1805.06359.
  * [34] While PCTS reports higher values of $\Gamma/\Delta_{0}$ for both N-doped and EP samples than what is shown in Fig. 4, this is likely due to differences in the probing depth between the two techniques, as PCTS is more surface sensitive and probes regions with more pair-breaking mechanisms.
  * Barra  _et al._ [2005] M. Barra, A. Cassinese, and R. Vaglio, Supercond. Sci. and Technol. 18, 271 (2005).
  * Varmazis  _et al._ [1975] C. Varmazis, J. R. Hook, D. J. Sandiford, and M. Strongin, Phys. Rev. B 11, 3354 (1975).
  * Kostić  _et al._ [1996] P. Kostić, B. Veal, A. P. Paulikas, U. Welp, V. R. Todt, C. Gu, U. Geiser, J. M. Williams, K. D. Carlson, and R. A. Klemm, Phys. Rev. B 53, 791 (1996).
  * Kogan and Prozorov [2020] V. G. Kogan and R. Prozorov, Phys. Rev. B 102, 184514 (2020).


# The matrices of argumentation frameworks

Xu Yuming
$School\ of\ Mathematics,Shandong\ University,Jinan,China$ Corresponding
author. E-mail<EMAIL_ADDRESS>
Abstract

We introduce matrix and its block to the Dung’s theory of argumentation
frameworks. It is showed that each argumentation framework has a matrix
representation, and the common extension-based semantics of argumentation
framework can be characterized by blocks of matrix and their relations. In
contrast with traditional method of directed graph, the matrix way has the
advantage of computability. Therefore, it has an extensive perspective to
bring the theory of matrix into the research of argumentation frameworks and
related areas.

Keywords: Argumentation framework; extension semantics; matrix; block

1\. Introduction

In recent years, the area of argumentation begins to become increasingly
central as a core study within Artificial Intelligence. A number of papers
investigated and compared the properties of different semantics which have
been proposed for argumentation frameworks (AFs, for short) as introduced by
Dung [8, 4, 3, 9, 6]. In early time, many of the analysis of arguments are
expressed in natural language. Later on, a tradition of using diagrams has
been developed to explicate the relations between the components of the
arguments. Now, argumentation frameworks are usually represented as directed
graphs, which play a significant role in modeling and analyzing the extension-
based semantics of AFs. For further notations and techniques of argumentation,
we refer the reader to [8, 2, 15, 1].

Our aim is to introduce matrix as a new mathematic tool to the research of
argumentation frameworks. First, we assign a matrix of order $n$ for each
argumentation framework with $n$ arguments. Each element of the matrix has
only two possible values: one and zero, where one represents the attack
relation and zero represents the non-attack relation between two arguments
(they can be the same one). Under this circumstance, the matrix can be thought
to be a representation of the argumentation framework. Secondly, we analysis
the internal structure of the matrix corresponding to various extension-based
semantics of the argumentation framework, and obtain the matrix approaches to
determine the stable extension, admissible extension and complete extension,
which can be easily realized on computer.

As will be seen in later, the matrix of an argumentation framework is not only
visualized as the directed graph, but also has another significant advantage
on the aspect of computation. We shall study various extension-based semantics
of the argumentation framework by comparing and computing the matrix of the AF
and its blocks.

2\. Dung’s theory of argumentation

Argumentation is a general approach to model defeasible reasoning and
justification in Artificial Intelligence. So far, many theories of
argumentation have been established. Among them, Dung’s theory of
argumentation framework is quite influence. In fact, it is abstract enough to
manage without any assumption on the nature of arguments and the attack
relation between arguments. Let us first recall some basic notion in Dung’s
theory of argumentation framework. We restrict them to finite argumentation
frameworks.

An argumentation framework is a pair $F=(A,R)$, where $A$ is a finite set of
arguments and $R\subset A\times A$ represents the attack-relation. For
$S\subset A$, we say that

(1) $S$ is conflict-free in $(A,R)$ if there are no $a,b\in S$ such that
$(a,b)\in R$;

(2) $a\in A$ is defeated by $S$ in $(A,R)$ if there is $b\in S$ such that
$(b,a)\in R$;

(3) $a\in A$ is defended by $S$ in $(A,R)$ if for each $b\in A$ with $(b,a)\in
R$, we have $b$ is

defeated by $S$ in $(A,R)$.

(4) $a\in A$ is acceptable with respect to $S$ if for each $b\in A$ with
$(b,a)\in R$, there is some

$c\in S$ such that $(c,b)\in R$.

The conflict-freeness, as observed by Baroni and Giacomin[1] in their study of
evaluative criteria for extension-based semantics, is viewed as a minimal
requirement to be satisfied within any computationally sensible notion of
”collection of justified arguments”. However, it is too weak a condition to be
applied as a reasonable guarantor that a set of arguments is ”collectively
acceptable”.

Semantics for argumentation frameworks can be given by a function $\sigma$
which assigns each AF $F=(A,R)$ a collection $\mathcal{S}\subset 2^{A}$ of
extensions. Here, we mainly focus on the semantic
$\sigma\in\\{s,a,p,c,g,i,ss,e\\}$ for stable, admissible, preferred, complete,
grounded, ideal, semi-stable and eager extensions, respectively.

Definition 1[14] Let $F=(A,R)$ be an argumentation framework and $S\in A$.

(1) $S$ is a stable extension of $F$, $i.e.$, $S\in s(F)$, if $S$ is conflict-
free in $F$ and each

$a\in A\setminus S$ is defeated by $S$ in $F$.

(2) $S$ is an admissible extension of $F$, $i.e.$, $S\in a(F)$, if $S$ is
conflict-free in $F$ and each

$a\in A\setminus S$ is defended by $S$ in $F$.

(3) $S$ is a preferred extension of $F$, $i.e.$, $S\in p(F)$, if $S\in a(F)$
and for each $T\in a(F)$,

we have $S\not\subset T$.

(4) $S$ is a complete extension of $F$, $i.e.$, $S\in c(F)$, if $S\in a(F)$
and for each $a\in A$

defended by $S$ in $F$, we have $a\in S$.

(5) $S$ is a grounded extension of $F$, $i.e.$, $S\in g(F)$, if $S\in c(F)$
and for each $T\in c(F)$,

we have $T\not\subset S$.

(6) $S$ is an ideal extension of $F$, $i.e.$, $S\in i(F)$, if $S\in a(F)$,
$S\subset\cap\\{T:T\in p(F)\\}$ and

for each $U\in a(F)$ such that $U\subset\cap\\{T:T\in p(F)\\}$, we have
$S\not\subset U$.

(7) $S$ is a semi-stable extension of $F$, $i.e.$, $S\in ss(F)$, if $S\in
a(F)$ and for each $T\in a(F)$,

we have $R^{+}(S)\not\subset R^{+}(T)$, where $R^{+}(U)=\\{U\cap\\{b:(a,b)\in
R,A\in U\\}\\}$.

(8) $S$ is a eager extension of $F$, $i.e.$, $S\in e(F)$, if $S\in c(F)$,
$S\subset\cap\\{T:T\in ss(F)\\}$ and

for each $U\in a(F)$ such that $U\subset\cap\\{T:T\in ss(F)\\}$, we have
$S\not\subset T$.

Note that, there are some elementary properties for any argumentation
framework $F=(A,R)$ and semantic $\sigma$. If $\sigma\in\\{a,p,c,g\\}$, then
we have $\sigma(F)\neq\emptyset$. And if $\sigma\in\\{g,i,e\\}$, then
$\sigma(F)$ contains exactly one extension. Furthermore, the following
relations hold for each argumentation framework $F=(A,R)$:

$s(F)\subseteq p(F)\subseteq c(F)\subseteq a(F)$.

Since every extension of an AF under the standard semantics (stable,
preferred, complete and grounded extensions) introduced by Dung is an
admissible set, the concept of admissible extensions plays an important role
in the study of argumentation frameworks.

3\. The matrix of an argumentation framework

We know that the directed graph is a traditional tool in the research of
argumentation frameworks, and has the feature of visualization [7, 10, 11]. It
is widely used for modeling and analyzing argumentation frameworks. In this
section, we shall introduce the matrix representation of argumentation
frameworks. Except for the visualization, the matrix also has the advantage of
computability in analyzing argumentation frameworks and computing various
extension semantics.

An $m\times n$ matrix $A$ is a rectangular array of numbers, consisting of $m$
rows and $n$ columns, denoted by

$A=\left(\begin{array}[]{cccccc}a_{1,1}&a_{1,2}&.&.&.&a_{1,n}\\\
a_{2,1}&a_{2,2}&.&.&.&a_{2,n}\\\ .&.&.&.&.&.\\\
a_{m,1}&a_{m,2}&.&.&.&a_{m,n}\end{array}\right).$

The $m\times n$ numbers $a_{1,1},a_{1,2},...,a_{m,n}$ are the elements of the
matrix $A$. We often called $a_{i,j}$ the $(i,j)$th element, and write
$A=(a_{i,j})$ for short. It is important to remember that the first suffix of
$a_{i,j}$ indicates the row and the second the column of $a_{i,j}$.

A column matrix is an $n\times 1$ matrix, and a row matrix is an $1\times n$
matrix, denoted by

$\left(\begin{array}[]{c}x_{1}\\\ x_{2}\\\ .\\\ .\\\ .\\\
x_{n}\end{array}\right),\left(\begin{array}[]{cccccc}x_{1}&x_{2}&.&.&.&x_{n}\end{array}\right)$

respectively. Matrices of both these types can be regarded as vectors and
referred to respectively as column vectors and row vectors. Usually, the $i$th
row of a matrix $A$ is denoted by $A_{i,*}$, and the $j$th column of $A$ is
denoted by $A_{*,j}$.

Definition 2 In an $n\times m$ matrix $A=(a_{i,j})$, we specify any $k(\leq
min\\{n,m\\})$ different rows $i_{1},i_{2},...,i_{k}$ and the same number of
different columns $i_{1},i_{2},...,i_{k}$. The elements appearing at the
intersections of these rows and columns form a square matrix of order $k$. We
call this matrix a principal block of order $k$ of the original matrix $A$; it
is denoted by

$M=\left(\begin{array}[]{cccccc}a_{i_{1},i_{1}}&a_{i_{1},i_{2}}&.&.&.&a_{i_{1},i_{k}}\\\
a_{i_{2},i_{1}}&a_{i_{2},i_{2}}&.&.&.&a_{i_{2},i_{k}}\\\ .&.&.&.&.&.\\\
a_{i_{k},i_{1}}&a_{i_{k},i_{2}}&.&.&.&a_{i_{k},i_{k}}\end{array}\right),$

or $M=M_{i_{1},i_{2},...,i_{k}}^{i_{1},i_{2},...,i_{k}}$ for short.

Definition 3 If in the original $n\times m$ matrix $A=(a_{i,j})$, we delete
the rows and columns which make up the block
$M=M^{i_{1},i_{2},...,i_{k}}_{i_{1},i_{2},...,i_{k}}$, then the remaining
elements form an $(n-k)\times(m-k)$ matrix. We call this matrix the
complementary block of $M$, and is denoted by the symbol
$\overline{M}=\overline{M_{i_{1},i_{2},...,i_{k}}^{i_{1},i_{2},...,i_{k}}}$.

Definition 4 In an $n\times m$ matrix $A$, we specify any $k(\leq n)$
different rows $i_{1},i_{2},...,i_{k}$ and $h(\leq m)$ different columns
$j_{1},j_{2},...,j_{h}$. The elements appearing at the intersections of these
rows and columns form a $k\times h$ matrix. We call this matrix a $k\times h$
block of the original matrix $A$; it is denoted by

$M=\left(\begin{array}[]{cccccc}a_{i_{1},j_{1}}&a_{i_{1},j_{2}}&.&.&.&a_{i_{1},j_{h}}\\\
a_{i_{2},j_{1}}&a_{i_{2},j_{2}}&.&.&.&a_{i_{2},j_{h}}\\\ .&.&.&.&.&.\\\
a_{i_{k},j_{1}}&a_{i_{k},j_{2}}&.&.&.&a_{i_{k},j_{h}}\end{array}\right),$

or $M=M_{i_{1},i_{2},...,i_{k}}^{j_{1},j_{2},...,j_{h}}$ for short.

For the underlying set $A$ of an argumentation framework $F=(A,R)$, there is
no ordering in nature. But, in many cases the ordering set can benefit us a
lot. Contrasting with the form $A=\\{a,b,...\\}$, it is more convenience to
put $A=\\{1,2,...,n\\}$ while the cardinality of $A$ is large. In particular,
we can map each argument to the corresponding row and column of a matrix. We
will follow this arrangement in the below discussion.

Definition 5 Let $F=(A,R)$ be an argumentation framework with
$A=\\{1,2,...,n\\}$. The matrix of $F$, denoted by $M(F)$, is a Boolean matrix
of order $n$, its element is determined by the following rules:

(1) $a_{i,j}=1$ iff $(i,j)\in R$;

(2) $a_{i,j}=0$ iff $(i,j)\notin R$.

Example 6 Considering the argumentation framework $F=(A,R)$, where
$A=\\{1,2,3\\}$ and $R=\\{(1,2),(2,3),(3,1)\\}$. By the definition, we have
the following matrix of $F$:

$M(F)=\left(\begin{array}[]{ccc}0&1&0\\\ 0&0&1\\\ 1&0&0\end{array}\right)$

Example 7 Given an argumentation framework $F=(A,R)$, where $A=\\{1,2,3,4\\}$
and $R=\\{(1,2),(1,3),(2,1),(2,3),(3,4)\\}$. The matrix of $F$ is as follows:

$M(F)=\left(\begin{array}[]{cccc}0&1&1&0\\\ 1&0&1&0\\\ 0&0&0&1\\\
0&0&0&0\end{array}\right)$

In comparison with graph-theoretic way and mathematical logic way, the matrix
of an argumentation framework has many excellent features. First, it possess a
concise mathematical format. Secondly, it contains all information of the $AF$
by combining the arguments with attack relation in a specific manner in the
matrix $M(F)$. Also, it can be deal with by program on computer. The most
important is that we can import the knowledge of matrix to the research of
argumentation frameworks.

4\. Determination of the conflict-free sets

As we know, there is no efficient method for us to decide a conflict set in an
argumentation framework, even we can draw up the directed graph of the AF.
After we introduce the matrix of the AF, the situation will be changed
completely. By checking the matrix of the argumentation framework, we can
easily find out all the conflict-free sets of the AF. Let us see an example,
firstly.

Example 8 Given an argumentation framework $F=(A,R)$, where
$A=\\{1,2,3,4,5\\}$ and $R=\\{(1,2),(2,3),(2,5),(4,3),(5,4)\\}$. Then, we can
easily to show that the collection of conflict-free sets of $F$ is

$\\{\emptyset,\\{1\\},\\{2\\},\\{3\\},\\{4\\},\\{5\\}\\{1,3\\},\\{1,4\\},\\{1,5\\},\\{2,4\\},\\{3,5\\},\\{1,3,5\\}\\}$,

by the routine method of directed graph.

On the other hand, we consider the matrix of $F=(A,R)$ and study its structure
from the level of blocks. First, we write out the matrix of $F$:

$M(F)=\left(\begin{array}[]{ccccc}0&1&0&0&0\\\ 0&0&1&0&1\\\ 0&0&0&0&0\\\
0&0&1&0&0\\\ 0&0&0&1&0\end{array}\right).$

By observing the principal blocks of the above matrix, we find that there are
five zero principal blocks of order 1

$M^{1}_{1}=\left(\begin{array}[]{c}0\end{array}\right),M^{2}_{2}=\left(\begin{array}[]{c}0\end{array}\right),M^{3}_{3}=\left(\begin{array}[]{c}0\end{array}\right),M^{4}_{4}=\left(\begin{array}[]{c}0\end{array}\right),M^{5}_{5}=\left(\begin{array}[]{c}0\end{array}\right)$

corresponding to the conflict-free sets $\\{1\\}$, $\\{2\\}$, $\\{3\\}$,
$\\{4\\}$, $\\{5\\}$, respectively. There are five zero principal blocks of
order 2

$M^{1,3}_{1,3}=\left(\begin{array}[]{cc}0&0\\\
0&0\end{array}\right),M^{1,4}_{1,4}=\left(\begin{array}[]{cc}0&0\\\
0&0\end{array}\right),M^{1,5}_{1,5}=\left(\begin{array}[]{cc}0&0\\\
0&0\end{array}\right),M^{2,4}_{2,4}=\left(\begin{array}[]{cc}0&0\\\
0&0\end{array}\right),M^{3,5}_{3,5}=\left(\begin{array}[]{cc}0&0\\\
0&0\end{array}\right)$

corresponding to the conflict-free sets $\\{1,3\\}$, $\\{1,4\\}$, $\\{1,5\\}$,
$\\{2,4\\}$, $\\{3,5\\}$, respectively. Also, there is a zero principal block
of order 3

$M^{1,3,5}_{1,3,5}=\left(\begin{array}[]{ccc}0&0&0\\\ 0&0&0\\\
0&0&0\end{array}\right)$

corresponding to the conflict-free sets $\\{1,3,5\\}$.

Note that, the above blocks are all principal blocks which are zero in the
matrix $M(F)$, and there is a one to one correspond between the collection of
all conflict-free sets of $F$ and the set of all zero principal blocks of
$M(F)$. In fact, for any argumentation framework $F$ there exists such
corresponding relation between the collection of all conflict-free sets of $F$
and the set of all zero principal blocks of $M(F)$.

Since it is easy to find out the zero principal blocks in the matrix of an
argumentation framework, we obtain a good way to decide the conflict-free sets
of the $AF$ through its matrix. Certainly, this way can be carried out on the
computer readily.

Definition 9 Let $F=(A,R)$ be an argumentation framework with
$A=\\{1,2,...,n\\}$, and $S=\\{i_{1},i_{2},...,i_{k}\\}\subset A$. The
principal block

$M^{i_{1},i_{2},...,i_{k}}_{i_{1},i_{2},...,i_{k}}=\left(\begin{array}[]{cccccc}a_{i_{1},i_{1}}&a_{i_{1},i_{2}}&.&.&.&a_{i_{1},i_{k}}\\\
a_{i_{2},i_{1}}&a_{i_{2},i_{2}}&.&.&.&a_{i_{2},i_{k}}\\\ .&.&.&.&.&.\\\
a_{i_{k},i_{1}}&a_{i_{k},i_{2}}&.&.&.&a_{i_{k},i_{k}}\end{array}\right)$

of order $k$ in the matrix $M(F)$ is called the $cf$-block of $S$, and denoted
by $M^{cf}$.

Theorem 10 Given an argumentation framework $F=(A,R)$ with
$A=\\{1,2,...,n\\}$, then $S=\\{i_{1},i_{2},...,i_{k}\\}\subset A$ is a
conflict-free set in $F$ iff the $cf$-block
$M^{i_{1},i_{2},...,i_{k}}_{i_{1},i_{2},...,i_{k}}$ of $S$ is zero.

Proof Assume that $M^{i_{1},i_{2},...,i_{k}}_{i_{1},i_{2},...,i_{k}}=0$, then
for arbitrary $1\leq s,t\leq k$ we have $a_{i_{s},i_{t}}=0$, $i.e.$,
$(i_{s},i_{t})\notin R$. Thus, $S=\\{i_{1},i_{2},...,i_{k}\\}$ is a conflict-
free set in $F$.

Suppose $S=\\{i_{1},i_{2},...,i_{k}\\}\subset A$ is a conflict-free set in
$F$, then for arbitrary $1\leq s,t\leq k$ we have that $(i_{s},i_{t})\notin
R$, $i.e.$, $a_{i_{s},i_{t}}=0$. Therefore, we have
$M^{i_{1},i_{2},...,i_{k}}_{i_{1},i_{2},...,i_{k}}=0$.

5\. Determination of the stable extensions

Example 11 We continuous to study the argumentation framework $F=(A,R)$, where
$A=\\{1,2,3,4,5\\}$ and $R=\\{(1,2),(2,3),(2,5),(4,3),(5,4)\\}$. Since the
stable extension is firstly a conflict-free set, we can look for the stable
extension from the collection

$\\{\emptyset,\\{1\\},\\{2\\},\\{3\\},\\{4\\},\\{5\\}\\{1,3\\},\\{1,4\\},\\{1,5\\},\\{2,4\\},\\{3,5\\},\\{1,3,5\\}\\}$

of conflict-free sets. In fact, the set $S=\\{1,3,5\\}$ is the only stable
extension in $F$ by a simple discussion.

Again, we turn our attention to the matrix of the $F=(A,R)$:

$M(F)=\left(\begin{array}[]{ccccc}0&1&0&0&0\\\ 0&0&1&0&1\\\ 0&0&0&0&0\\\
0&0&1&0&0\\\ 0&0&0&1&0\end{array}\right).$

Since $S=\\{1,3,5\\}$ is a stable extension of $F$, the arguments $2$ and $4$
are defeated by $\\{1,3,5\\}$. This fact is reflected in the matrix $M(F)$ of
$F$ as follows.

In the column vector $F_{*,2}$ (column 2), $a_{1,2}=1$ means that $(1,2)\in
R$, and thus the argument $1$ attacks the argument $2$. In the column vector
$F_{*,4}$ (column 4), $a_{5,4}=1$ means that $(5,4)\in R$, and thus the
argument $5$ attacks the argument $4$.

From the behavior of the elements $a_{1,2}=1$ and $a_{5,4}=1$ in the matrix
$M(F)$, we can extract a matrix approach to decide that the conflict-free set
$S=\\{1,3,5\\}$ is a stable extension: Corresponding to the arguments $2,4\in
A\setminus S$, we firstly pick out the column vectors $F_{*,2}$ and $F_{*,4}$
in the matrix $M(F)$, then check the elements $a_{1,2},a_{3,2},a_{5,2}$ of
$F_{*,2}$, and the elements $a_{1,4},a_{3,4},a_{5,4}$ of $F_{*,4}$. If there
is one element of $\\{a_{1,2},a_{3,2},a_{5,2}\\}$ which is non-zero, then the
argument $2$ is defeated by $S$. Similar result is hold for the argument $4$.
This process leads to a block of the matrix $M(F)$ at the intersection of
columns $2,4$ and rows $1,3,5$.

To sum up, we can decide that the conflict set $S=\\{1,3,5\\}$ is a stable
extension by the fact that the two column vectors of the above block of the
matrix $M(F)$ are all non-zero. Further analysis indicates that the converse
is also true. This motivation makes us to give the following definition.

Definition 12 Let $F=(A,R)$ be an argumentation framework with
$A=\\{1,2,...,n\\}$, and $S=\\{i_{1},i_{2},...,i_{k}\\}\subset A$ is a stable
extension of $F$. The $k\times h$ block

$M^{i_{1},i_{2},...,i_{k}}_{j_{1},j_{2},...,j_{h}}=\left(\begin{array}[]{cccccc}a_{i_{1},j_{1}}&a_{i_{1},j_{2}}&.&.&.&a_{i_{1},j_{h}}\\\
a_{i_{2},j_{1}}&a_{i_{2},j_{2}}&.&.&.&a_{i_{2},j_{h}}\\\ .&.&.&.&.&.\\\
a_{i_{k},j_{1}}&a_{i_{k},j_{2}}&.&.&.&a_{i_{k},j_{h}}\end{array}\right)$

in the matrix $M(F)$ is called the $s$-block of $S$ and denoted by $M^{s}$,
where $\\{j_{1},j_{2},...,j_{h}\\}=A\setminus S$.

In other words, the elements appearing at the intersections of rows
$i_{1},i_{2},...,i_{k}$ and columns $j_{1},j_{2},...,j_{h}$ in the matrix
$M(F)$ form the $s$-block $M^{i_{1},i_{2},...,i_{k}}_{j_{1},j_{2},...,j_{h}}$
of $S$.

Theorem 13 Given an argumentation framework $F=(A,R)$ with
$A=\\{1,2,...,n\\}$, then $S=\\{i_{1},i_{2},...,i_{k}\\}\subset A$ is a stable
extension in $F$ iff the following conditions hold:

(1) The $cf$-block $M^{i_{1},i_{2},...,i_{k}}_{i_{1},i_{2},...,i_{k}}$ of $S$
is zero,

(2) Every column vector of the $s$-block
$M^{i_{1},i_{2},...,i_{k}}_{j_{1},j_{2},...,j_{h}}$ of $S$ is non-zero, where
$A\setminus S$

$=\\{j_{1},j_{2},...,j_{h}\\}$.

Proof Let $S$ be a conflict-free set and $A\setminus
S=\\{j_{1},j_{2},...,j_{h}\\}$, then we need only to prove that every element
of $A\setminus S(1\leq t\leq h)$ is defeated by $S$ in $F$ iff all column
vectors of the $s$-block $M^{i_{1},i_{2},...,i_{k}}_{j_{1},j_{2},...,j_{h}}$
of $S$ are non-zero.

Assume that every element of $A\setminus S(1\leq t\leq h)$ is defeated by $S$
in $F$. Take any column vector $A_{*,j_{t}}(1\leq t\leq h)$ of the $s$-block
$M^{i_{1},i_{2},...,i_{k}}_{j_{1},j_{2},...,j_{h}}$ of $S$, then we have
$j_{t}\in A\setminus S$. By the assumption, there is some element $i_{r}\in
S(1\leq r\leq k)$ such that the argument $i_{r}$ attacks the argument $j_{t}$,
$i.e.$, $(i_{r},j_{t})\in R$. It follows that $a_{i_{r},j_{t}}=1$ in the
matrix $M(F)$ and the $s$-block
$M^{i_{1},i_{2},...,i_{k}}_{j_{1},j_{2},...,j_{h}}$ of $S$, and thus the
column vector $A_{*,j_{t}}$ is non-zero.

Conversely, suppose that all column vectors of the $s$-block
$M^{i_{1},i_{2},...,i_{k}}_{j_{1},j_{2},...,j_{h}}=M^{s}$ of $S$ are non-zero.
Take any element $j_{t}\in A\setminus S(1\leq t\leq h)$, then
$M^{s}_{*,j_{t}}$ is a column vector of the $s$-block
$M^{i_{1},i_{2},...,i_{k}}_{j_{1},j_{2},...,j_{h}}=M^{s}$ of $S$. By the
hypothesis, we know that $A_{*,j_{t}}$ is non-zero. Therefore, there is some
$i_{r}\in S(1\leq r\leq k)$ such that $a_{i_{r},j_{t}}=1$, $i.e.$,
$(i_{r},j_{t})\in R$. This means that the argument $i_{r}$ attacks the
argument $j_{t}$ of $S$ in $F$, and thus we claim that $j_{t}$ is defeated by
$S$ in $F$.

6\. Determination of the admissible extensions

Example 14 Let us return to the argumentation framework $F=(A,R)$, where
$A=\\{1,2,3,4,5\\}$ and $R=\\{(1,2),(2,3),(2,5),(4,3),(5,4)\\}$. Since an
admissible extension is necessarily a conflict-free set, we can look for the
admissible extension from the collection

$\\{\emptyset,\\{1\\},\\{2\\},\\{3\\},\\{4\\},\\{5\\}\\{1,3\\},\\{1,4\\},\\{1,5\\},\\{2,4\\},\\{3,5\\},\\{1,3,5\\}\\}$

of conflict-free sets. By definition, it is easy to check that $\\{1\\}$,
$\\{1,5\\}$ and $\\{1,3,5\\}$ are all the admissible extensions in $F$.

Since $\\{1,3,5\\}$ is also a stable extension and $\\{1\\}$ is not typical
enough as an admissible extension in $F$, we will mainly concentrate on the
admissible extension $S=\\{1,5\\}$ which is not a stable extension in $F$.

First, we write out the matrix of argumentation framework $F=(A,R)$:

$M(F)=\left(\begin{array}[]{ccccc}0&1&0&0&0\\\ 0&0&1&0&1\\\ 0&0&0&0&0\\\
0&0&1&0&0\\\ 0&0&0&1&0\end{array}\right).$

Secondly, we study the structure of the matrix $M(F)$ of $F$ to find out the
internal properties which can reflect the fact that $S=\\{1,5\\}$ is an
admissible extension.

In the column vector $M(F)_{*,5}$ of the matrix $M(F)$, $a_{2,5}=1$ means that
$(2,5)\in R$, $i.e.$, the argument $2$ attacks the argument $5$. Under this
circumstance, the element $a_{1,2}=1$ in the row vector $M(F)_{*,2}$ of the
matrix $M(F)$ implies that $(1,2)\in R$, $i.e.$, the argument $1$ attacks the
argument $2$. This illustrates that the argument $5$ is defended by
$\\{1,5\\}$ in $F$. In the column vector $M(F)_{*,1}$ of the matrix $M(F)$, we
have $a_{i,1}=0$ for each $1\leq i\leq 5$. It follows that the argument $1$ is
defended by $\\{1,5\\}$ in $F$.

In the above analysis, the behavior of $a_{2,5}=1$ and $a_{1,2}=1$ in the
matrix $M(F)$ is intrinsic for the fact that the argument $5$ is defended by
$\\{1,5\\}$ in $F$. This inspires us a general idea to decide the conflict-
free set $S=\\{1,5\\}$ to be admissible through the structure of the matrix
$M(F)$ of $F$.

(1) In order to decide whether the arguments of $\\{1,5\\}=S$ are defended by
$S$, we should firstly find the attackers of the argument $1$ and $5$. So, we
must pick out the column vectors $M(F)_{*,1}$ and $M(F)_{*,5}$ of the matrix
$M(F)$ corresponding to the arguments $1$ and $5$ respectively. Since the set
$S$ is conflict-free, there is no attack relation between $1$ and $5$, $i.e.$,
$a_{1,1}=0,a_{5,1}=0,a_{1,5}=0,a_{5,5}=0$. Therefore, we only need to check
the elements $a_{2,1},a_{3,1},a_{4,1}$ of the column vector $M(F)_{*,1}$, and
the elements $a_{2,5},a_{3,5},a_{4,5}$ of the column vector $M(F)_{*,5}$. Each
non-zero element of the set $\\{a_{2,1},a_{3,1},a_{4,1}\\}$ tells us an
attacker of the argument $1$, and each non-zero element of the set
$\\{a_{2,5},a_{3,5},a_{4,5}\\}$ tells us an attacker of the argument $5$. This
leads to a block of the matrix $M(F)$ at the intersection of column $1,5$ and
row $2,3,4$, which is exactly the $s$-block of $S$.

(2) After having determined the attackers $(\in\\{2,3,4\\})$ of the argument
$1$ and $5$, we should secondly to check whether these attackers are defeated
by $S=\\{1,5\\}$. For example, $a_{2,5}=1$ means that the argument $2$ is an
attacker of the argument $5$. So, we should check the element $a_{1,2}$ and
$a_{5,2}$ to see whether the attacker $2$ of the argument $5$ is defeated by
$\\{1,5\\}$. Similar situation holds for any other attackers of the argument
$1$ and $5$. Namely, we need also to check the elements $a_{1,3},a_{5,3}$ ( if
the argument $3$ is an attacker of the argument $1$ or $5$ ) and elements
$a_{1,4},a_{5,4}$ ( if the argument $4$ is an attacker of the argument $1$ or
$5$). This process leads to a block of the matrix $M(F)$ at the intersection
of columns $2,3,4$ and rows $1,5$.

In summary, we need to check two blocks (related to $S=\\{1,5\\}$) of the
matrix $M(F)$ in order to decide that the conflict-free set $S=\\{1,5\\}$ is
an admissible extension. This motivate us to give the following definition.

Definition 15 Let $F=(A,R)$ be an argumentation framework with
$A=\\{1,2,...,n\\}$, and $S=\\{i_{1},i_{2},...,i_{k}\\}\subset A$ is an
admissible extension of $F$. The $h\times k$ block

$M^{j_{1},j_{2},...,j_{h}}_{i_{1},i_{2},...,i_{k}}=\left(\begin{array}[]{cccccc}a_{j_{1},i_{1}}&a_{j_{1},i_{2}}&.&.&.&a_{j_{1},i_{k}}\\\
a_{j_{2},i_{1}}&a_{j_{2},i_{2}}&.&.&.&a_{j_{2},i_{k}}\\\ .&.&.&.&.&.\\\
a_{j_{h},i_{1}}&a_{j_{h},i_{2}}&.&.&.&a_{j_{h},i_{k}}\end{array}\right)$

of the matrix $M(F)$ is called the $a$-block of $S$ and denoted by $M^{a}$,
where $\\{j_{1},j_{2},...,j_{h}\\}=A\setminus S$.

In other words, the elements appearing at the intersection of rows
$j_{1},j_{2},...,j_{h}$ and columns $i_{1},i_{2},...,i_{k}$ in the matrix
$M(F)$ form the $a$-block $M^{j_{1},j_{2},...,j_{h}}_{i_{1},i_{2},...,i_{k}}$
of $S$.

Note that, there is a natural relation between the $a$-block
$M^{j_{1},j_{2},...,j_{h}}_{i_{1},i_{2},...,i_{k}}$ and the $s$-block
$M^{i_{1},i_{2},...,i_{k}}_{j_{1},j_{2},...,j_{h}}$ in matrix theory. Namely,
the $a$-block $M^{j_{1},j_{2},...,j_{h}}_{i_{1},i_{2},...,i_{k}}$ of $S$ is
precisely the complementary block of the $s$-block
$M^{i_{1},i_{2},...,i_{k}}_{j_{1},j_{2},...,j_{h}}$ of $S$ in the matrix
$M(F)$.

For convenience, in this section we may assume that the sequences
$i_{1},i_{2},...,i_{k}$ and $j_{1},j_{2},...,j_{h}$ are all increasing.

Theorem 16 Given an argumentation framework $F=(A,R)$ with
$A=\\{1,2,...,n\\}$, then $S=\\{i_{1},i_{2},...,i_{k}\\}\subset A$ is an
admissible extension in $F$ iff the following conditions hold:

(1) The $cf$-block $M^{i_{1},i_{2},...,i_{k}}_{i_{1},i_{2},...,i_{k}}$ of $S$
is zero,

(2) The column vector of $s$-block
$M^{i_{1},i_{2},...,i_{k}}_{j_{1},j_{2},...,j_{h}}$ of $S$ corresponding to
the non-zero row

vector of the $a$-block $M^{j_{1},j_{2},...,j_{h}}_{i_{1},i_{2},...,i_{k}}$ of
$S$ is non-zero, where $A\setminus S=\\{j_{1},j_{2},...,j_{h}\\}$.

Proof Let $S$ be a conflict-free set and $A\setminus
S=\\{j_{1},j_{2},...,j_{h}\\}$. We need only to prove that every $i_{r}\in
S(1\leq r\leq k)$ is defended by $S$ in $F$ iff the column vector of $s$-block
$M^{i_{1},i_{2},...,i_{k}}_{j_{1},j_{2},...,j_{h}}$ of $S$ corresponding to
the non-zero row vector of the $a$-block
$M^{j_{1},j_{2},...,j_{h}}_{i_{1},i_{2},...,i_{k}}$ of $S$ is non-zero

Assume that every $i_{r}\in S(1\leq r\leq k)$ is defended by $S$ in $F$. If
the row vector $M^{a}_{t,*}(1\leq t\leq h)$ of the $a$-block
$M^{j_{1},j_{2},...,j_{h}}_{i_{1},i_{2},...,i_{k}}=M^{a}$ of $S$ is non-zero,
then there is some $i_{r}(1\leq r\leq k)$ such that $a_{j_{t},i_{r}}=1$. Note
that $a_{j_{t},i_{r}}$ is at the intersection of row $t$ and column $r$ of the
$a$-block $M^{a}$ of $S$, and at the intersection of row $j_{t}$ and column
$i_{r}$ of the matrix $M(F)$. This implies that $(j_{t},i_{r})\in R$, $i.e.$,
the argument $j_{t}$ attacks the argument $i_{r}$. By the assumption, there is
some $i_{q}\in S(1\leq q\leq k)$ such that the argument $i_{q}$ attacks the
argument $j_{t}$, $i.e.$, $(i_{q},j_{t})\in R$. It follows that
$a_{i_{q},j_{t}}=1$ in the matrix $M(F)$. But, $a_{i_{q},j_{t}}$ is also an
element of the $s$-block $M^{s}$, which is at the intersection of row $q$ and
column $t$ of $M^{s}$. Namely, $a_{i_{q},j_{t}}$ is an element of the column
vector $M^{s}_{*,t}$ of $M_{s}$. Therefore, we conclude that the column vector
$M^{s}_{*,t}$ of $s$-block
$M^{i_{1},i_{2},...,i_{k}}_{j_{1},j_{2},...,j_{h}}=M^{s}$ of $S$ is non-zero.

Conversely, suppose that the column vector of $s$-block
$M^{i_{1},i_{2},...,i_{k}}_{j_{1},j_{2},...,j_{h}}$ of $S$ corresponding to
the non-zero row vector of the $a$-block
$M^{j_{1},j_{2},...,j_{h}}_{i_{1},i_{2},...,i_{k}}$ of $S$ is non-zero. For
any fixed $i_{r}\in S(1\leq r\leq k)$, if there is no $j_{t}\in A\setminus
S(1\leq t\leq h)$ such that the argument $j_{t}$ attacks the argument $i_{r}$,
then by the fact that $S$ is a conflict-free set we claim that there is no
$i\in A$ such that the argument $i$ attacks the argument $i_{r}$. It follows
that argument $i_{r}\in S$ is defended by $S$ in $F$.

Otherwise, there is some $j_{t}\in A\setminus S(1\leq t\leq h)$ such that the
argument $j_{t}$ attacks the argument $i_{r}$. It follows that
$(j_{t},i_{r})\in R$, $i.e.$, $a_{j_{t},i_{r}}=1$. Since the element
$a_{j_{t},i_{r}}$ is at the intersection of row $t$ and column $r$ of the
$a$-block $M^{j_{1},j_{2},...,j_{h}}_{i_{1},i_{2},...,i_{k}}=M^{a}$ of $S$,
the row vector $M^{a}_{t,*}$ of the $a$-block $M^{a}$ of $S$ is non-zero. By
the assumption, we conclude that the corresponding column vector $M^{s}_{*,t}$
of the $s$-block $M^{i_{1},i_{2},...,i_{k}}_{j_{1},j_{2},...,j_{h}}=M^{s}$ of
$S$ is non-zero. Therefore, there is some $i_{q}\in S(1\leq q\leq k)$ such
that $a_{i_{q},j_{t}}=1$. Note that, the element $a_{i_{q},j_{t}}$ is at the
intersection of row $q$ and column $t$ of the $s$-block
$M^{i_{1},i_{2},...,i_{k}}_{j_{1},j_{2},...,j_{h}}$ and at the intersection of
row $i_{q}$ and column $j_{t}$ of the matrix $M(F)$. Consequently, we have
that $(i_{q},j_{t})\in R$, $i.e.$, the argument $i_{q}\in S$ attacks the
argument $j_{t}$. Now, we have proved that the argument $i_{r}\in S$ is also
defended by $S$ in $F$.

Remark: The fact that any stable extension must be admissible is clearly
expressed by the properties of $s$-blocks in the matrix. In other words, the
condition every column vector of the $s$-block
$M^{i_{1},i_{2},...,i_{k}}_{j_{1},j_{2},...,j_{h}}$ of $S$ are non-zero is
stronger than that the column vector of the $s$-block
$M^{i_{1},i_{2},...,i_{k}}_{j_{1},j_{2},...,j_{h}}$ of $S$ corresponding to
the non-zero row vector of the $a$-block
$M^{j_{1},j_{2},...,j_{h}}_{i_{1},i_{2},...,i_{k}}$ of $S$ is non-zero.

7\. Determination of the complete extensions

Example 17 Consider the argumentation framework $F=(A,R)$, where
$A=\\{1,2,3,4,5\\}$ and $R=\\{(1,2),(2,3),\\{2,4\\},(2,5),(4,3),(5,4)\\}$.
Since the admissible extension is necessarily a conflict-free set, we can find
out the admissible extension from the collection of conflict-free sets

$\\{\emptyset,\\{1\\},\\{2\\},\\{3\\},\\{4\\},\\{5\\}\\{1,3\\},\\{1,4\\},\\{1,5\\},\\{3,5\\},\\{1,3,5\\}\\}$.

By the directed graph of $F$, it is easy to check that $\\{1,5\\}$ and
$\\{1,3,5\\}$ are all the admissible extensions in $F$. Furthermore, one can
verify that $S_{1}=\\{1,3,5\\}$ is the only complete extension in $F$, while
$S_{2}=\\{1,5\\}$ is not.

Next, we will analysis the different expressions in the matrix $M(F)$ of $F$
between $\\{1,3,5\\}$ (as a complete extension but not an admissible
extension) and $\\{1,5\\}$ (as an admissible extension). By comparing them, we
extract the matrix method to decide that an admissible extension is complete.

Let us firstly write out the matrix of the argumentation framework $F$:

$M(F)=\left(\begin{array}[]{ccccc}0&1&0&0&0\\\ 0&0&1&1&1\\\ 0&0&0&0&0\\\
0&0&1&0&0\\\ 0&0&0&1&0\end{array}\right).$

In the column vector $M(F)_{*,2}$ of the matrix $M(F)$, $a_{1,2}=1$ means that
$(1,2)\in R$, $i.e.$, the argument $1$ attacks the argument $2$. Since
$S_{1}=\\{1,3,5\\}$ is a conflict-free set, there is no element of $S_{1}$
which attacks the argument $1$. It follows that the arguments $2$ is not
defended by $S_{1}$ in $F$. In the column vector $M(F)_{*,4}$ of the matrix
$M(F)$, $a_{5,4}=1$ means that $(5,4)\in R$, $i.e.$, the argument $5$ attacks
the argument $4$. Also because that $S_{1}=\\{1,3,5\\}$ is a conflict-free
set, there is no element of $S_{1}$ which attacks the argument $5$. Thus, we
have that the arguments $4$ is not defended by $S_{1}$ in $F$. These are
exactly the reasons for the admissible extension $S_{1}=\\{1,3,5\\}$ to be a
complete extension.

Next, we will mainly focus our attention on the argument $3$ with respect to
$S_{2}=\\{1,5\\}$.

In the column vector $M(F)_{*,3}$ of the matrix $M(F)$, $a_{2,3}=1$ means that
$(2,3)\in R$, and $a_{4,3}=1$ means that $(4,3)\in R$. Therefore, both
arguments $2$ and $4$ attack the argument $3$. On the other hand, in the
column vector $M(F)_{*,2}$ of the matrix $M(F)$, $a_{1,2}=1$ means that
$(1,2)\in R$, $i.e.$, the argument $1$ attacks the argument $2$. In the column
vector $M(F)_{*,4}$ of the matrix $M(F)$, $a_{5,4}=1$ means that $(5,4)\in R$,
$i.e.$, the argument $5$ attacks the argument $4$. Consequently, we have that
the argument $3$ is defended by $S_{2}=\\{1,5\\}$ in $F$. It is precisely that
the argument $3$ is not included in $S_{2}$ which leads to the fact that
$S_{2}=\\{1,5\\}$ is not a complete extension.

From the above analysis, we find a simple fact: In an argumentation framework
$F=(A,R)$ with $A=\\{1,2,...,n\\}$, an admissible extension
$S=\\{i_{1},i_{2},...,i_{k}\\}$ is complete iff each argument of $A\setminus
S=\\{j_{1},j_{2},...,j_{h}\\}$ is not defended by $S$ in $F$. And, we can
summarize the process to decide an admissible extension $S$ to be complete by
the blocks of matrix $M(F)$ of $F$ as follows:

(1) First, we pick out the column vectors
$M(F)_{\ast,j_{1}},M(F)_{\ast,j_{2}},...,M(F)_{\ast,j_{h}}$ of the matrix
$M(F)$ corresponding to the arguments of $A\setminus
S=\\{j_{1},j_{2},...,j_{h}\\}$. For each argument $j_{t}\in A\setminus S(1\leq
t\leq h)$, we check the elements $a_{1,j_{t}},a_{2,j_{t}},...,a_{n,j_{t}}$ in
the column vector $M(F)_{\ast,j_{t}}$ of the matrix $M(F)$ to find all the
attackers of the argument $j_{t}$.

(2) For each argument $j_{t}(1\leq t\leq h)$, we consider two cases with
respect to its attackers.

(a) There is some $j_{p}\in A\setminus S(1\leq p\leq h)$ such that
$a_{j_{p},j_{t}}=1$ in the column vector $M(F)_{\ast,j_{t}}$ of the matrix
$M(F)$, $i.e.$, $(j_{p},j_{t})\in R$, then the argument $j_{p}$ attacks the
argument $j_{t}$ in $F$. In order that the argument $j_{t}$ is not defended by
$S$, any argument $i_{r}\in S(1\leq r\leq k)$ should not attack the argument
$j_{p}$. Thus, we have $(i_{r},j_{p})\notin R$, $i.e.$, $a_{i_{r},j_{p}}=0$
for all $1\leq r\leq k$.

(b) There is no $j_{p}\in A\setminus S(1\leq p\leq h)$ such that
$a_{j_{p},j_{t}}=1$ in the column vector $M(F)_{\ast,j_{t}}$ of the matrix
$M(F)$, then there must be some $i_{r}\in S(1\leq r\leq k)$ such that
$a_{i_{r},j_{t}}=1$ in the column vector $M(F)_{\ast,j_{t}}$. Otherwise, there
is no $i\in A$ such that $a_{i,j_{t}}=1$, $i.e.$, there is no $i\in A$ such
that $(i,j_{t})\in R$. It follows that there is no argument $i\in A$ which
attacks the argument $j_{t}$ in $F$. This implies that the argument $j_{t}$ is
defended by $S$ in $F$, and thus $S$ is not a complete extension.

In case $(a)$, the elements $"a_{j_{p},j_{t}}"(1\leq p\leq h,1\leq t\leq h)$
form a block of the matrix $M(F)$ at the intersection of row
$j_{1},j_{2},...,j_{h}$ and the same number of columns. The elements
$"a_{i_{r},j_{t}}"(1\leq r\leq k,1\leq t\leq h)$ form anther block of the
matrix $M(F)$ at the intersection of row $i_{1},i_{2},...,i_{k}$ and the
column $j_{1},j_{2},...,j_{h}$, which is exactly the $s$-block of $S$. In case
$(b)$, one can find that the elements considered form the same blocks as in
case $(a)$. This motivation makes us to give the following definition.

Definition 18 Let $F=(A,R)$ be an argumentation framework with
$A=\\{1,2,...,n\\}$, and $S=\\{i_{1},i_{2},...,i_{k}\\}\subset A$ is a
complete extension of $F$. The block

$M^{j_{1},j_{2},...,j_{h}}_{j_{1},j_{2},...,j_{h}}=\left(\begin{array}[]{cccccc}a_{j_{1},i_{1}}&a_{j_{1},i_{2}}&.&.&.&a_{j_{1},i_{k}}\\\
a_{j_{2},i_{1}}&a_{j_{2},i_{2}}&.&.&.&a_{j_{2},i_{k}}\\\ .&.&.&.&.&.\\\
a_{j_{h},i_{1}}&a_{j_{h},i_{2}}&.&.&.&a_{j_{h},i_{k}}\end{array}\right)$

of order $h$ in the matrix of $M(F)$ is called the $c$-block of $S$ and
denoted by $M^{c}$, where $\\{j_{1},j_{2},...,j_{h}\\}=A\setminus S$.

In other words, the elements appearing at the intersection of rows
$j_{1},j_{2},...,j_{h}$ and the same number of columns in the matrix $M(F)$
form the $c$-block $M^{j_{1},j_{2},...,j_{h}}_{j_{1},j_{2},...,j_{h}}$ of $S$.

Note that, the $c$-block
$M^{c}=M^{j_{1},j_{2},...,j_{h}}_{j_{1},j_{2},...,j_{h}}$ of $S$ is exactly
the complementary block of the $s$-block
$M^{s}=M^{i_{1},i_{2},...,i_{k}}_{i_{1},i_{2},...,i_{k}}$ of $S$, in the
matrix $M(F)$ of $F$.

Now, the fact that $S_{1}=\\{1,3,5\\}$ is a complete extension in the above
example can be verified by the following conditions:

(1) The column vector of $s$-block $M^{1,3,5}_{2,4}$ of $S_{1}$ corresponding
to the non-zero row vector

of $c$-block $M^{2,4}_{2,4}$ of $S_{1}$ is zero;

(2) The column vector of $s$-block $M^{1,3,5}_{2,4}$ of $S_{1}$ corresponding
to the zero column vector

of $c$-block $M^{2,4}_{2,4}$ of $S_{1}$ is non-zero.

For convenience, in this section we also assume that the sequences
$i_{1},i_{2},...,i_{k}$ and $j_{1},j_{2},...,j_{h}$ are all increasing.

Lemma 19 Let $F=(A,R)$ be an argumentation framework with $A=\\{1,2,...,n\\}$,
then $S=\\{i_{1},i_{2},...,i_{k}\\}\subset A$ is a complete extension of $F$
iff $S$ is an admissible extension and each argument $j_{t}\in S(1\leq t\leq
h)$ is not defended by $S$ in $F$.

Theorem 20 Given an argumentation framework $F=(A,R)$ with
$A=\\{1,2,...,n\\}$, then the admissible extension
$S=\\{i_{1},i_{2},...,i_{k}\\}\subset A$ is a complete extension in $F$ iff
the following conditions hold:

(1) the column vector of $s$-block
$M^{i_{1},i_{2},...,i_{k}}_{j_{1},j_{2},...,j_{h}}$ of $S$ corresponding to
the non-zero row vector

of the $c$-block $M^{j_{1},j_{2},...,j_{h}}_{j_{1},j_{2},...,j_{h}}$ of $S$ is
zero,

(2) the column vector of $s$-block
$M^{i_{1},i_{2},...,i_{k}}_{j_{1},j_{2},...,j_{h}}$ of $S$ corresponding to
the zero column vector

of the $c$-block $M^{j_{1},j_{2},...,j_{h}}_{j_{1},j_{2},...,j_{h}}$ of $S$ is
non-zero,

where $A\setminus S=\\{j_{1},j_{2},...,j_{h}\\}$.

Proof Let $S$ be an admissible extension and $A\setminus
S=\\{j_{1},j_{2},...,j_{h}\\}$, we need only to prove that every $j_{t}\in
S(1\leq t\leq h)$ is not defended by $S$ in $F$ iff the condition $(1)$ and
$(2)$ are hold.

Assume that every $j_{t}\in A\setminus S(1\leq t\leq h)$ is not defended by
$S$ in $F$. If the row vector $M^{{}^{c}}_{r,*}(1\leq r\leq h)$ of the
$c$-block $M^{j_{1},j_{2},...,j_{h}}_{j_{1},j_{2},...,j_{h}}$ of $S$ is non-
zero, then there is some $1\leq t\leq h$ such that $a_{j_{r},j_{t}}=1$,
$i.e.$, $(j_{r},j_{t})\in R$. It follows that the argument $a_{j_{r}}$ attacks
the argument $a_{j_{t}}$. By the assumption, there is no argument in $S$ which
attacks the argument $a_{j_{r}}$. Therefore, for each $i_{q}\in S(1\leq q\leq
k)$ we have $(i_{q},j_{r})\notin R$, $i.e.$, $a_{i_{q},j_{r}}=0$. This means
that the column vector $M^{{}^{s}}_{*,r}$ of the $s$-block
$M^{i_{1},i_{2},...,i_{k}}_{j_{1},j_{2},...,j_{h}}$ of $S$ is zero.

If the column vector $M^{{}^{c}}_{*,t}(1\leq t\leq h)$ of the $c$-block
$M^{j_{1},j_{2},...,j_{h}}_{j_{1},j_{2},...,j_{h}}$ of $S$ is zero, then for
each $1\leq p\leq h$ we have that $a_{j_{p},j_{t}}=0$, $i.e.$,
$(j_{p},j_{t})\notin R$. Therefore, there is no argument in $A\setminus S$
which attacks the argument $j_{t}$. If there is no argument in $S$ which
attacks the argument $j_{t}$, then there is no argument in $A$ which attacks
the argument $j_{t}$. It follows that the argument $j_{t}$ is defended by $S$
in $F$, a contradiction with the assumption. Thus, there is some argument
$i_{r}\in S(1\leq r\leq k)$ which attacks the argument $j_{t}$, $i.e.$,
$(i_{r},j_{t})\in R$. This implies that $a_{i_{r},j_{t}}=1$, and thus the
column vector $M^{{}^{s}}_{*,t}$ of the $s$-block
$M^{i_{1},i_{2},...,i_{k}}_{j_{1},j_{2},...,j_{h}}$ of $S$ is non-zero.

Conversely, suppose that the conditions $(1)$ and $(2)$ are hold. Let
$j_{t}\in A\setminus S(1\leq t\leq h)$, we consider the column vector
$M^{c}_{*,t}$ of the $c$-block
$M^{j_{1},j_{2},...,j_{h}}_{j_{1},j_{2},...,j_{h}}$ of $S$. If the column
vector $M^{c}_{*,t}$ is zero, then by condition $(2)$ we have that the column
vector $M^{s}_{*,t}$ of the $s$-block
$M^{i_{1},i_{2},...,i_{k}}_{j_{1},j_{2},...,j_{h}}$ of $S$ is non-zero. It
follows that there is some $i_{q}\in S(1\leq q\leq k)$ such that
$a_{i_{q},j_{t}}=1$, $i.e.$, $(i_{q},j_{t})\in R$. This means that the
argument $i_{q}$ attacks the argument $j_{t}$ in $F$. Considering that $S$ is
a conflict-free set, there is no argument $i_{r}\in S(1\leq r\leq k)$ which
attacks the argument $i_{q}$ in $F$.

If the column vector $M^{c}_{*,t}$ is non-zero, then the row vector
$M^{c}_{t,*}$ is also non-zero. By condition $(1)$, the column vector
$M^{s}_{*,t}$ of the $s$-block
$M^{i_{1},i_{2},...,i_{k}}_{j_{1},j_{2},...,j_{h}}=M^{s}$ of $S$ is zero. It
follows that $a_{i_{r},j_{t}}=0$, $i.e.$, $(i_{r},j_{t})\notin R$ for each
$1\leq r\leq k$. This implies that there is no argument $i_{r}\in S(1\leq
r\leq k)$ which attacks the argument $j_{t}$ in $F$.

To sum up, we conclude that the argument $j_{t}\in A\setminus S(1\leq t\leq
h)$ is not defended by $S$.

8\. Conclusions and perspectives

In this paper, we introduced the matrix $M(F)$ of an argumentation framework
$F=(A,R)$, and the $cf$-block $M^{cf}$, $s$-block $M^{s}$, $a$-block $M^{a}$
and $c$-block $M^{c}$ of a set $S\subset A$, presented several theorems to
decide various extensions (stable, admissible, complete) of the AF, by blocks
of the matrix $M(F)$ of $F$ and relations between these blocks.

Interestingly, the $s$-block $M^{s}$ ($a$-block $M^{a}$, $c$-block $M^{c}$) of
$S$ corresponds to the determination for $S$ to be a stable extension
(admissible extension, complete extension respectively). And, the $c$-block of
$S$ is exactly the complementary block of the $cf$-block of $S$, the $a$-block
of $S$ is exactly the complementary block of the $s$-block of $S$.
Furthermore, we can decide basic extensions of an argumentation framework by
the special feature of blocks and relations between these blocks. These facts
indicate that there is indeed a corresponding relation between the
argumentation framework and its matrix. So, we can investigate the structure
and properties of an argumentation framework by using the theory and method of
matrix.

For the other common extension semantics (preferred, grounded, ideal, semi-
stable and eager) of Dung’s argumentation framework not discussed in the above
sections, we can also provide the matrix method to describe them, by combining
the obtained results. For example, if we want to decide that a complete
extension $S\subset A$ is grounded in $F=(A,R)$, we could first find out all
the complete extensions by theorem 20. Then, we compare the $cf$-blocks of
these complete extensions. If the $cf$-block of $S$ is the minimal one in the
collection of $cf$-blocks of all complete extensions, then we claim that $S$
is a grounded extension.

The prospectives are that, we can find out the internal pattern of AFs and the
relations between different objects which we concerned in AFs, by studying
blocks of the matrix of AFs. Our future goal is to develop the matrix method
in the related areas, such as argument acceptability, dialogue games,
algorithmic and complexity and so on [7, 11, 8, 13, 16, 12].

References

## References

  * [1] P. Baroni, M. Giacomin, On principle-based evaluation of extension-based argumentation semantics, Artificial Intelligence 171 (2007), 675-700.
  * [2] T. J. M. Bench-Capon, Paul E. Dunne, Argumentation in artificial intelligence, Artificial intelligence 171(2007)619-641
  * [3] M.Caminada, Semi-stable semantics, in: Frontiers in Artificial Intelligence and its Applications, vol. 144, IOS Press, 2006, pp. 121-130.
  * [4] C.Cayrol, M.C.Lagasquie-Schiex, Graduality in argumentation, J. AI Res. 23 (2005)245-297.
  * [5] S.Coste-Marquis, C.Devred, C.Devred, Symmetric argumentation frameworks, in: Lecture Notes in Artificial Intelligence, vol. 3571, Springer-Verlag, 2005, pp. 317-328.
  * [6] S.Coste-Marquis, C.Devred, P. Marquis, Prudent semantics for argumentation frameworks, in: Proc. 17th ICTAI, 2005, pp. 568-572.
  * [7] Y.Dimopoulos, A. Torres, Graph theoretical structures in logic programs and default theories, Teoret. Comput. Sci. 170(1996)209-244.
  * [8] P.M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and $n$-person games, Artificial Intelligence 77 (1995), 321-357.
  * [9] P.M.Dung, P. Mancarella, F. Toni, A dialectic procedure for sceptical assumption-based argumentation, in: Frontiers in Artificial Intelligence and its Applications, vol. 144, IOS Press, 2006, pp. 145-156.
  * [10] P.E.Dunne, Computational properties of argument systems satisfying graph-theoretic constrains, Artificial Intelligence 171 (2007), 701-729.
  * [11] P.E.Dunne, T. J. M. Bench-Capon, Coherence in finite argument systems, Artificial intelligence 141(2002)187-203.
  * [12] P.E.Dunne, T. J. M. Bench-Capon, Two party immediate response disputes: properties and efficiency, Artificial Intelligence 149 (2003), 221-250.
  * [13] H.Jakobovits, D.Vermeir, Dialectic semantics for argumentation frameworks, in: Proc. 7th ICAIL, 1999, pp. 53-62.
  * [14] E. Oikarinen, S.Woltron, Characterizing strong equivalence for argumentation frameworks, Artificial intelligence(2011), doi:10.1016/j.artint.2011.06.003.
  * [15] G. Vreeswijk, Abstract argumentation system, Artificial intelligence 90(1997)225-279.
  * [16] G. Vreeswijk, H.Pakken, Credulous and sceptical argument games for preferred semantics, in: Proceedings of JELIA’2000, the 7th European Workshop on Logic for Artificial Intelligence, Berlin, 2000, pp. 224-238.