Imperative programming allows users to implement their deep neural networks (DNNs) easily and has become an essential part of recent deep learning (DL) frameworks.
Recently, several systems have been proposed to combine the usability of imperative programming with the optimized performance of symbolic graph execution.
Such systems convert imperative Python DL programs to optimized symbolic graphs and execute them.
However, they cannot fully support the usability of imperative programming.
For example, if an imperative DL program contains a Python feature with no corresponding symbolic representation (e.g., third-party library calls or unsupported dynamic control flows) they fail to execute the program.
To overcome this limitation, we propose , an imperative-symbolic co-execution system that can handle any imperative DL programs while achieving the optimized performance of symbolic graph execution.
To achieve this, builds a symbolic graph by decoupling DL operations from Python features.
Then, conducts the imperative execution to support all Python features, while delegating the decoupled operations to the symbolic execution.
We evaluated 's performance improvement and coverage with ten imperative DL programs for several DNN architectures.
The results show that can speed up the execution of all ten imperative DL programs, whereas AutoGraph, one of the state-of-the-art systems, fails to execute five of them.

§ INTRODUCTION

The rapid evolution of deep neural networks (DNNs) has been fueled by the support of deep learning (DL) frameworks [6, 32].
Such frameworks provide users with a programming layer to build and execute DNNs, commonly adopting Python as their host language.
Typically, they execute DL programs with one of the two execution models: imperative or symbolic execution.
In the former, the Python interpreter executes a DL program as a normal program, invoking DL operations on-the-fly.
The invoked DL operations are executed on a separate DL accelerator asynchronously, and the Python interpreter continues running the program.
The dynamic control flows of the DL operations are naturally expressed by the interpretation of the program, and users can utilize any functionalities of Python (e.g., dynamic typing and third-party libraries [9, 16]) while executing DL operations.
On the other hand, in the latter model, the Python interpreter embeds DL operations into a symbolic graph that represents the entire dataflow of a DNN.
Thus, users should define their DL programs only with existing symbolic operations that DL frameworks support.
In other words, the dynamic control flows of a DNN should be explicitly represented by control flow operations (e.g., tf.cond and tf.while of TensorFlow).
However, the symbolic execution can take advantages of various optimization techniques because the symbolic graph contains a whole computation lineage of a DNN architecture.

Although symbolic execution achieves higher performance compared to imperative execution, imperative execution has been preferred because of its usability.
Several systems [2, 3, 4, 15, 19, 29, 39] have been proposed to match the speed of symbolic execution while enjoying the benefit of imperative execution.
These systems attempt to generate a symbolic graph that represents an entire imperative program and execute the graph instead of imperatively running the program.
Methods for generating the symbolic graph can be broadly classified into two approaches: single path tracing and static compilation.
The former approach generates a symbolic graph by imperatively executing a single iteration of a program and recording the executed DL operations.
Systems that adopt the latter approach translate the abstract syntax tree (AST) of a program into a symbolic graph.

Unfortunately, both approaches can correctly handle only a subset of imperative DL programs.
For example, dynamic control flows in an imperative program are not captured by the single path tracing approach.
On the other hand, the static compilation approach cannot correctly generate a symbolic graph if a target program contains an AST node that does not have a corresponding symbolic operation such as try-excepts, generators, Python object mutations, and third-party library calls.
As a result, it is up to the users to clearly understand the limited usability of these systems.

In this paper, we propose , an imperative-symbolic co-execution system that addresses the limitations.
While the previous approaches replace the imperative execution with the symbolic execution, maintains the imperative execution to support all Python features where DL operations are delegated to the symbolic execution.
Also, generates a symbolic graph by utilizing multiple traces of an imperative program.
To be specific, imperatively runs an imperative DL program for several iterations and collects traces, each of which is a linear chain of DL operations sorted by the execution order.
The collected traces are merged into a , a directed acyclic graph (DAG) that encapsulates the captured DL operations along with their diverse execution orders.
stops collecting traces when the trace of the latest iteration is already embedded in the .
To generate an executable symbolic graph from the , adds additional information to the .
First of all, annotates the to enable communication between the imperative execution and the symbolic execution.
In addition, further analyzes the to insert control flow operations explicitly, so that a symbolic graph can be executed with the DL operations in a certain trace.
After generating a symbolic graph from the , starts the co-execution of a skeleton imperative program, in which DL operations are not performed, and the symbolic graph that represents the DL operations.
Here, continually checks whether the current trace is being expressed by the .
If detects a new trace, discards the symbolic graph and collects more traces by running the original program imperatively.
then re-generates the symbolic graph and restarts the co-execution.
Consequently, is able to run any imperative DL programs correctly and efficiently even if it contains the Python features that the previous approaches cannot handle.

We have implemented on TensorFlow v2.4.1 and compared with TensorFlow's imperative execution [7] and AutoGraph [29].
Our evaluation shows that can train ten imperative DL programs including convolutional neural networks, transformer-based networks, and generative adversarial networks up to x faster than the original imperative execution.
However, AutoGraph fails to support five programs for three reasons: third-party library call, Python object mutation, and tensor materialization during conversion, which we describe in  <ref>.

§ BACKGROUND & RELATED WORKS

§.§ Imperative and Symbolic Execution

The imperative execution (a.k.a. define-by-run) [30, 32, 43] treats a DL program entirely as a typical Python program.
Whenever the Python interpreter encounters a statement that declares a DL operation (e.g., z = torch.matmul(x, y)), the interpreter asynchronously invokes a corresponding computation kernel of a DL accelerator (typically GPU or TPU).
The imperative execution highly improves the programmability of DL programs because users can fully utilize the convenient language features and rich ecosystem of Python, including built-in functions, dynamic control flows, dynamic typing, and third-party libraries.
However, since the imperative execution cannot obtain a whole view of DNN computation, it misses optimization opportunities that the symbolic execution explained below can carry out.

The symbolic execution (a.k.a. define-and-run) [6, 14, 42] executes a pre-built symbolic graph.
In the symbolic execution, users should express their DNN architectures as symbolic graphs using the three kinds of symbolic operations: DL operations, control flow operations, and auxiliary operations.
The DL operations are conventional compute-intensive operations (e.g., matrix multiplication or convolutional layer), and the control flow operations determine which DL operations to be executed based on a tensor value within the graph.
Finally, to mitigate the limited usability of the symbolic execution, it supports auxiliary operations (e.g., tf.print and tf.py_function of TensorFlow).
After the symbolic graph is constructed, graph optimizations could be applied such as
operation fusion [11, 20, 26, 31, 35, 41, 46, 47, 48], parallelized execution [23, 31, 35], device placement [27, 28, 48], layout optimization [20, 25], and memory optimization [8, 17, 18].
Then, an optimized graph executor such as TVM [11], TensorRT [31], TFRT [40], and XLA [41] undertakes the actual execution of the symbolic graph.

§.§ Imperative Program with Symbolic Execution

third-party library call &
tensor materialization

dynamic control flow

Python object mutation

Simple examples that the static compilation approach cannot deal with. Note that AutoGraph could silently produce an incorrect result in the Python object mutation case.

There are two approaches to gain the usability of imperative execution and the performance of symbolic execution simultaneously.
They attempt to convert an imperative DL program to a symbolic graph and exploit the symbolic execution with the converted graph.
The single path tracing approach (e.g., torch.trace [3], JAX [15], and tf.function [39]) executes an imperative DL program once and records all DL operations that were executed.
A single linear chain of the executed DL operations, which is called a trace, becomes a symbolic graph of the imperative program.
The symbolic graph is executed instead of the imperative program for subsequent iterations.
Although the single path tracing approach looks very simple and intuitive, it is hard to capture dynamic control flows of the imperative program with this approach.
To reflect them correctly, users need to explicitly declare the control flow operations for all dynamic control flows in their imperative programs, which undermines the programmability of the imperative program.
Moreover, Python features that do not have corresponding symbolic operations (e.g., mutation of Python objects, use of third-party libraries) are neither captured by the trace.
It can yield an incorrect result since, in the following iterations, a graph executor executes a symbolic graph, which does not contain the Python features.

The static compilation approach (e.g., TorchScript [4] and JANUS [19]) is proposed to resolve the problem of the single path tracing approach.
In contrast to the single path tracing approach, the static compilation approach does not extract a trace to generate a symbolic graph.
Instead, it traverses an abstract syntax tree (AST) of the imperative program and directly converts each AST node to a corresponding symbolic operation.
Even if it guarantees the correctness of the program, it fails to convert a program to a symbolic graph if the program contains a Python feature with no corresponding symbolic operation.
We classify the representative failure cases into four categories: third-party library call, tensor materialization during conversion, dynamic control flow, and Python object mutation.
Figure <ref> presents simple examples of the cases.
The static compilation approach cannot convert the third-party library calls of Figure <ref> and fails when it attempts to materialize the tensor data (loss.numpy()) during the conversion.
Figure <ref> shows the generator in Python that the static compilation approach cannot convert.
For Figure <ref>, only JANUS handles it by implementing custom auxiliary operations (i.e., GetAttr and SetAttr operations) that access the Python heap during the symbolic execution.

To increase the practicality of the previous approaches, AutoGraph [29] combines the static compilation approach with the single path tracing approach.
AutoGraph converts AST nodes that correspond to dynamic control flow such as if-else, for, and while to new AST nodes representing proper control flow operations such as tf.cond and tf.while.
Then, AutoGraph generates a symbolic graph by applying the single path tracing approach to the converted AST.
Unfortunately, it cannot fully support various kinds of dynamic control flows such as generator and try-except of Python.
Hence, AutoGraph also entails the same correctness problem of the single path tracing approach when the imperative DL program employs the features described in Figure <ref>.

When the static compilation approach detects unsupported features, it just raises an error and aborts the program execution.
To avoid this, users have to write their programs using only the supported features or put in additional efforts such as annotating types and refactoring functions to use tensor objects for their inputs and outputs.
In this regard, AutoGraph [29] and TorchScript [4] provide the official language references [1, 5] that users should be aware of before writing a target imperative program.
However, those references usually require expert knowledge to understand, imposing a steep learning curve for new users.
For example, the language document of AutoGraph [1] spans roughly twelve pages and divides features that AutoGraph does not support into four categories and ten subcategories.
TorchScript provides an official language specification [5] by enumerating supported features over eleven pages.

LazyTensor [36] is a concurrent work related to ours.
It uses the lazy evaluation approach, in which the Python interpreter and symbolic graph executor run alternately.
The Python interpreter executes an imperative DL program as it is and extracts a linear trace of operations.
LazyTensor then checks whether the extracted trace is already cached or not.
If cached, LazyTensor directly executes the cached graph.
If not, it compiles and executes the new graph, then stores the graph for further executions.
With the lazy evaluation, LazyTensor could support all Python features while executing the symbolic graph as does.
However, it has an unavoidable performance overhead due to the alternate execution.
In other words, the graph executor progresses only when the Python interpreter finishes checking the existence of the cached graph.
Similarly, the Python interpreter progresses after finishing the graph execution.
Moreover, if an imperative program has a dynamic control flow that is not determined by a tensor value, LazyTensor fails to capture the control flow transparently.
In this case, LazyTensor would work inefficiently because the traces could be different for each iteration.

§ OUR APPROACH: IMPERATIVE-SYMBOLIC CO-EXECUTION

To the best of our knowledge, no existing DL framework can completely convert an arbitrary imperative DL program into a symbolic graph.
We believe that a one-to-one mapping from all Python features to corresponding symbolic operations should exist to support all imperative programs with the approaches.
In other words, building such a mapping is the same as covering all Python syntax with symbolic operations.
Moreover, the mapping should be updated as a new feature of Python (e.g., pattern matching of Python 3.10 [33]) is introduced.
Eventually, it is equal to building a new Python execution engine for a symbolic graph representing a Python program itself, which requires a tremendous amount of time and effort.

Therefore, we take a different approach that does not replace the entire imperative execution with the symbolic execution as the previous approaches do.
Instead, we let the Python interpreter run an imperative program to support all Python features naturally while separating only DL operations from the imperative execution.
As the Python interpreter executes the program except performing DL operations, the decoupled DL operations are executed by a graph executor simultaneously.
To enable the co-execution, we generate a symbolic graph representing DL operations that would have been launched by the Python interpreter.
While the previous approaches have to build a complete symbolic graph that encapsulates all semantics of the DL program for correctness, we construct a symbolic graph solely based on collected traces of DL operations.
Although we do not embed all semantics of the DL program in the symbolic graph, it can handle any DL program by the co-execution of the skeleton program complementing the symbolic execution.
Within the skeleton program, DL operations are not performed but all other Python features are preserved as the original imperative program.
Executing the symbolic graph in parallel with the skeleton program, we fully achieve the usability of the imperative execution along with the optimized performance of the symbolic execution.

§ SYSTEM DESIGN

is a system that realizes our imperative-symbolic co-execution approach. In this section, we describe how implements the co-execution of a skeleton imperative program and a symbolic graph in detail.
There are two requirements to seamlessly maintain the imperative execution along with executing the symbolic graph.
First of all, should allow exchanging tensor values between the imperative execution and the symbolic execution when there exists data dependency between each other (e.g., Figure <ref>).
Furthermore, the imperative execution should inform the symbolic execution of the correct choice of path to follow because the execution flow of the program is determined by the Python interpreter.
To achieve these, implements new symbolic operations for such communication and inserts them into the symbolic graph.
In the following, we first describe the entire process of the imperative-symbolic co-execution ( <ref>).
Next, we explain how merges collected traces into the and generates a symbolic graph from it in detail ( <ref>).

§ EVALUATION

In this section, we evaluate in the following two aspects:

* Can exploit symbolic execution from imperative DL programs that AutoGraph, the static-compilation-and-tracing approach, cannot? ( <ref>)

* How much does speed up imperative DL programs? ( <ref>)

§.§ Implementation and Experiment Setup

Frameworks. We use TensorFlow [6] v2.4.1 as our baseline DL framework. We have built on TensorFlow v2.4.1,
and our approach is applicable to other DL frameworks if they support both imperative and symbolic execution (e.g., MXNet [10] and PyTorch [32]).
More details about the implementation of are described in Appendix C.
All evaluated imperative DL programs are implemented with the imperative API of TensorFlow, which has become the standard interface since TensorFlow v2.0.
We compare with TensorFlow imperative execution and with AutoGraph [29], a state-of-the-art system that combines the static compilation approach with the single path tracing approach.
We compile a single training step function of each imperative DL program (i.e., @tf.function(autograph=True)).

Environments. We conduct all the experiments on a single machine that is equipped with 8-core AMD Ryzen 7 2700X @ 3.7GHz and an NVIDIA TITAN Xp GPU.
We use Ubuntu 18.04, CUDA 11.0, cuDNN 8.0, and Python 3.8.8.

Imperative DL Programs.
For the experiments, we use ten imperative DL programs collected from open-source GitHub repositories:
DropBlock [12], BERT-Q&A [13], MusicTransformer [21], SDPoint [22], BERT-CLS [24], GPT2 [34], DCGAN [37], ResNet50 [38], FasterRCNN [44], and YOLOv3 [45].

Program     Reason of the failure

DropBlock [12]     Python object mutation

MusicTransformer [21]     Python object mutation

SDPoint [22]     Python object mutation

BERT-CLS [24]     third-party library call

FasterRCNN [44]     tensor materialization during conversion

The programs that AutoGraph fails to execute and the reason for the failures.
Note that can execute all of them.

§.§ Imperative Program Coverage

handles all the benchmark programs successfully with the imperative-symbolic co-execution.
However, since AutoGraph does not support the entire set of Python features, it fails to execute five out of ten programs.
Table <ref> shows why AutoGraph fails to handle the programs and the detailed code snippets are described in Appendix D.

According to the AutoGraph language document [1], more failures could exist if an imperative DL program contains unsupported Python features such as the use of Python generator, try-except, and None type values.
To resolve all the limitations in AutoGraph, new functions to handle each failure should be implemented and it requires a huge engineering effort.
simply avoids the conversion-related problems by the imperative-symbolic co-execution.

§.§ Training Throughput

The training speed-up results of , AutoGraph, and when applying XLA [41] to both systems relative to TensorFlow imperative execution.
The dotted line presents the training throughput of the imperative execution.
Note that and AutoGraph share the same upper bound of performance improvement from the symbolic execution of TensorFlow.

Figure <ref> presents the training speed-up of compared to TensorFlow imperative execution.
For all programs, we measure the average training throughputs from 100 to 200 steps, and each experiment is conducted ten times.
achieves higher performance than the imperative execution for every program.
To estimate whether fully achieves the optimized performance of symbolic execution, we also compare the performance of with AutoGraph, which shares the same graph executor of TensorFlow with .
AutoGraph closely follows the performance of the symbolic execution because it totally replaces the imperative execution with the symbolic execution.
For the five programs that AutoGraph can execute, the performance improvements of are on par with AutoGraph, which shows that highly achieves the symbolic execution's optimized performance.
Experiment settings such as batch size and the dataset are included in Appendix E.

Since generates a symbolic graph and utilizes the symbolic execution, we evaluate the performance of by applying XLA [41] as shown in Figure <ref>.
Compared to the imperative execution, improves the performance of seven programs by up to x when applying XLA.
XLA is not applicable to GPT2 and FasterRCNN due to the dynamic shape of the input data.
For each training iteration, the shapes of input data to the models can change.
However, XLA cannot efficiently handle dynamic shapes because it assumes static shapes.
For YOLOv3, we profile the execution and find that the current XLA fails to efficiently cluster operations for YOLOv3.
To be more specific, YOLOv3 includes some DL operations such as ResizeNearestNeighbor and Where, which are not supported by XLA.
Thus, XLA cannot efficiently fuse DL operations.
In addition, we observe that Terra's performance decreases more than that of AutoGraph for YOLOv3 because the schedules of some Output Fetching operations are reordered because of XLA kernels, causing a longer stall in the PythonRunner.
However, this problem can be addressed by extending XLA to support our custom operations.

We profile the execution of both PythonRunner and GraphRunner to analyze the performance of .
We focus on the performance analysis in the co-execution phase because 's execution is mostly in this phase.
The number of transitions between the two phases and the overhead analysis for the tracing phase are included in Appendix F.
Figure <ref> shows the performance breakdown of the two Runners in a single training step.
`PythonRunner Exec' denotes the Python interpreter's active running time, such as executing user code or validating the symbolic graph.
Both `PythonRunner Stall' and `GraphRunner Stall' indicate the stall time in which the PythonRunner waits for the GraphRunner to fetch the materialized tensor or vice versa.
Finally, we measure GPU’s active time to run the CUDA kernels along with the overhead of TensorFlow’s graph executor as `GraphRunner Exec'.
For all programs except for FasterRCNN, the GraphRunner is not stalled, implying that the GraphRunner fully exploits the optimized performance of the symbolic execution.
In FasterRCNN, the stall of the GraphRunner occurs when the PythonRunner receives a materialized tensor from the GraphRunner and feeds it back to the GraphRunner.
For YOLOv3, the PythonRunner's execution time is longer than that of the GraphRunner,
which yields the slightly larger performance gap between and AutoGraph in Figure <ref>.

Performance breakdown within a single training step for both the PythonRunner and the GraphRunner.

2*Program     2*

ResNet50     x1.25     x1.13

BERT Q&A     x1.23     x0.94

DCGAN     x1.56     x1.34

Comparison of the training speed-up between and with lazy evaluation.
The results are relative speed-up to TensorFlow imperative execution as Figure <ref>.

Moreover, Figure <ref> shows that the GraphRunner takes a longer time than the PythonRunner in most cases.
The result implies the reason why the performance improvements of are comparable to the performance improvements of AutoGraph.
The execution of the PythonRunner is efficiently concealed by the execution of the GraphRunner with the co-execution.
To demonstrate the effect of the co-execution, we serialize the execution of the PythonRunner and the GraphRunner then evaluate the performance for the simple programs among our benchmarks.

Within the serialized execution, the GraphRunner does not start the execution along with the PythonRunner.
Instead, it starts the execution when the PythonRunner requires tensor data through the Output Fetching operation.
Eventually, the serialized execution is the same as the lazy evaluation that LazyTensor [36] does.
Our results in Table <ref> show that the lazy evaluation cannot fully achieve high performance of the symbolic execution.
Even worse, it could become slower than the imperative execution when the execution time of the GraphRunner is not much longer than the execution time of the PythonRunner.

§ CONCLUSION

We propose , a novel approach to execute imperative Python DL programs.
performs imperative-symbolic co-execution, which addresses the problem of converting an imperative program to a symbolic graph completely.
generates a symbolic graph only from the DL operations of an imperative DL program.
It then carries out the imperative execution, simultaneously executing the symbolic graph.
Therefore, achieves optimized performance while maintaining all Python features of the imperative program.
Our evaluation shows that can speed up all imperative DL programs, even for the programs that AutoGraph cannot handle.

§ BROADER IMPACT

Our work aims to accelerate the execution of imperative DL programs while maintaining programmability.
Our work is not associated with a specific application because our approach is applicable for any imperative DL programs.
Thus, we believe our work does not have a significant impact on any audience from either an ethical or societal perspective, at the application level.

§ ACKNOWLEDGEMENTS

We thank the reviewers for their valuable comments.
We also thank Haeyoon Cho, Jae-Won Chung, Jeongyoon Eo, Wonwook Song, Gyewon Lee, Soojeong Kim, Hokwen Joung, and Taegyun Kim for their constructive feedback.
This work was partly supported by
Google Research Award,
Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) [NO.2021-0-01343, Artificial Intelligence Graduate School Program (Seoul National University)],
Development of QA systems for Video Story Understanding to pass the Video Turing Test,
Institute for Information & communications Technology Promotion (IITP) grant funded by the Korea government (MSIT) (No.2015-0-00221, Development of a Unified High-Performance Stack for Diverse Big Data Analytics), and Samsung Advanced Institute of Technology.

[1]
Autograph Limitation Document.

[2]

[3]

[4]

[5]
TorchScript Language Reference.

[6]
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey
Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Ghemawat, Michael Isard,
Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek G. Murray,
Benoit Steiner, Paul Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan
Yu, and Xiaoqiang Zheng.
TensorFlow: A System for Large-scale Machine Learning.
In Proceedings of USENIX Symposium on Operating Systems Design
and Implementation (OSDI), 2016.

[7]
Akshay Agrawal, Akshay Naresh Modi, Alexandre Passos, Allen Lavoie, Ashish
Agarwal, Asim Shankar, Igor Ganichev, Josh Levenberg, Mingsheng Hong, Rajat
Monga, and Shanqing Cai.
TensorFlow Eager: A Multi-Stage, Python-Embedded DSL for Machine
In Proceedings of Conference on Systems and Machine Learning
(SysML), 2019.

[8]
Byung Hoon Ahn, Jinwon Lee, Jamie Menjay Lin, Hsin-Pai Cheng, Jilei Hou, and
Hadi Esmaeilzadeh.
Ordering Chaos: Memory-Aware Scheduling of Irregularly Wired Neural
Networks for Edge Devices.
In Proceedings of Conference on Machine Learning and Systems
(MLSys), 2020.

[9]
Lars Buitinck, Gilles Louppe, Mathieu Blondel, Fabian Pedregosa, Andreas
Mueller, Olivier Grisel, Vlad Niculae, Peter Prettenhofer, Alexandre
Gramfort, Jaques Grobler, Robert Layton, Jake VanderPlas, Arnaud Joly, Brian
Holt, and Gaël Varoquaux.
API design for machine learning software: experiences from the
scikit-learn project.
In ECML PKDD Workshop: Languages for Data Mining and Machine
Learning, pages 108–122, 2013.

[10]
Tianqi Chen, Mu Li, Yutian Li, Min Lin, Naiyan Wang, Minjie Wang, Tianjun Xiao,
Bing Xu, Chiyuan Zhang, and Zheng Zhang.
MXNet: A Flexible and Efficient Machine Learning Library for
Heterogeneous Distributed Systems.
In Workshop on Machine Learning Systems in NIPS, 2015.

[11]
Tianqi Chen, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Yan, Haichen
Shen, Meghan Cowan, Leyuan Wang, Yuwei Hu, Luis Ceze, Carlos Guestrin, and
Arvind Krishnamurthy.
TVM: An Automated End-to-End Optimizing Compiler for Deep Learning.
In Proceedings of USENIX Symposium on Operating Systems Design
and Implementation (OSDI), 2018.

[12]

[13]
Hugging Face.

[14]

[15]
Roy Frostig, Matthew James Johnson, and Chris Leary.
Compiling Machine Learning Programs via High-Level Tracing.
In Proceedings of Conference on Systems and Machine Learning
(SysML), 2018.

[16]
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers,
Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg,
Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van
Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark
Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard, Tyler Reddy,
Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant.
Array programming with numpy.
Nature, 585(7825):357–362, 2020.

[17]
Chienchin Huang, Gu Jin, and Jinyang Li.
SwapAdvisor: Pushing Deep Learning Beyond the GPU Memory Limit via
Smart Swapping.
In Proceedings of ACM International Conference on Architectural
Support for Programming Languages and Operating Systems (ASPLOS), 2019.

[18]
Paras Jain, Ajay Jain, Aniruddha Nrusimha, Amir Gholami, Pieter Abbeel, Joseph
Gonzalez, Kurt Keutzer, and Ion Stoica.
Checkmate: Breaking the Memory Wall with Optimal Tensor
In Proceedings of Conference on Machine Learning and Systems
(MLSys), 2020.

[19]
Eunji Jeong, Sungwoo Cho, Gyeong-In Yu, Joo Seong Jeong, Dong-Jin Shin, and
Byung-Gon Chun.
JANUS: Fast and Flexible Deep Learning via Symbolic Graph
Execution of Imperative Programs.
In Proceedings of USENIX Symposium on Networked Systems Design
and Implementation (NSDI), 2019.

[20]
Zhihao Jia, Oded Padon, James Thomas, Todd Warszawski, Matei Zaharia, and Alex
TASO: Optimizing Deep Learning Computation with Automatic Generation
of Graph Substitutions.
In Proceedings of ACM Symposium on Operating Systems Principles
(SOSP), 2019.

[21]

[22]
Jason Kuen.
Stochastic Downsampling for Cost-Adjustable Inference and Improved
Regularization in Convolutional Networks (SDPoint).

[23]
Woosuk Kwon, Gyeong-In Yu, Eunji Jeong, and Byung-Gon Chun.
Nimble: Lightweight and Parallel GPU Task Scheduling for Deep
In Proceedings of Advances in Neural Information Processing
Systems (NeurIPS), 2020.

[24]

[25]
Yizhi Liu, Yao Wang, Ruofei Yu, Mu Li, Vin Sharma, and Yida Wang.
Optimizing CNN Model Inference on CPUs.
In Proceedings of USENIX Annual Technical Conference (ATC),

[26]
Lingxiao Ma, Zhiqiang Xie, Zhi Yang, Jilong Xue, Youshan Miao, Wei Cui,
Wenxiang Hu, Fan Yang, Lintao Zhang, and Lidong Zhou.
Rammer: Enabling Holistic Deep Learning Compiler Optimizations with
In Proceedings of USENIX Symposium on Operating Systems Design
and Implementation (OSDI), 2020.

[27]
Azalia Mirhoseini, Anna Goldie, Hieu Pham, Benoit Steiner, Quoc V. Le, and Jeff
A Hierarchical Model for Device Placement.
In Proceedings of International Conference on Learning
Representations (ICLR), 2018.

[28]
Azalia Mirhoseini, Hieu Pham, Quoc V. Le, Benoit Steiner, Rasmus Larsen,
Yuefeng Zhou, Naveen Kumar, Mohammad Norouzi, Samy Bengio, and Jeff Dean.
Device Placement Optimization with Reinforcement Learning.
In Proceedings of International Conference on Machine Learning
(ICML), 2017.

[29]
Dan Moldovan, James M. Decker, Fei Wang, Andrew A. Johnson, Brian K. Lee,
Zachary Nado, D. Sculley, Tiark Rompf, and Alexander B. Wiltschko.
AutoGraph: Imperative-style Coding with Graph-based Performance.
In Proceedings of Conference on Systems and Machine Learning
(SysML), 2019.

[30]
Graham Neubig, Chris Dyer, Yoav Goldberg, Austin Matthews, Waleed Ammar,
Antonios Anastasopoulos, Miguel Ballesteros, David Chiang, Daniel Clothiaux,
Trevor Cohn, Kevin Duh, Manaal Faruqui, Cynthia Gan, Dan Garrette, Yangfeng
Ji, Lingpeng Kong, Adhiguna Kuncoro, Gaurav Kumar, Chaitanya Malaviya, Paul
Michel, Yusuke Oda, Matthew Richardson, Naomi Saphra, Swabha Swayamdipta, and
Pengcheng Yin.
DyNet: The Dynamic Neural Network Toolkit.
arXiv preprint arXiv: 1701.03980, 2017.

[31]
NVIDIA TensorRT: Programmable Inference Accelerator.

[32]
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory
Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban
Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan
Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith
PyTorch: An Imperative Style, High-Performance Deep Learning
In Proceedings of Advances in Neural Information Processing
Systems (NeurIPS), 2019.

[33]
Python Software Foundation.
Pep 634: Structural pattern matching.

[34]
Abhay Singh.

[35]
Muthian Sivathanu, Tapan Chugh, Sanjay S. Singapuram, and Lidong Zhou.
Astra: Exploiting Predictability to Optimize Deep Learning.
In Proceedings of ACM International Conference on Architectural
Support for Programming Languages and Operating Systems (ASPLOS), 2019.

[36]
Alex Suhan, Davide Libenzi, Ailing Zhang, Parker Schuh, Brennan Saeta,
Jie Young Sohn, and Denys Shabalin.
Lazytensor: combining eager execution with domain-specific compilers.
arxiv2102.13267, 2021.

[37]
Deep Convolutional Generative Adversarial Network Tutorial.

[38]
TensorFlow Model Garden.

[39]

[40]
TFRT: A New TensorFlow Runtime.

[41]
XLA: Optimizing Compiler for TensorFlow.

[42]
Theano Development Team.
Theano: A Python framework for fast computation of mathematical
arXiv preprint arXiv: 1605.02688, 2016.

[43]
Seiya Tokui, Ryosuke Okuta, Takuya Akiba, Yusuke Niitani, Toru Ogawa, Shunta
Saito, Shuji Suzuki, Kota Uenishi, Brian Vogel, and Hiroyuki Yamazaki
Chainer: A Deep Learning Framework for Accelerating the Research
In Proceedings of ACM SIGKDD Conference on Knowledge Discovery
and Data Mining, 2019.

[44]

[45]
Zihao Zhang.

[46]
Jie Zhao, Bojie Li, Wang Nie, Zhen Geng, Renwei Zhang, Xiong Gao, Bin Cheng,
Chen Wu, Yun Cheng, Zheng Li, Peng Di, Kun Zhang, and Xuefeng Jin.
AKG: Automatic Kernel Generation for Neural Processing Units using
Polyhedral Transformations.
In Proceedings of ACM SIGPLAN Conference on Programming Language
Design and Implementation (PLDI), 2021.

[47]
Zhen Zheng, Pengzhan Zhao, Guoping Long, Feiwen Zhu, Wenyi Zhao Kai Zhu,
Lansong Diao, Jun Yang, and Wei Lin.
FusionStitching: Boosting Memory Intensive Computations for Deep
Learning Workloads.
arXiv preprint arXiv: 2009.10924, 2020.

[48]
Yanqi Zhou, Sudip Roy, Amirali Abdolrashidi, Daniel Wong, Peter Ma, Qiumin Xu,
Hanxiao Liu, Mangpo Phitchaya Phothilimtha, Shen Wang, Anna Goldie, Azalia
Mirhoseini, and James Laudon.
Transferable Graph Optimizers for ML Compilers.
In Proceedings of Advances in Neural Information Processing
Systems (NeurIPS), 2020.


# On Perverse sheaves of a Coxeter hyperplane arrangement of type
$\mathcal{A}_{n}$

Umesh V Dubey  Harish-Chandra Research Institute, A CI of HBNI, Prayagraj, UP,
INDIA<EMAIL_ADDRESS>and  Subham Sarkar  Kerala School of
Mathematics, INDIA<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

Kapranov and schechtman gave quiver description of perverse sheaves on real
hyperplane arrangements. We used this description to relate the perverse
sheaves on Coxeter hyperplane arrangements of type $\mathcal{A}_{n}$ for
different values of $n$. As a consequence we prove that the simple perverse
sheaves whose stalk on open cells are zero are induced from the perverse
sheaves on lower dimension arrangements.

###### 1991 Mathematics Subject Classification:

Primary 20F55; Secondary 32S22, 32S60

##  1\. Introduction

For an algebraic variety $X$ defined over the field of complex numbers
${\mathds{C}}$, let $\mathscr{P}er(X,\mathcal{S})$ be the category of perverse
sheaves with respect to a Whitney stratification $\mathcal{S}$. It is an
abelian category obtained as a heart of a suitable $t$-structure defined by a
perversity condition in the triangulated category
$D^{b}_{const}(X,\mathcal{S})$, the bounded derived category of complexes of
sheaves of ${\mathds{C}}$ vector spaces whose cohomology sheaves are
constructible with respect to the stratification $\mathcal{S}$ ([BBD82]). In
certain special cases the category $\mathscr{P}er(X,\mathcal{S})$ has a few
combinatorial descriptions due to [MV86] and [KS16].

Let $X$ be a linear subspace of dimension $n$ and $H_{i}$ be a hyperplane
defined over the field of real numbers in $X\cong{\mathds{C}}^{n}$ for all
$1\leq i\leq N$. Then $X$ has a natural Whiney stratification $\mathcal{S}$.
The abelian category of perverse sheaves $\mathscr{P}er(X,\mathcal{S})$ is
equivalent to the category of representation of double quivers with a certain
set of relations known as _monotonicity, invertibility,_ and _transitivity_
[KS16]. In [Bap21], the category $\mathscr{P}er(X,\mathcal{S})$ is equivalent
to the abelian category of modules over a noncommutative ring $R$ when $X$ is
Coxeter hyperplane arrangements of type $\mathcal{A}_{n}$. Here we prove the
following.

Let $V^{n}$ be the linear subspace in ${\mathds{R}}^{n}$ defined by
$\\{\sum_{i=1}^{n+1}x_{i}=0\\}\subset\mathds{R}^{n+1}$. A Coxeter arrangement
of hyperplanes in $V^{n}$ defined by the collection of hyperplanes
$\mathcal{A}_{n}$ consisting of hyperplanes

$L^{n}_{i,j}:=\\{(x_{1},x_{2},\dots,x_{n+1})\in V^{n}:x_{i}-x_{j}=0,\hskip
17.0pt1\leq i<j\leq n+1\\}.$

The hyperplane arrangements of type $\mathcal{A}_{n}$ determine a natural
Whitney stratification $\mathcal{S}^{n}$ on $V^{n}_{{\mathds{C}}}$ ($\S$ 2.2).
For $1\leq i<j\leq n+1$, the linear map

$\rho_{L^{n+1}_{i,j}}:V^{n}\rightarrow V^{n+1}$

defined by

$(x_{1}\dots,x_{i-1},x_{i},x_{i+1},\dots,x_{n},-(\sum_{k}x_{k}))\mapsto((x_{1}\dots,x_{j-1},x_{i},x_{j+1},\dots,x_{n+1},-(\sum_{k\neq
i}x_{k}+2x_{i}))$

is not a stratified algebraic morphism between two arrangements
$(V^{n}_{{\mathds{C}}},\mathcal{S}^{n})$ and
$(V^{n+1}_{{\mathds{C}}},\mathcal{S}^{n+1})$. However, we have

######  Theorem 1.1.

For any $1\leq i<j\leq n+1$, there is a fully-faithful exact functor

$\Lambda_{L_{i,j}^{n+1}}:\mathscr{P}er(V_{{\mathds{C}}}^{n},\mathcal{S}^{n})\rightarrow\mathscr{P}er(V_{{\mathds{C}}}^{n+1},\mathcal{S}^{n+1}),$
(1)

which makes the following diagram commutative

${\mathscr{P}er(V_{{\mathds{C}}}^{n},\mathcal{S}^{n})}$${\mathcal{J}_{n}}$${\mathscr{P}er(V_{{\mathds{C}}}^{n+1},\mathcal{S}^{n+1})}$${\mathcal{J}_{n+1}.}$$\scriptstyle{\mathcal{Q}^{n}}$$\scriptstyle{\Lambda_{L_{i,j}^{n+1}}}$$\scriptstyle{\Phi_{L_{i,j}^{n}}}$$\scriptstyle{\mathcal{Q}^{n+1}}$

In [Row], the irreducible objects in
$\mathscr{P}er(V_{{\mathds{C}}}^{n},\mathcal{S}^{n})$ has been completely
classified for $n=1$ and partially for $n=2$. In the same spirit, we obtain
the following corollary.

######  Corollary 1.2.

Let $\mathcal{F}$ be a constructible sheaves on the hyperplane arrangement
$\mathcal{A}_{n+1}$. Then we have the following.

  1. (1)

If $\mathcal{F}\in\mathscr{P}er(V_{{\mathds{C}}}^{n+1},\mathcal{S}^{n+1})$ is
irreducible then $\operatorname{dim}_{{\mathds{C}}}(E_{C}(\mathcal{F}))=0$ or
$1$, where $C$ be any open cell in $\mathcal{C}_{\mathcal{A}_{n+1}}$.

  2. (2)

Suppose
$\mathcal{F}\in\mathscr{P}er(V_{{\mathds{C}}}^{n+1},\mathcal{S}^{n+1})$ is
irreducible and $\operatorname{dim}_{{\mathds{C}}}(E_{C}(\mathcal{F}))=0$
where $C$ be any open cell in $\mathcal{C}_{\mathcal{A}_{n+1}}$. Then there
exists $\mathcal{G}\in\mathscr{P}er(V_{{\mathds{C}}}^{n},\mathcal{S}^{n})$ and
$L_{i,j}^{n+1}\in\mathcal{H}_{\mathcal{A}_{n+1}}$ such that

$\Lambda_{L_{i,j}^{n+1}}(\mathcal{G})=\mathcal{F}.$

##  2\. Perverse sheaves of real hyperplane arrangements

In this section we will recall the quiver description of Kapranov and
Schechtmann [KS16] which we will use in later sections.

Let $X$ be an algebraic variety over ${\mathds{C}}$ and $\mathcal{S}$ be a
Whiney stratification on $X({\mathds{C}})$. We denote by
$\mathscr{P}er(X,\mathcal{S})$ the category of perverse sheaves with respect
to $\mathcal{S}$ satisfying the following perversity conditions. Let
$\mathcal{F}\in D^{b}_{const}(X,\mathcal{S})$.

  * •

$\emph{CONDITION P}^{-}:$ For each $i$, the $i^{th}$ degree cohomology sheaf
$\underline{H}^{i}(\mathcal{F})$ is supported on a closed subspace of
codimension $\geq i$.

  * •

$\emph{CONDITION P}^{+}:$ The sheaf
$\underline{H}^{i}(l^{!}\mathcal{F})=\underline{\mathds{H}}^{i}_{Z}(\mathcal{F})$
is zero, for all $i<p$ where $l:Z\hookrightarrow X$ is a locally closed
analytic submanifold of $X$ of codimension $p$.

###  2.1. Sheaves on cellular space and linear algebra data

A topological space $X$ with a filtration
$\upchi=\\{X_{d}:\operatorname{dim}X_{d}=d\geq 1\\}$ by closed subspace is
said to be a cellular space if $X_{d}\setminus X_{d-1}$ is the disjoint union
of cells of dimension $d$. Let $\mathcal{C}_{X,\upchi}$ be the set of all
cells corresponding to the filtration $\upchi$ on $X$ which has the following
partial order $\leq$.

$\text{For any }C\text{ and
}C^{\prime}\in\mathcal{C}_{X,\upchi},C^{\prime}\leq C\text{ if and only if
}C^{\prime}\subset\bar{C}.$ (2)

######  Definition 2.1.

A sheaf $\mathcal{F}$ is said to be a cellular sheaf if for any
$C\in\mathcal{C}_{X,\upchi}$, $j_{C}^{*}\mathcal{F}$ is a constant sheaf with
stalk a finite-dimensional complex vector space where $j_{C}:C\hookrightarrow
X$.

Let us denote $Sh_{X,\upchi}$ to be the category of cellular sheaves on $X$
with respect to $\upchi$. For any $\mathcal{F}\in Sh_{X,\upchi}$, consider
$\mathcal{F}_{C}:=H^{0}(C,j_{C}^{*}\mathcal{F})$, the stalk at
$C\in\mathcal{C}_{X}$. For any $C$, $C^{\prime}\in\mathcal{C}_{X}$ satisfying
$C^{\prime}\leq C$, define

$\gamma_{C^{\prime}C}:\mathcal{F}_{C^{\prime}}\rightarrow\mathcal{F}_{C}$ (3)

as follows. Take $y\in C^{\prime}\subset V$ to be a sufficiently small
contractible open neighborhood of $y$ and consider $x\in V\cap C^{\prime}$.
Let $U$ be a small contractible neighborhood of $x\in C$ in $X$. Since
$U\subset V$, define $\gamma_{C^{\prime}C}$ to be the restriction map

$H^{0}(V,\mathcal{F})=\mathcal{F}_{C^{\prime}}\rightarrow
H^{0}(U,\mathcal{F})=\mathcal{F}_{C}.$

Let
$\operatorname{Rep}(\mathcal{C}_{X}):=\operatorname{Fun}(\mathcal{C}_{X},\operatorname{Vec}_{{\mathds{C}}})$
be the category of functors from $\mathcal{C}_{X}$ to
$\operatorname{Vec}_{{\mathds{C}}}$, the category of finite dimensional vector
spaces over ${\mathds{C}}$.

######  Proposition 2.2.

[KS16, Proposition 1.8]

  1. (1)

The following covariant functor is an equivalence of categories

$\displaystyle Sh_{X,\upchi}\longrightarrow$
$\displaystyle\operatorname{Rep}(\mathcal{C}_{X})$
$\displaystyle\mathcal{F}\mapsto$
$\displaystyle(\mathcal{F}_{C},\gamma_{C^{\prime}C}).$

  2. (2)

Let $D^{b}_{\upchi}(Sh_{X})$ be the bounded derived category of sheaves whose
cohomology sheaves lies in $Sh_{X,\upchi}$. The above equivalence of
categories induces the following equivalence of the respective derived
categories

$D^{b}(\operatorname{Rep}(\mathcal{C}_{X}))\longrightarrow
D^{b}_{\upchi}(Sh_{X}).$ (4)

In other words any object in $\mathcal{F}^{\bullet}\in D^{b}_{\upchi}(Sh_{X})$
determines a complex of vector spaces
$(\mathcal{F}_{C}^{\bullet})_{C\in\mathcal{C}_{X}}$ with generalisation map of
complex
$\gamma_{C^{\prime}C}^{\bullet}:\mathcal{F}_{C}^{\bullet}\longrightarrow\mathcal{F}_{C^{\prime}}^{\bullet}$,
where $C^{\prime}\leq C\in\mathcal{C}_{X}$. A category of perverse sheaves can
be defined as an abelian subcategory of $D^{b}_{\upchi}(Sh_{X})$. Therefore if
$\mathcal{F}^{\bullet}$ is perverse, it determines a set of _linear algebra
data_ (a complex of vector spaces with generalization maps).

###  2.2. Real hyperplane arrangements

Let $V$ be a vector space defined over ${\mathds{R}}$ of dimension $n\geq 1$
and $\mathcal{H}$ be an arrangement of linear hyperplanes in $V$. Here we only
consider _essential_ hyperplane arrangements. In otherwords,
$\underset{H\in\mathcal{H}}{\cap}H=\\{0\\}$. Each hyperplane $H\in\mathcal{H}$
defined by a linear equation $f_{H}:V\rightarrow{\mathds{R}}$. We choose once
and for all a set of equations $\\{f_{H}:H\in\mathcal{H}\\}$.

Each $x\in V$ determines a sign vector
$(v_{H}(x))_{H\in\mathcal{H}}\in\mathcal{H}^{\\{+,-,0\\}}$, where
$v_{H}(x):=\operatorname{sgn}(f_{H}(x))$ and
$\operatorname{sgn}:{\mathds{R}}\rightarrow\\{+,-,0\\}$ be the sign function.
Any two distinct points $x$ and $y\in V$ are said to be lie in the same face
if and only if $v_{H}(x)=v_{H}(y)$, for all $H\in\mathcal{H}$. Hence we
identify the set of faces with the corresponding set of sign vectors
associated with $\mathcal{H}$. The faces are locally closed convex subsets of
$V$ and it induces cellular decomposition of $V$. In particular, faces would
be called cells depending on the context. Hence the hyperplane arrangement
induces a natural filtration $\upchi$ on $V$.

Let $\mathcal{C}_{\mathcal{H},\upchi}$ be set of cells corresponding to the
arrangement of hyperplanes $\mathcal{H}$ in $V$. The following two partial
ordering in $\mathcal{C}_{\mathcal{H},\upchi}$ are equivalent.

  1. (1)

For any $C$ and $C^{\prime}\in\mathcal{C}_{\mathcal{H},\upchi}$,
$C^{\prime}\leq C$ if and only if $C^{\prime}\subset\bar{C}$.

  2. (2)

The following partial order on $\\{+,-,0\\}$

$0\leq+,\hskip 5.0pt0\leq-$

gives a partial order on $\mathcal{C}_{\mathcal{H},\upchi}$ as follows. For
any $C$ and $C^{\prime}\in\mathcal{C}_{\mathcal{H},\upchi}$,

$C^{\prime}\leq C\hskip 19.0pt\text{ if and only if }\hskip
10.0ptv_{H}(C^{\prime})\leq v_{H}(C)$

for any hyperplane $H\in\mathcal{H}$.

On the other hand there exist another natural filtration $\bar{\upchi}$ on
$V_{{\mathds{C}}}$ associated to the $\mathcal{H}$ where

$X_{d}:=\bigcup_{\operatorname{dim}(C)\leq d}{\mathds{R}}^{n}\oplus iC.$

It induces a cell decomposition $\mathcal{C}_{\mathcal{H},\bar{\upchi}}$ on
$V_{{\mathds{C}}}$ with the above partial order. There is a bijection between
$\mathcal{C}_{\mathcal{H},\upchi}$ and
$\mathcal{C}_{\mathcal{H},\bar{\upchi}}$ which preserve the partial orders.
Hence we identify $\mathcal{C}_{\mathcal{H},\upchi}$ with
$\mathcal{C}_{\mathcal{H},\bar{\upchi}}$.

###  2.3. Real hyperplane arrangement and linear algebra data

An arrangement of hyperplanes $\mathcal{H}$ defines a natural Whitney
stratification on $V_{{\mathds{C}}}\cong{{\mathds{C}}}^{n}$ as follows. The
set of flats is defined by
$\mathcal{L}_{\mathcal{H}}:=\\{\underset{H\in\mathcal{I}}{\cap}H:\mathcal{I}\subset\mathcal{H}\\}.$
For any flats $L\in\mathcal{L}$, define associated Whitney stratum
$L^{\textdegree}_{{\mathds{C}}}:=L_{{\mathds{C}}}\setminus(\cup_{H\nsupseteq
L}H_{{\mathds{C}}})$. The set
$\mathcal{S}_{0}:=\\{L^{\textdegree}_{{\mathds{C}}}:L\in\mathcal{L}_{\mathcal{H}}\\}$
gives a Whitney stratification on ${{\mathds{C}}}^{n}$. Let us consider
$\mathscr{P}er({{\mathds{C}}}^{n},\mathcal{S}_{0})$ to be the category of
perverse sheaves on ${{\mathds{C}}}^{n}$ with respect to $\mathcal{S}_{0}$ and
it is an abelian category of the triangulated category
$D^{b}({{\mathds{C}}}^{n},\mathcal{S}_{0})$.

For $\mathcal{F}\in D^{b}_{\mathcal{S}_{0}}({\mathds{C}}^{n})$, consider
$\mathcal{R}_{\mathcal{F}}^{\bullet}:=R\Gamma_{{\mathds{R}}^{n}}(\mathcal{F}^{\bullet})[n]\in
D^{b}_{\mathcal{C}_{\mathcal{H}}}({\mathds{R}}^{n})$ which is a complex of
cellular sheaves. Hence by (4), $\mathcal{R}_{\mathcal{F}}^{\bullet}$ can be
identified with linear algebra data of complexes of vector spaces as follows.
Let

$E_{C}^{\bullet}(\mathcal{F}):=R\Gamma(C,\mathcal{R}_{\mathcal{F}}^{\bullet})$

and

$\gamma_{C^{\prime}C}:E^{\bullet}_{C^{\prime}}(\mathcal{F})\rightarrow
E^{\bullet}_{C}(\mathcal{F}).$

For $\mathcal{F}\in\mathscr{P}er(V_{{\mathds{C}}}^{n},\mathcal{S}^{n})\subset
D^{b}_{\mathcal{S}_{n}}({\mathds{C}}^{n})$, $E_{C}^{\bullet}(\mathcal{F})$ is
quasi-isomorphic to a complex of vector spaces with only non-zero entry
$E_{C}(\mathcal{F})$ at degree zero. In particular, for each
$C\in\mathcal{C}_{\mathcal{H},\upchi}$, functor $\mathcal{F}\mapsto
E_{C}(\mathcal{F})$ is an exact functor. Hence one obtains
$\gamma_{C^{\prime}C}:E_{C^{\prime}}(\mathcal{F})\rightarrow
E_{C}(\mathcal{F})$ as a linear map of vector spaces.

Let $j_{C}:{\mathds{R}}^{n}+iC\hookrightarrow{\mathds{C}}^{n}$, where
$C\in\mathcal{C}_{\mathcal{H},\upchi}$ of dimension $d$, define

$\mathcal{E}^{\bullet}_{C}(\mathcal{F}):=j_{C\star}j_{C}^{!}(\mathcal{F})[d]=R\Gamma_{{\mathds{R}}^{n}+iC}(\mathcal{F})[d].$

Recall the associated complex of homological Postnikov system, [Sec 4.A,
[KS16]], of $\mathcal{F}$ which realises $\mathcal{F}$ as a total object

$\mathcal{E}^{\bullet}(\mathcal{F}):=\bigoplus_{\operatorname{dim}(C)=0}\mathcal{E}^{\bullet}_{C}(\mathcal{F})\rightarrow\bigoplus_{\operatorname{dim}(C)=1}\mathcal{E}^{\bullet}_{C}(\mathcal{F})\rightarrow\dots\rightarrow\mathcal{E}^{\bullet}_{0}(\mathcal{F}).$
(5)

Now applying the functor $R\Gamma({\mathds{C}}^{n},\text{ })$ to the equation
(5), we get the associated total complex of the corresponding Postnikov system
in the derived categories of vector spaces, known as _Cousin complex_ of
$\mathcal{F}$.

$\bigoplus_{\operatorname{dim}(C)=0}E^{\bullet}_{C}(\mathcal{F})\otimes
or(C)\overset{\tilde{\delta}}{\rightarrow}\bigoplus_{\operatorname{dim}(C)=1}E^{\bullet}_{C}(\mathcal{F})\otimes
or(C)\overset{\tilde{\delta}}{\rightarrow}\dots\rightarrow
E^{\bullet}_{0}(\mathcal{F})\otimes or(C).$ (6)

For $C^{\prime}\leq C$ such that
$\operatorname{dim}(C^{\prime})=\operatorname{dim}(C)-1$, one obtains

$\delta_{CC^{\prime}}:E_{C}\rightarrow E_{C^{\prime}}.$ (7)

This map extends to give $\delta_{CC^{\prime}}$ for any $C^{\prime}\leq C$. We
can also use the Verdier duality to redefine
$\delta_{CC^{\prime}}:=\gamma^{\mathcal{F}^{\star}}_{C^{\prime}C}$ where
$\mathcal{F}^{\star}:=\underline{R\operatorname{Hom}}(\mathcal{F},or_{X})$
denotes the Verdier dual of perverse sheaf $\mathcal{F}$, see [Prop 4.6,
[KS16]]. This defines a perfect duality in the category of perfect complexes.
from now onwards we use the notation $\mathcal{C}_{\mathcal{H}}$ instead of
$\mathcal{C}_{\mathcal{H},\upchi}$

######  Definition 2.3.

A double representation of $\mathcal{C}_{\mathcal{H}}$ is given by a datum
$(E_{C},\gamma_{C^{\prime}C},\delta_{CC^{\prime}})$, where $E_{C}$ is a
${\mathds{C}}$-vector space for every $C\in\mathcal{C}_{\mathcal{H}}$ and for
$C^{\prime}\leq C$ linear maps

$\gamma_{C^{\prime}C}:E_{C^{\prime}}\rightarrow E_{C}\text{ and
}\delta_{CC^{\prime}}:E_{C}\rightarrow E_{C^{\prime}}$

Such that

  * •

$\gamma_{CC}=\delta_{CC}=Id_{C}$

  * •

$\gamma_{CC^{\prime\prime}}=\gamma_{C^{\prime}C^{\prime\prime}}\gamma_{CC^{\prime}}$
and
$\delta_{CC^{\prime\prime}}=\delta_{C^{\prime}C^{\prime\prime}}\delta_{CC^{\prime}}.$
where $C^{\prime\prime}\leq C^{\prime}\leq C$.

######  Definition 2.4.

  * •

Let $C_{1}$ and $C_{2}$ be two distinct faces of dimensnion $d$ such that the
linear span of $C_{1}$ and $C_{2}$ are equal. Then $C_{1}$ and $C_{2}$ are
said to be opposed each other by a face $D$ of dimension $d-1$ if $D\leq
C_{1}$, $D\leq C_{2}$; and for any hyperplane $H\in\mathcal{H}$,
$\sigma(C)_{H}=0$ and $\sigma(A)_{H}=-\sigma(B)_{H}\neq 0.$

  * •

Any triple of faces $(A,B,C)$ is said to be colinear if any line joining a
point in $A$ and $C$ lies in $B$.

Suppose $\operatorname{Rep}_{2}(\mathcal{C}_{\mathcal{H}})$ be the category of
double representation of $\mathcal{C}_{\mathcal{H}}$. It is an abelian
category. For any cells $A$, $B$ and $C\in\mathcal{C}_{\mathcal{H}}$
satisfying $C\leq A$ and $C\leq B$ we define
$\phi_{AB}:=\gamma_{CB}\delta_{AC}$. Consider the full subcategory
$\mathcal{J}_{\mathcal{H}}$ consisting of double representations which satisfy
the relations – _monotonicity_ , _transitivity_ and _invertibility_ which are
defined as follows.

  * •

_Monotonicity_ : For any $C\leq C^{\prime}$, one has
$\gamma_{C^{\prime}C}\delta_{CC^{\prime}}=Id_{C}$.

  * •

_Transitivity_ : For any colinear cells $C_{1}$, $D_{1}$ and
$C_{2}\in\mathcal{C}_{\mathcal{H}}$, one has

$\phi_{C_{1}C_{2}}=\phi_{D_{1}C_{2}}\phi_{C_{1}D_{1}}$

.

  * •

_Invertibility_ : If $C_{1}$ and $C_{2}$ oppose each other by $D_{1}$, then
$\phi_{C_{1}C_{2}}$ is an isomorphism.

We can also define a perfect duality on the category
$Rep_{2}(\mathcal{C}_{\mathcal{H}})$. Define the dual of a double
representation as
$(V_{C},\gamma_{C^{\prime}C},\delta_{CC^{\prime}})^{\star}:=(V_{C}^{*},\delta_{CC^{\prime}}^{*},\gamma_{C^{\prime}C}^{*})$,
where $V_{C}^{*}$ is the vector space dual. Now we can check that the duality
functor preserves all three relations and hence it will restrict to the
subcategory $\mathcal{J}_{\mathcal{H}}$ to give the perfect duality.

######  Theorem 2.5.

[KS16, Theorem 8.1] Let $\mathcal{H}$ be any real hyperplane arrangement on
$\mathds{R}^{n}$ and $\mathcal{S}$ be a natural Whitney stratification
associated to $\mathcal{H}$. There is an equivalence of categories

$\mathcal{Q}:\mathscr{P}er({\mathds{C}}^{n},\mathcal{S}_{0})\longrightarrow\mathcal{J}_{\mathcal{H}},$
$\mathcal{F}\mapsto\left(E_{C}(\mathcal{F},\gamma_{C^{\prime}C}(\mathcal{F}),\delta_{CC^{\prime}}(\mathcal{F}))\right)_{C^{\prime}\leq
C\in\mathcal{C}_{\mathcal{H}}}.$

where $\mathcal{J}_{\mathcal{H}}$ is the full subcategory of
$\operatorname{Rep}_{2}(\mathcal{C}_{\mathcal{H}})$. Moreover, the functor
$\mathcal{Q}$ commutes with the duality i.e.
$\mathcal{Q}(\mathcal{F}^{\star})=\mathcal{Q}(\mathcal{F})^{\star}$.

##  3\. Coxeter type arrangements

Coxeter hyperplane arrangement of type $\mathcal{A}_{n}$ is defined in [PS00,
$\S 3$]. It is also known as a braid arrangement of type $\mathcal{A}_{n}$.
Let $V^{n}$ be a linear subspace of dimension $n$ over the field of real
numbers, defined by

$V^{n}:=\\{\sum_{i=1}^{n+1}x_{i}=0\\}\subset\mathds{R}^{n+1}.$

Consider $V_{{\mathds{C}}}^{n}$ to be its complexification. Here we consider
the Coxeter arrangement of hyperplanes of type $\mathcal{A}_{n}$ on $V^{n}$.

######  Definition 3.1.

A Coxeter arrangement of type $\mathcal{A}_{n}$ is defined as a collection of
hyperplanes $\mathcal{H}_{\mathcal{A}_{n}}$consisting the following set of
equation in $V^{n}$

$L^{n}_{i,j}:=\\{(x_{1},x_{2},\dots,x_{n+1})\in V^{n}:x_{i}-x_{j}=0,\hskip
17.0pt1\leq i<j\leq n+1\\}.$

###  3.1. Embedding of triangulations

A triangulation of a topological space $X$ is a cellular (CW-complex)
structure on $X$. An hyperplane arrangement on a linear space $X$ gives a
triangulation of $X$. Here we compare two distinct triangulations of a linear
space $X$ of dimension $n$, obtained by two different hyperplane arrangements
$\mathcal{A}_{n}$ and the induced hyperplane arrangement $\mathcal{A}_{n+1}$
on a subspace $L^{n+1}_{i,j}$. Since the equation of hyperplane in the above
two cases are symmetric in $i$ and $j$, it is enough to consider the special
case $i=1$ and $j=n+1$. Consider

$\rho_{L^{n+1}_{1,n+1}}:V^{n}\rightarrow V^{n+1}$

defined by

$(x_{1}\dots,x_{n},-(\sum_{i}x_{i}))\mapsto((x_{1}\dots,x_{n-1},x_{1},-(\sum_{i\neq
1}x_{i}+2x_{1})).$

We claim that the above map induces an order preserving embedding

$\iota_{L_{1,n+1}^{n+1}}:\mathcal{C}_{\mathcal{A}_{n}}\longrightarrow\mathcal{C}_{\mathcal{A}_{n+1}}.$

The hyperplane arrangement of type $\mathcal{A}_{n}$ can be identified with an
arrangement $\mathcal{H}_{{\mathds{R}}^{n}}$ on ${\mathds{R}}^{n}$ as follows.
For each $n\geq 1$, consider the natural isomorphism between real vector
spaces of dimension $n$, $\phi_{n}:{{\mathds{R}}}^{n}\longrightarrow V^{n}$,
defined by $(y_{1},y_{2},\dots,y_{n})\mapsto(x_{1},x_{2},\dots,x_{n+1})$,
where $x_{i}=y_{i}$ for all $1\leq i\leq n$ and
$x_{n+1}=-\sum_{j=1}^{j=n}y_{j}$.

For all $H\in\mathcal{H}_{n}$, $\phi^{*}(H)$, the pullback hyperplanes are the
following

$\displaystyle A_{i,j}^{n}:=$ $\displaystyle Y_{i}-Y_{j}\text{ for }1\leq
i<j\leq n,$ $\displaystyle B_{i}^{n}:=$ $\displaystyle 2Y_{i}+\sum_{j\neq
i}Y_{j}\text{ for }1\leq i\leq n.$

Consider the arrangement of hyperplane
$\mathcal{H}_{{\mathds{R}}^{n}}:=\\{A_{i,j}^{n},B_{i}^{n}:1\leq i<j\leq n\\}$
of ${\mathds{R}}^{n}$. The above isomorphism induces a bijection between
$\mathcal{H}_{{\mathds{R}}^{n}}$ and $\mathcal{A}_{n}$. Let us denote
$W_{n}:={\mathds{R}}^{n+1}\cap A_{1,n+1}^{n+1}$ to be the real vector space of
dimension $n$ with the following hyperplane arrangement $\mathcal{H}_{W_{n}}$:

$\displaystyle\tilde{A}_{i,j}^{n+1}$ $\displaystyle:=A_{i,j}^{n+1}\cap
A_{1,n+1}^{n+1}=$ $\displaystyle Y_{i}-Y_{j}$ $\displaystyle\text{ for
}1<i<j\leq n,$ $\displaystyle\tilde{A}_{1,j}^{n+1}$
$\displaystyle:=A_{1,j}^{n+1}\cap A_{1,n+1}^{n+1}=$ $\displaystyle
Y_{1}-Y_{j}$ $\displaystyle\text{ for }1<j\leq n,$
$\displaystyle\tilde{A}_{i,n+1}^{n+1}$ $\displaystyle=A_{i,n+1}^{n+1}\cap
A_{1,n+1}^{n+1}=$ $\displaystyle Y_{i}-Y_{n+1}=Y_{i}-Y_{1}$
$\displaystyle\text{ for }1<i\leq n,$ $\displaystyle\tilde{B}_{i}^{n+1}$
$\displaystyle:=B_{i}^{n+1}\cap A_{1,n+1}^{n+1}=$ $\displaystyle
2Y_{1}+2Y_{i}+\sum_{j\neq i,1}Y_{j}$ $\displaystyle\text{ for }1<i\leq n,$
$\displaystyle\tilde{B}_{1}^{n+1}$ $\displaystyle:=B_{1}^{n+1}\cap
A_{1,n+1}^{n+1}=$ $\displaystyle 3Y_{1}+\sum_{j\neq i,1}Y_{j}.$

Moreover, we claim that the natural isomorphism

$\Psi_{n}:{\mathds{R}}^{n}\longrightarrow W_{n},$
$(y_{1},\dots,y_{n})\mapsto(y_{1},\dots,y_{n},y_{1})$

induces an order-preserving bijection
$\iota_{n}:\mathcal{C}_{{\mathds{R}}^{n}}\longrightarrow\mathcal{C}_{W_{n}}$.
In particular, it is enough to prove that two different arrangements
$\mathcal{H}_{{\mathds{R}}^{n}}$ and the pullback of hyperplanes in
$\mathcal{H}_{W_{n}}$ by $\Psi_{n}$ in ${\mathds{R}}^{n}$, induces an order-
preserving bijection between poset of cells in ${\mathds{R}}^{n}$ with respect
to $\mathcal{H}_{{\mathds{R}}^{n}}$ and $\mathcal{H}_{W_{n}}$. For any
$P\in{\mathds{R}}^{n}$, define

$E_{i}(P):=2z_{i}+\sum_{j\neq 1,i}z_{j}.$

######  Theorem 3.2.

There is an order preserving bijection
$\iota_{n}:\mathcal{C}_{{\mathds{R}}^{n}}\longrightarrow\mathcal{C}_{W_{n}}$
which induces an order preserving embedding

$\iota_{L_{1,n+1}^{n+1}}:\mathcal{C}_{\mathcal{A}_{n}}\longrightarrow\mathcal{C}_{\mathcal{A}_{n+1}}.$

###### Proof.

Let us recall that we have an isomorphism
$\phi_{n}:{\mathds{R}}^{n}\longrightarrow V^{n}$ and consider the hyperplane
arrangements $\mathcal{H}_{{\mathds{R}}^{n}}$, obtained by pullback of
hyperplanes $L_{i,j}^{n}$, where $1\leq i<j\leq n$. The hyperplanes
$\mathcal{A}_{n+1}$ induce an arrangement of hyperplanes on $L_{1,n+1}^{n+1}$.
We also have an isomorphism $\psi_{n}:{\mathds{R}}^{n}\longrightarrow
L_{1,n+1}^{n+1}$ which pullback the induced hyperplane arrangements and we
obtain an arrangement $\mathcal{H}_{W_{n}}$. Hence we obtain two distinct
arrangements $\mathcal{H}_{{\mathds{R}}^{n}}$ and pullback of hyperplanes in
$\mathcal{H}_{W_{n}}$ in ${\mathds{R}}^{n}$. Let $\Lambda$ and $\Gamma$ be the
sign vectors associated to $\mathcal{H}_{{\mathds{R}}^{n}}$ and
$\mathcal{H}_{W_{n}}$ respectively, defined as follows.

$\displaystyle\Lambda:{\mathds{R}}^{n}\longrightarrow$
$\displaystyle\mathcal{H}_{{\mathds{R}}^{n}}^{\\{+,-,0\\}}$ $\displaystyle
x\mapsto$
$\displaystyle\left((v_{A_{i,j}^{n}}(x),v_{B^{n}_{i}}(x)\right)_{1\leq i<j\leq
n}$

and

$\displaystyle\Gamma:{\mathds{R}}^{n}\longrightarrow$
$\displaystyle\mathcal{H}_{W_{n}}^{\\{+,-,0\\}}$ $\displaystyle x\mapsto$
$\displaystyle\left((v_{\tilde{A}_{i,j}^{n+1}}(x),v_{\tilde{B}^{n+1}_{i}}(x),v_{\tilde{A}_{i,n+1}^{n+1}}(x)\right)_{1\leq
i<j\leq n}.$

The sign vectors associated to any hyperplane arrangement determine a cell
decomposition on ${\mathds{R}}^{n}$ uniquely. Hence, in order to show
$\iota_{n}$ is an order-preserving bijection one needs to show

  * •

For any $C\in\mathcal{C}_{\mathcal{H}_{{\mathds{R}}^{n}}}$ and
$v(C)\in\mathcal{H}_{n}^{\\{+,-,0\\}}$ there exist a
$C_{W}\in\mathcal{C}_{W_{n}}$ such that $v(C_{W})=(v(C),e_{1},\dots,e_{n+1})$,
where $e_{i}=v_{\tilde{A}_{i,n+1}^{n+1}}(C_{W})\in\\{+,-,0\\}$.

  * •

The above correspondence is an order preserving bijection.

For any cell $C\in\mathcal{C}_{{\mathds{R}}^{n}}$, a point in $C$ determines
an unique sign vector in $\mathcal{H}_{{\mathds{R}}^{n}}^{\\{+,-,0\\}}$ and
vice-versa. Hence it is enough to prove that for any $P\in
C\subset{\mathds{R}}^{n}$, there exists a point $Q\in{\mathds{R}}^{n}$ such
that

$v(Q)=(v(P),e_{1},\dots,e_{n}),\hskip 3.0pt\text{where
}e_{i}=v_{\tilde{A}_{i,n+1}^{n+1}}(Q)\in\\{+,-,0\\}.$

By Lemma (3.3) and Lemma (3.4), there is an bijection between the collection
of open cells corresponding to $\mathcal{H}_{{\mathds{R}}^{n}}$ and
$\mathcal{H}_{W_{n}}$ in ${\mathds{R}}^{n}$.

∎

######  Lemma 3.3.

There is an order-preserving bijection between the poset of cells of
codimension zero associated to the hyperplane arrangements of
$\mathcal{H}_{{\mathds{R}}^{n}}$ and $\mathcal{H}_{W_{n}}$ in
${\mathds{R}}^{n}$.

###### Proof.

Let $C\in\mathcal{C}_{\mathcal{H}_{{\mathds{R}}^{n}}}$ be an open cell. An
open cell in ${\mathds{R}}^{n}$, corresponding to
$\mathcal{H}_{{\mathds{R}}^{n}}$ determines a sign vector with only non-zero
entries. In particular, for any $P\in C$, all of the entries of
$v_{A_{i,j}^{n}}(P)$ are either $+ve$ or $-ve$ sign, for all $1\leq i\neq
j\leq n$. Hence for any point $P=(z_{1},\dots,z_{n})\in C$, one has the
following presentation

$z_{\lambda_{1}}<z_{\lambda_{2}}<\dots<z_{\lambda_{i}}<z_{\lambda_{i+1}}<\dots<z_{\lambda_{n}},$
(8)

The sign vector $v(C)$ must determines one of the following relations

  1. (1)

$v_{B_{i}^{n}}(P)>0$, for all $i$

  2. (2)

$v_{B_{i}^{n}}(P)<0$, for all $i$ or

  3. (3)

$v_{B_{i_{j}}^{n}}(P)>0$ and $v_{B_{m_{j}}^{n}}(P)<0$, where $1\leq i_{j}$,
$m_{j}\leq n$.

Then it is enough to prove that there exist a point $Q=(z_{1}^{\prime},\dots
z_{n}^{\prime})$ satisfying (8) and also satisfy one of the following
relations

  1. I.

For all $1\leq i\leq n$, if $v_{B_{i}^{n}}(P)>0$, then $v_{B_{i}^{n+1}}(Q)>0$,

  2. II.

For all $1\leq i\leq n$, if $v_{B_{i}^{n}}(P)<0$, then $v_{B_{i}^{n+1}}(Q)<0$
or

  3. III.

If $v_{B_{i_{j}}^{n}}(P)>0$ and $v_{B_{m_{j}}^{n}}(P)<0$, then
$v_{\tilde{B}_{i_{j}}^{n+1}}(Q)>0$ and $v_{\tilde{B}_{m_{j}}^{n+1}}(Q)<0$
where $1\leq i_{j}$, $m_{j}\leq n$.

Let us assume that $z_{1}\geq 0$.

  * •

Case [I]:

Suppose we have $v_{B_{i}^{n}}(P)>0$, for all $i$. Then Choose $Q=P$, one has
$v_{B_{i}^{n+1}}(Q)>0$.

  * •

Case [III]: Let $v_{B_{i_{j}}^{n}}(P)>0$ and $v_{B_{m_{j}}^{n}}(P)<0$, where
$1\leq i_{j}$, $m_{j}\leq n$.

Hence,

$z_{1}+E_{i_{j}}(P)>0,\hskip 5.0ptz_{1}+E_{m_{j}}(P)<0.$

Consider

$M_{P}:=Min_{m_{j}}\\{-E_{m_{j}}(P)/2\\}>0.$

If $z_{1}<M_{P}$, consider $Q=P$ and $v_{\tilde{B}_{i_{j}}^{n+1}}(Q)>0\hskip
3.0pt\text{and }v_{\tilde{B}_{m_{j}}^{n+1}}(Q)<0$ holds. Suppose
$z_{1}>M_{P}>0$. Then the entries of the point $P$ must have one of the
following presentations

$0<M_{P}<z_{\lambda_{1}}=z_{1}<z_{\lambda_{2}}<\dots<z_{\lambda_{i}}<z_{\lambda_{i+1}}<\dots<z_{\lambda_{n}},$
(9)

or, for some $1\leq i\leq k-1$ and $0\leq j\leq i-2$,

$z_{\lambda_{1}}<\dots<z_{\lambda_{k-i-1}}<0<z_{\lambda_{k-i}}<\dots<z_{\lambda_{k-i+j}}<M_{P}<z_{\lambda_{k-i+j+1}}<\dots<z_{\lambda_{k-1}}=z_{1}<\dots<z_{\lambda_{n}}.$
(10)

If the entries of the point $P$ satisfy the presentation given in (9),
consider $z_{1}^{\prime}$ any real number such that
$0<z_{1}^{\prime}<M_{P}<z_{\lambda_{1}}=z_{1}$ and $z_{t}^{\prime}=z_{t}$ for
all $1<t\leq n$. Since $E_{m_{j}}(Q)=E_{m_{j}}(P)$ and
$z_{1}^{\prime}<M_{P}\leq-E_{m_{j}}/2$ implies
$2z_{1}^{\prime}+E_{m_{j}}(P)<0$. Thus

$B_{m_{j}}^{n+1}(Q)=2z_{1}^{\prime}+E_{m_{j}}(P)<0.$

Suppose the entries of the point $P$ is given by (10). Let

$m:=z_{\lambda_{k-i+j+1}}-M_{P}.$

Choose $\epsilon>0$ such that

$z_{\lambda_{k-i+j}}<M_{p}-\epsilon<M_{P}.$

Pick

$z_{\lambda_{k-i+j+1}}^{\prime}=z_{\lambda_{k-i+j+1}}-m-{\epsilon}=M_{P}-\epsilon,$
$z_{\lambda_{k-i+j+2}}^{\prime}=z_{\lambda_{k-i+j+1}}-m-{\epsilon}/2=M_{P}-\epsilon/2,$

and finally

$z_{\lambda_{k-2}}^{\prime}=z_{\lambda_{k-i+j+1}}-m-\frac{\epsilon}{j-i}=M_{P}-\frac{\epsilon}{j-i}$

and $z_{\lambda_{t}}^{\prime}=z_{\lambda_{t}}$, for all $t\leq k-i+j$ and
$t\geq\lambda_{k}$. In particular one has

$z_{t}\leq z_{t}^{\prime}.$ (11)

There always exist a real number $z_{1}^{\prime}$ such that
$M_{P}-\frac{\epsilon}{j-i}<z_{1}^{\prime}<M_{P}$. Since,
$z_{1}^{\prime}<M_{P}\leq-E_{m_{j}}/2$ implies
$2z_{1}^{\prime}+E_{m_{j}}(P)<0$. Hence

$\displaystyle 2z_{1}^{\prime}+E_{m_{j}}(P^{\prime})=$ $\displaystyle
2z_{1}^{\prime}+2z_{m_{j}}^{\prime}+\sum_{l\neq m_{j},1}z_{l}^{\prime}\leq$
$\displaystyle 2z_{1}^{\prime}+2z_{m_{j}}+\sum_{l\neq m_{j},1}z_{l}\hskip
5.0pt(\text{ using }\eqref{tataa})$
$\displaystyle=2z_{1}^{\prime}+E_{m_{j}}(P)<0.$

Hence $\tilde{B}_{m_{j}}^{n+1}(Q)<0$ and $\tilde{B}_{i_{j}}^{n+1}(Q)>0$ for
$1\leq i_{j}$, $m_{j}\leq n$.

The case $z_{1}=M_{p}$ is similar to the above case.

  * •

Case [II]:

Let $v_{B_{i}^{n}}(P)<0$ for all $1\leq i\leq n$. If $z_{1}<M_{P}$, consider
$Q=P$ and $v_{B_{i}^{n+1}}(Q)<0$ holds. Otherwise we can proceed as follows.
Since $v_{\tilde{B}_{i}^{n+1}}(Q)<0$ for all $1\leq i\leq n$, the entries of
the the point $P$ can only have the presentation in (17) (Since $z_{i}$ are
all positive). Now the proof follows by doing steps as in the Case [III].

The case $z_{1}<0$ is similar to the case $z_{1}\geq 0$, so we skip the proof
here. Hence if $C$ be any open cell in $\mathcal{C}_{{\mathds{R}}^{n}}$
satisfy any of the condition, there exist an cell
$C^{\prime}\in\mathcal{C}_{W_{n}}$ satisfy the similar condition. ∎

######  Lemma 3.4.

There is an order-preserving bijection between the poset of cells of
codimension $\geq 1$ associated to the hyperplane arrangements of
$\mathcal{H}_{{\mathds{R}}^{n}}$ and $\mathcal{H}_{W_{n}}$ in
${\mathds{R}}^{n}$.

###### Proof.

Let $C\in\mathcal{C}_{\mathds{R}^{n}}$ be a cell of codimension $\geq 1$ such
that at least one of entries of the sign vectors of $v(C)$ is zero.
Equivalently, for every point $P\in C$, such that either $A_{i,j}^{n}(P)=0$ or
$B^{n}_{i}(P)=0$, for some $1\leq i<j\leq n$. Let us consider the following
cases.

  * •

Case [I]: None of $A_{i,j}^{n}$ is vanishing at $P$. In particular, the
entries of the point $P\in C$ has the following representation

$z_{\lambda_{1}}<z_{\lambda_{2}}<\dots<z_{\lambda_{i}}<z_{\lambda_{i+1}}<\dots<z_{\lambda_{n}}.$
(12)

Then $B^{n}_{i}(P)=0$ for exactly one $i$ satisfying $1\leq i\leq n$. Indeed,
for any $P=(z_{1},z_{2},\dots,z_{n})$ and $a\leq i_{1}$, $i_{2}\leq n$,

$v_{B_{i_{1}}^{n}}(P)=v_{B_{i_{2}}^{n}}(P)=0,$

implies $z_{i_{1}}=z_{i_{2}}$. Hence $A_{i_{1},i_{2}}^{n}(P)=0$, a
contradiction. The entries of the sign vector $v(C)$ corresponding to
$B_{i}^{n}$ must be of the form

$v_{B_{i_{j}}^{n}}(P)>0,\hskip 5.0ptv_{B_{l}^{n}}(P)=0\hskip 3.0pt\text{ and
}v_{B_{m_{j}}^{n}}(P)<0,$ (13)

where $1\leq i_{j}$, $l$, $m_{j}\leq n$ for all $j$. Our claim there is a
point $Q\in{\mathds{R}}^{n}$ satisfying the presentation in (12) such that

$v_{\tilde{B}_{i_{j}}^{n+1}}(Q)>0,\hskip
5.0ptv_{\tilde{B}_{l}^{n+1}}(Q)=0\hskip 3.0pt\text{ and
}v_{\tilde{B}_{m_{j}}^{n+1}}(Q)<0,$ (14)

From (13), one obtains for $1\leq i_{j}$, $l$, $m_{j}\leq n$

$z_{1}+E_{i_{j}}(P)>0,\hskip 5.0ptz_{1}+E_{m_{j}}(P)<0\hskip 3.0pt\text{ and
}z_{1}=-E_{l}(P).$ (15)

In particular one has

$z_{1}=-E_{l}(P)<-E_{m_{j}}(P)\hskip 3.0pt\text{and
}-E_{l}(P)<z_{\lambda_{n}}\hskip 3.0pt\text{for all }m_{j}.$ (16)

Let us assume that $z_{1}\geq 0$. _Sub-Case 1_ : The entries of $P$ must be of
the following form

$z_{\lambda_{1}}<\dots<z_{\lambda_{k-i-1}}<0<z_{\lambda_{k-i}}<\dots<z_{\lambda_{k-i+j}}<-E_{l}/2<z_{\lambda_{k-i+j+1}}<\dots<z_{\lambda_{k-1}}=z_{1}<\dots<z_{\lambda_{n}},$
(17)

where $1\leq i\leq k-1$ and $0\leq j\leq i-2$.

Let

$m:=z_{\lambda_{k-i+j+1}}+E_{l}/2.$

Choose $\epsilon>0$, small enough so that

$\dots<z_{\lambda_{k-i+j}}<z_{\lambda_{k-i+j+1}}-m-\epsilon<-E_{l}(P)/2<z_{\lambda_{k-i+j+1}}<\dots$

For $l\notin\\{\lambda_{k-i+j+1},\dots,\lambda_{k-1}\\}$, pick

$z_{\lambda_{k-i+j+1}}^{\prime}=z_{\lambda_{k-i+j+1}}-m-{\epsilon}=\frac{-E_{l}}{2}-\epsilon,$
$z_{\lambda_{k-i+j+2}}^{\prime}=z_{\lambda_{k-i+j+1}}-m-{\epsilon}/2=\frac{-E_{l}}{2}-\epsilon/2,$

and finally

$z_{\lambda_{k-2}}^{\prime}=z_{\lambda_{k-i+j+1}}-m-\frac{\epsilon}{j-i}=\frac{-E_{l}}{2}-\frac{\epsilon}{j-i}$

and $z_{\lambda_{t}}^{\prime}=z_{\lambda_{t}}$, for all $t\leq k-i+j$ and
$n>t\geq\lambda_{k}$ and

$z_{n}^{\prime}=z_{n}+\sum_{2\leq t\leq
i-j-1}(z^{\prime}_{\lambda_{k-t}}-z_{\lambda_{k-t-1}}).$

In particular, one has

$z_{t}^{\prime}\leq z_{t}$ (18)

Since $E_{\lambda_{k}}>E_{\lambda_{k+1}}$ for all $k$, one necessarily has

$l\neq\lambda_{n}\hskip 3.0pt\text{and }m_{j}\neq\lambda_{n}\text{ for all
j}.$ (19)

Hence for $l\notin\\{\lambda_{k-i+j+1},\dots,\lambda_{k-1},\lambda_{n}\\}$,

$\displaystyle\tilde{B}_{l}^{n+1}(Q)=$ $\displaystyle
2z_{1}^{\prime}+2z_{l}^{\prime}+\sum_{t\neq 1,l}z_{t}^{\prime}$
$\displaystyle=$ $\displaystyle
2z_{1}^{\prime}+2z_{l}^{\prime}+\sum_{t\in[1,k-i+j]\cup[k+1,n-1]}z_{\lambda_{t}}+\left(z_{\lambda_{k-i+j+1}}^{\prime}+\dots+z_{\lambda_{k-1}}^{\prime}\right)+z_{\lambda_{n}}^{\prime}$
$\displaystyle=$ $\displaystyle 2z_{1}^{\prime}+E_{l}(Q)$ $\displaystyle=$
$\displaystyle 2z_{1}^{\prime}+E_{l}(Q)=0$

On the other hand if there exist a $j_{0}$ such that
$m_{j_{0}}\in\\{\lambda_{k-i+j+1},\dots,\lambda_{k-1}\\}$,

$\displaystyle\tilde{B}_{\lambda_{m_{j_{0}}}}^{n+1}(Q)=$ $\displaystyle
2z_{1}^{\prime}+E_{\lambda_{m_{j_{0}}}}(Q)$ $\displaystyle=$ $\displaystyle
2z_{1}^{\prime}+2z_{\lambda_{m_{j_{0}}}}^{\prime}+\sum_{t\neq\lambda_{m_{j_{0}}},1}z_{t}^{\prime}$
$\displaystyle=$ $\displaystyle
2z_{1}^{\prime}+2z_{\lambda_{m_{j_{0}}}}+\sum_{t\neq\lambda_{m_{j_{0}}},1}z_{t}-(z_{\lambda_{m_{j_{0}}}}-z_{\lambda_{m_{j_{0}}}}^{\prime})$
$\displaystyle=$ $\displaystyle
2z_{1}^{\prime}+E_{\lambda_{m_{j_{0}}}}(P)-(z_{\lambda_{m_{j_{0}}}}-z_{\lambda_{m_{j_{0}}}}^{\prime})$
$\displaystyle=$ $\displaystyle-
E_{l}(P)+E_{m_{j_{0}}}(P)-(z_{\lambda_{m_{j_{0}}}}-z_{\lambda_{m_{j_{0}}}}^{\prime})<0\hskip
3.0pt\text{ by \eqref{taa1}}\text{ and }\eqref{tataa}.$

For $m_{j_{0}}<\lambda_{k-i+j}$ and $\lambda_{k-1}<m_{j_{0}}<\lambda_{n}$,

$\displaystyle\tilde{B}_{m_{j_{0}}}^{n+1}(Q)=$ $\displaystyle
2z_{1}^{\prime}+E_{\lambda_{m_{j_{0}}}}(Q)$ $\displaystyle=$ $\displaystyle
2z_{1}^{\prime}+2z_{m_{j_{0}}}^{\prime}+\sum_{t\neq\lambda_{m_{j_{0}}},1}z_{t}^{\prime}$
$\displaystyle=$ $\displaystyle
2z_{1}^{\prime}+2z_{m_{j_{0}}}+\sum_{t\neq\lambda_{m_{j_{0}}},1}z_{t}$
$\displaystyle=$ $\displaystyle 2z_{1}^{\prime}+E_{\lambda_{m_{j_{0}}}}(P)$
$\displaystyle=$ $\displaystyle-E_{l}(P)+E_{m_{j}}(P)<0\hskip
3.0pt(by\eqref{taa1}).$

If $l\in\\{\lambda_{k-i+j+1},\dots,\lambda_{k-1}\\}$, in particular
$l=\lambda_{k-i+j+t_{0}}$ where $1\leq t_{0}\leq i-j-1$. Then define
$z^{\prime}_{\lambda_{t}}=z_{\lambda_{t}}$ as in the previous case for
$t\neq\lambda_{n}$ and

$z_{n}^{\prime}:=z_{n}+\sum_{t\neq
1,j-i+t_{0}}\left(z_{\lambda_{k-t}}-z_{\lambda_{k-t-1}}\right)+2\left(z_{\lambda_{k-i+j+t_{0}}}-z_{\lambda_{k-i+j+t_{0}-1}}\right).$

Now one necessarily has $\tilde{B}_{l}^{n+1}(Q)=0$. Since
$B_{\lambda_{i}}^{n}(P)<B_{\lambda_{i+1}}^{n}(P)$ for all $i$, one necessarily
has $B_{k-i+j+t_{0}-1}^{n}(Q)<0$. Hence it enough to show that

$\tilde{B}_{\lambda_{k-i+j+t_{0}-1}}^{n+1}(Q)<0.$

Now

$\displaystyle\tilde{B}_{\lambda_{k-i+j+t_{0}-1}}^{n+1}(Q)=$ $\displaystyle
2z_{1}^{\prime}+E_{\lambda_{\lambda_{k-i+j+t_{0}-1}}}(Q)$ $\displaystyle=$
$\displaystyle
2z_{1}^{\prime}+2z_{\lambda_{\lambda_{k-i+j+t_{0}-1}}}^{\prime}+\sum_{t\neq\lambda_{\lambda_{k-i+j+t_{0}-1}},1}z_{t}^{\prime}$
$\displaystyle=$ $\displaystyle
2z_{1}^{\prime}+2z_{\lambda_{\lambda_{k-i+j+t_{0}-1}}}+\sum_{t\neq\lambda_{k-i+j+t_{0}-1},1}z_{t}$
$\displaystyle-\left(z_{\lambda_{\lambda_{k-i+j+t_{0}-1}}}-z_{\lambda_{\lambda_{k-i+j+t_{0}-1}}}^{\prime}\right)+\left(z_{\lambda_{\lambda_{k-i+j+t_{0}}}}-z_{\lambda_{\lambda_{k-i+j+t_{0}}}}^{\prime}\right)$
$\displaystyle=$ $\displaystyle
2z_{1}^{\prime}+E_{\lambda_{k-i+j+t_{0}-1}}(P)+\left(z_{\lambda_{\lambda_{k-i+j+t_{0}}}}-z_{\lambda_{\lambda_{k-i+j+t_{0}-1}}}\right)$
$\displaystyle+\left(z_{\lambda_{\lambda_{k-i+j+t_{0}-1}}}^{\prime}-z_{\lambda_{\lambda_{k-i+j+t_{0}}}}^{\prime}\right)$
$\displaystyle=$ $\displaystyle
2z_{1}^{\prime}+E_{\lambda_{k-i+j+t_{0}}}(P)+\left(z_{\lambda_{\lambda_{k-i+j+t_{0}-1}}}^{\prime}-z_{\lambda_{\lambda_{k-i+j+t_{0}}}}^{\prime}\right)<0.\hskip
3.0pt$

  * •

Case [II]

Suppose the entries of the point $P\in C$ has the following representation

$z_{\lambda_{1}}<z_{\lambda_{2}}=\dots=z_{\lambda_{i_{1}}}<z_{\lambda_{i_{1}+1}}=z_{\lambda_{i_{2}}}<\dots<z_{\lambda_{n}}.$
(20)

The entries of the sign vector $v(C)$ corresponding to $B_{i}^{n}$ has the
following possibilities. Either

    1. (1)

all of the $v_{B_{i}^{n}}(P)>0$,

    2. (2)

all of the $v_{B_{i}^{n}}(P)<0$, or

    3. (3)

few of $v_{B_{i_{j}}^{n}}(P)>0$ and $v_{B_{m_{j}}^{n}}(P)<0$,

    4. (4)

$v_{B_{i_{j}}^{n}}(P)>0$, $v_{B_{l_{j}}^{n}}(P)=0$ and
$v_{B_{m_{j}}^{n}}(P)<0$, where $1\leq i_{j}$, $l$, $m_{j}\leq n$ for all $j$.

Our claim is the following

    1. I.

For all $1\leq i\leq n$, if $v_{B_{i}^{n}}(P)>0$, then
$v_{\tilde{B}_{i}^{n+1}}(Q)>0$,

    2. II.

For all $1\leq i\leq n$, if $v_{B_{i}^{n}}(P)<0$, then
$v_{\tilde{B}_{i}^{n+1}}(Q)<0$ or

    3. III.

If $v_{B_{i_{j}}^{n}}(P)>0$ and $v_{B_{m_{j}}^{n}}(P)<0$, then
$v_{\tilde{B}_{i_{j}}^{n+1}}(Q)>0$ and $v_{\tilde{B}_{m_{j}}^{n+1}}(Q)<0$
where $1\leq i_{j}$, $m_{j}\leq n$.

    4. IV.

If $v_{B_{i_{j}}^{n}}(P)>0$, $v_{B_{l_{j}}^{n}}(P)=0$ and
$v_{B_{m_{j}}^{n}}(P)<0$, then $v_{\tilde{B}_{i_{j}}^{n+1}}(Q)>0$,
$v_{\tilde{B}_{l_{j}}^{n+1}}(Q)=0$ and $v_{\tilde{B}_{m_{j}}^{n+1}}(Q)<0$,

The proof of claim [I], [II]and [III] is similar to the case 3.3. The proof of
claim [IV] can be reduced to the proof in Case [I] as follows. One has

$v_{B_{i_{1}}^{n}}(P)=v_{B_{i_{1}}^{n}}(P)=0$

implies $z_{i_{1}}=z_{i_{2}}$. Moreover
$v_{B_{l_{1}}^{n}}(P)<v_{B_{l_{2}}^{n}}(P)$ if $z_{l_{1}}<z_{l_{2}}$.
Therefore identifying equalities in (20) can be reduced to (8) and the
condition (3) can be reduced to the Case[I].

∎

Recall that the hyperplane arrangement $\mathcal{H}_{{\mathds{R}}^{n}}$ and
$\mathcal{A}_{n}$ are isomorphic since one is the pullback of the other under
the natural linear isomorphism $\phi_{n}$, for all $n$. For any $1\leq i<j\leq
n+1$, let $W_{n}^{i,j}:={\mathds{R}}^{n+1}\cap\phi_{n+1}^{*}(L_{i,j}^{n+1})$
be a linear subspace of dimension $n$ with an arrangement
$\mathcal{H}_{W_{n}^{i,j}}$ induced by $\mathcal{A}_{n+1}$. Similar to the
case $i=1$ and $j=n+1$ there is a natural isomorphism of linear spaces
${\mathds{R}}^{n}\longrightarrow W_{n}^{i,j}$ which induces an embedding of
corresponding posets.

######  Theorem 3.5.

Let $W_{n}^{i,j}:={\mathds{R}}^{n+1}\cap A_{i,j}^{n+1}$. There is an order
preserving bijection
$\iota_{n}^{i,j}:\mathcal{C}_{{\mathds{R}}^{n}}\longrightarrow\mathcal{C}_{W_{n}^{i,j}}$
which induces an order preserving embedding

$\iota_{L_{i,j}^{n+1}}:\mathcal{C}_{\mathcal{A}_{n}}\longrightarrow\mathcal{C}_{\mathcal{A}_{n+1}}.$

###  3.2. Double representation for Coxeter arrangement

From Theorem 2.5, the abelian category
$\mathscr{P}er(V_{{\mathds{C}}}^{n},S^{n})$ is equivalent to the abelian
category $\mathcal{J}_{\mathcal{A}_{n}}$, the full subcategory of double
representations of $\mathcal{C}_{\mathcal{A}_{n}}$ satisfying _monotonicity_ ,
_transitivity_ and _invertibility_. Let us denote
$\mathcal{J}_{n}:=\mathcal{J}_{\mathcal{A}_{n}}$. Reacll that the hyperplane
arrangement $\mathcal{H}_{\mathcal{A}_{n}}$ is isomorphic to the hyperplane
arrangement $\mathcal{H}_{{\mathds{R}}^{n}}$ in ${\mathds{R}}^{n}$ for all $n$
and $\mathcal{H}_{\mathcal{A}_{n+1}}$ induces an arrangement on
$L^{n+1}_{i,j}$. The induced arrangement on $L^{n+1}_{i,j}$ is isomorphic to
$\mathcal{H}_{W_{n}^{i,j}}$. By Theorem 3.5 there is an order preserving
bijection between posets of faces of the above two arrangements
$\mathcal{H}_{{\mathds{R}}^{n}}$ and $\mathcal{H}_{W_{n}^{i,j}}$. In
particular, there is an order preserving embedding of posets

$\iota_{L_{i,j}^{n+1}}:\mathcal{C}_{\mathcal{A}_{n}}\hookrightarrow\mathcal{C}_{\mathcal{A}_{n+1}}.$

Define

$\tilde{\Phi}_{L_{i,j}^{n+1}}:\operatorname{Rep}_{2}(\mathcal{A}_{n})\rightarrow\operatorname{Rep}_{2}(\mathcal{A}_{n+1})$
$\psi=(E_{C},\gamma_{C^{\prime}C},\delta_{CC^{\prime}})_{(C,C^{\prime}\in\mathcal{C}_{\mathcal{A}_{n}})}\mapsto\tilde{\Phi}_{L_{i,j}^{n+1}}\psi:=(\tilde{E}_{D},\tilde{\gamma}_{D^{\prime}D},\tilde{\delta}_{DD^{\prime}})_{(D,D^{\prime}\in\mathcal{C}_{\mathcal{A}_{n+1}})},$

where

$\displaystyle\tilde{E}_{D}$
$\displaystyle=E_{\iota_{L_{i,j}^{n+1}}(\tilde{C})}\hskip 10.0pt\text{ if
}D=\iota_{L_{i,j}^{n+1}}(\tilde{C})$ $\displaystyle=0,\text{ otherwise.}$

######  Proposition 3.6.

For any $1\leq i<j\leq n+1$, $\tilde{\Phi}_{L_{i,j}^{n+1}}$ induces an exact
and fully-faithful functor
$\Phi_{L_{i,j}^{n+1}}:\mathcal{J}_{n}\rightarrow\mathcal{J}_{n+1}$.

###### Proof.

Let $\mathcal{J}_{n+1|L^{n+1}_{i,j}}$ be the full subcategory of
$\mathcal{J}_{n+1}$ consisting of double representations of poset associated
to the induce hyperplane arrangement on $L^{n+1}_{i,j}$. Thus any element of
$\mathcal{J}_{n+1|L^{n+1}_{i,j}}$ can be identified with
$(E_{C},\gamma_{C^{\prime}C},\delta_{CC^{\prime}})_{(C,C^{\prime}\in\bar{\mathcal{C}}_{\mathcal{A}_{n}})}$
where
$\bar{\mathcal{C}}_{\mathcal{A}_{n}}:=\iota_{L_{i,j}^{n+1}}(\mathcal{C}_{\mathcal{A}_{n}})$.
In order to prove $\tilde{\Phi}_{L_{i,j}^{n+1}}$ induces the following functor

$\Phi_{L_{i,j}^{n+1}}:\mathcal{J}_{n}\rightarrow\mathcal{J}_{n+1|L^{n+1}_{i,j}}\subseteq\mathcal{J}_{n+1},$

it is enough to show that $\tilde{\Phi}_{L_{i,j}^{n+1}}(\psi)$ satisfies
monotonicity, transitivity and invertibility. For simplicity, we consider the
case $i=1$ and $j=n+1$.

_Monotonicity_ $:$ For any
$\psi=(E_{C},\gamma_{C^{\prime}C},\delta_{CC^{\prime}})_{(C,C^{\prime}\in\mathcal{C}_{\mathcal{A}_{n}})}\in\mathcal{J}_{n}$,
by montonicity one has

$\gamma_{C^{\prime}C}\delta_{CC^{\prime}}=Id_{E_{C}},$

where $C^{\prime}$, $C\in\mathcal{C}_{\mathcal{A}_{n}}$ satisfying
$C^{\prime}\leq C$. Hence
$\iota_{L_{1,n+1}^{n+1}}(C^{\prime})\leq\iota_{L_{1,n+1}^{n+1}}(C)$. Thus
$\tilde{\Phi}_{L_{i,j}^{n}}(\psi)$ satisfies monotonicity relation for
$D=\iota_{L_{1,n+1}^{n+1}}(C)$ and
$D^{\prime}=\iota_{L_{1,n+1}^{n+1}}(C^{\prime})$. For any
$D\subset(V^{n+1}\setminus L^{n+1}_{1,n+1})$, one has $E_{D}=0$ and
$\delta_{DD^{\prime}}$ is the zero map. Hence monotonicity is satisfied by
$\Phi_{L_{1,n+1}^{n+1}}(\psi)$.

_Transitivity_ $:$ For a collinear triple
$(A,B,C)\in\mathcal{C}_{\mathcal{A}_{n}}^{3}$, using the transitivity relation
on $\phi$ one obtains $\phi_{AC}=\phi_{BC}\phi_{AB}$. In order to check
transitivity for $\Phi_{L_{1,n+1}^{n+1}}(\psi)$, it is enough to prove
transitivity for all collinear triples in
$\mathcal{C}_{\mathcal{A}_{n+1}}^{3}$.

If $A$, $B$ and $C\subset L^{n+1}_{1,n+1}$, then collinear triple $(A,B,C)$ is
a image of a collinear triple in $\mathcal{C}_{\mathcal{A}_{n}}$. Hence
transitivity of such a triple is satisfied by the transitivity relation of
$\psi$. If any two of $A$, $B$ and $C$ lies in $L^{n+1}_{1,n+1}$ then the
third one must lie on $L^{n+1}_{1,n+1}$, as $L^{n+1}_{1,n+1}$ is a linear
subspace of $V^{n+1}$. Hence the transitivity is satisfied for such triple
follows from the previous case. If $A$, $C\subset(V^{n+1}\setminus
L^{n+1}_{1,n+1})$ and $B\subset L^{n+1}_{1,n+1}$, then from definition it
follows that $E_{A}=E_{C}=0$ with $\phi_{AC}=0$ and $\phi_{AB}=0$. Hence
$\phi_{AC}=\phi_{BC}\phi_{AB}=0$. Similarly if none of the $A$, $B$ and $C$
lies in $L^{n+1}_{1,n+1}$, then $E_{A}=E_{B}=E_{C}=0$ and
$\phi_{AC}=\phi_{BC}=\phi_{AB}=0$. Thus transitivity holds for
$\Phi_{L_{1,n+1}^{n+1}}(\psi)$.

_Invertibility_ $:$ Let $C_{1}$ and $C_{2}$ be two faces opposes through a
$(d-1)$-dimensional face $B$. Then $\phi_{C_{1}C_{2}}$ is an isomorphism. Thus
either $C_{1}$ and $C_{2}$ both lies in $L^{n+1}_{1,n+1}$ or both do not lie
in $L^{n+1}_{1,n+1}$. In any case it is an isomorphism.

∎

######  Theorem 3.7.

For any $1\leq i<j\leq n+1$, there is a fully-faithful exact functor
compatible with the Verdier duality

$\Lambda_{L_{i,j}^{n+1}}:\mathscr{P}er(V_{{\mathds{C}}}^{n},\mathcal{S}^{n})\rightarrow\mathscr{P}er(V_{{\mathds{C}}}^{n+1},\mathcal{S}^{n+1}),$
(21)

which makes the following diagram commutative

${\mathscr{P}er(V_{{\mathds{C}}}^{n},\mathcal{S}^{n})}$${\mathcal{J}_{i}}$${\mathscr{P}er(V_{{\mathds{C}}}^{n+1},\mathcal{S}^{n+1})}$${\mathcal{J}_{n+1}.}$$\scriptstyle{\mathcal{Q}^{n}}$$\scriptstyle{\Lambda_{L_{i,j}^{n+1}}}$$\scriptstyle{\Phi_{L_{i,j}^{n}}}$$\scriptstyle{\mathcal{Q}^{n+1}}$

Moreover image of simple objects are simple.

###### Proof.

We have the following commutative diagram

${\mathscr{P}er(V_{{\mathds{C}}}^{n},\mathcal{S}^{n})}$${\mathcal{J}_{n}}$${\mathscr{P}er(L^{n+1}_{i,j},\mathcal{S}_{|L^{n+1}_{i,j}}^{n+1})}$${\mathcal{J}_{n+1|L^{n+1}_{i,j}}}$${\mathscr{P}er(V_{{\mathds{C}}}^{n+1},\mathcal{S}^{n+1})}$${\mathcal{J}_{n+1}.}$$\scriptstyle{\mathcal{Q}^{n}}$$\scriptstyle{\cong}$$\scriptstyle{\Phi_{L_{i,j}^{n}}}$$\scriptstyle{\mathcal{Q}^{n+1}_{|L^{n+1}_{i,j}}}$$\scriptstyle{(h_{(-1)}\circ
k_{*})[-1]}$$\scriptstyle{r_{*}}$$\scriptstyle{\mathcal{Q}^{n+1}}$

In this diagram, $r_{*}$ is the right adjoint of the hyperbolic restriction,
[Sec 5.A, [KS16]], where
$k:L_{i,j\mathbb{C}}\hookrightarrow\mathbb{R}^{n}+iL_{i,j}$ and
$h:R^{n}+iL_{i,j}\hookrightarrow V_{\mathbb{C}}^{n}$. Let $h_{(-1)}$ be the
right adjoint of $h^{!}$.

The functor $\mathcal{Q}^{n+1}_{|L^{n+1}_{i,j}}$ and $\Phi_{L_{i,j}^{n}}$ are
equivalence of categories (by 2.5 and 3.6). Let $\Theta^{n+1}$ be the inverse
of the functor $\mathcal{Q}^{n+1}$ and $\Theta^{n+1}_{|L^{n+1}_{i,j}}$ be the
the inverse of $\mathcal{Q}^{n+1}_{|L^{n+1}_{i,j}}$, the restriction
$\mathcal{Q}^{n+1}$. Thus the top left vertical functor

$\Theta^{n+1}_{|L^{n+1}_{i,j}}\circ\Phi_{L_{i,j}^{n}}\circ\mathcal{Q}^{n}$

is an equivalence of categories.

We can check that the lower square commutes with hyperbolic extensions $r^{*}$
on right and $(k^{*}\circ h^{!}[1])$ on left, [Prop 5.1, [KS16]]. Hence using
the adjunction required square commutes i.e.
$r_{*}\circ\mathcal{Q}^{n+1}_{|L^{n+1}_{i,j}}=\mathcal{Q}^{n+1}\circ((h_{(-1)}\circ
k_{*})[-1])$. Therefore we can define

$\Lambda_{L_{i,j}^{n+1}}:=\Theta^{n+1}\circ
r_{*}\circ\Phi_{L_{i,j}^{n}}\circ\mathcal{Q}^{n},$

which gives a fully faithful exact functor with the required commutative
square. The compatibility with the Verdier duality follows from the fact that
all three arrows are compatible with duality. The last assertion follows from
the fact that any sub-object of the image is again in the image. ∎

######  Corollary 3.8.

Let $\mathcal{F}$ be a constructible sheaves on the hyperplane arrangement
$\mathcal{A}_{n+1}$. Then we have the following.

  1. (1)

If $\mathcal{F}\in\mathscr{P}er(V_{{\mathds{C}}}^{n+1},\mathcal{S}^{n+1})$ is
irreducible then $\operatorname{dim}_{{\mathds{C}}}(E_{C}(\mathcal{F}))=0$ or
$1$, where $C$ be any open cell in $\mathcal{C}_{\mathcal{A}_{n+1}}$.

  2. (2)

Suppose
$\mathcal{F}\in\mathscr{P}er(V_{{\mathds{C}}}^{n+1},\mathcal{S}^{n+1})$ is
irreducible and $\operatorname{dim}_{{\mathds{C}}}(E_{C}(\mathcal{F}))=0$
where $C$ be any open cell in $\mathcal{C}_{\mathcal{A}_{n+1}}$. Then there
exists $\mathcal{G}\in\mathscr{P}er(V_{{\mathds{C}}}^{n},\mathcal{S}^{n})$ and
$L_{i,j}^{n+1}\in\mathcal{H}_{\mathcal{A}_{n+1}}$ such that

$\Lambda_{L_{i,j}^{n+1}}(\mathcal{G})=\mathcal{F}.$

###### Proof.

  1. (1)

For any two open cell $C$ and $C^{\prime}\in\mathcal{C}_{\mathcal{A}_{n}}$,
there exist

$\phi_{CC^{\prime}}:E_{C}(\mathcal{F})\longrightarrow
E_{C^{\prime}}(\mathcal{F}),$

which is an isomorphism by invertibility. Thus if $E_{\lambda}\subset
E_{C}(\mathcal{F})$ be a proper subspace, one necessarily has a proper
subspace $\phi_{CC^{\prime}}(E_{\lambda})\subset E_{C^{\prime}}(\mathcal{F})$.
Since, by monotonicity, for any faces $D$, $C$ satisfying $D\leq C$, one has a
injective map $\delta_{DC}:E_{C}(\mathcal{F})\longrightarrow
E_{D}(\mathcal{F})$. Hence one can generate a proper subrepresentation of
$\left(E_{C}(\mathcal{F}),\delta_{C^{\prime}C},\gamma_{CC^{\prime}}\right)_{C\in\mathcal{C}_{\mathcal{A}_{n}}}$
by taking translates of $E_{\lambda}$ under various maps
$\delta_{\star,\star}$.

Thus if
$\left(E_{C}(\mathcal{F}),\delta_{C^{\prime}C},\gamma_{CC^{\prime}}\right)_{C\in\mathcal{C}_{\mathcal{A}_{n}}}$
is irreducible then $E_{C}(\mathcal{F})$ is irreducible if and only if
$\operatorname{dim}_{{\mathds{C}}}(E_{C}(\mathcal{F}))=0$ or $1$.

  2. (2)

Suppose $\mathcal{F}$ is irreducible and there exist two distinct codimension
one cell $D_{1}$ and $D_{2}$ and two distinct hyperplanes $H_{1}$ and
$H_{2}\in\mathcal{A}_{n+1}$ such that for all $i$

$\displaystyle E_{D_{i}}(\mathcal{F})$ $\displaystyle\neq 0$ $\displaystyle
D_{i}\subset$ $\displaystyle H_{i}$

There exist an open cell $C$ in $\mathcal{A}_{n+1}$ such that
$(D_{1},C,D_{2})$ form a collinear triple. Indeed, any line joining $d_{1}\in
D_{1}$ and $d_{2}\in D_{2}$ must intersect an open cell, Since $D_{i}$ is a
connected component of $H_{i}\setminus\cup_{H_{j}(\neq
H_{i})\in\mathcal{A}_{n+1}}\left(H_{j}\cap H_{k}\right)$ for $i\in\\{1,2\\}$.
Then by transitivity

$\phi_{D_{1}D_{2}}=\phi_{C_{2}D_{2}}\phi_{D_{1}C_{2}}=0$

Similarly there exist $L\subset H_{1}\cap H_{2}$, a cell of codimension one in
$H_{1}$ and $H_{2}$ such that $(D_{1},L,D_{2})$ forms a collinear triple. Then
$\phi_{D_{1}D_{2}}=\gamma_{LD_{2}}\delta_{D_{1}L}=0$. Hence

$\operatorname{Im}(\delta_{D_{1}L})\subset\operatorname{Ker}(\gamma_{LD_{2}}).$

In other words $E_{L}(\mathcal{F})$ contains
$\operatorname{Im}(\delta_{D_{1}L})$ and $\operatorname{Im}(\delta_{D_{2}L})$
as direct summand. Similarly it happen in all other cells contained in
$H_{1}\cap H_{2}$. Hence $E_{C}(\mathcal{F})$ can not be irreducible, which a
contradiction.

∎

######  Corollary 3.9.

Let $\mathcal{F}\in\mathscr{P}er(V_{{\mathds{C}}}^{2},\mathcal{S}^{2})$ be be
a perverse sheaves on the hyperplane arrangement $\mathcal{A}_{2}$. If
$\mathcal{F}$ is irreducible and $\operatorname{dim}E_{C}(\mathcal{F})=1$,
where $C$ be an open cells, then $\operatorname{dim}E_{D}(\mathcal{F})\leq 2$,
for any cell $D$ of dimension one.

###### Proof.

Let $C_{1}$, $C_{2}$ be two open cell and $D$ be a cell of dimension one in
$\mathcal{A}_{2}$ satisfying

$C_{1}\geq D\leq C_{2}.$

Hence by monotonicity,

$E_{C_{1}}(\mathcal{F})\hookrightarrow E_{D}(\mathcal{F})\text{ and
}E_{C_{2}}(\mathcal{F})\hookrightarrow E_{D}(\mathcal{F}).$

Since $C_{1}$ and $C_{2}$ are opposed by $D_{1}$, by invertibility,

$\phi_{DC_{2}}\circ\phi_{C_{1}D}:E_{C_{1}}(\mathcal{F})\cong
E_{C_{2}}(\mathcal{F})$

is an isomorphism. Moreover $\phi_{C_{1}O}:E_{C_{1}}(\mathcal{F})\rightarrow
E_{O}(\mathcal{F})$ can be factorised by
$\phi_{C_{1}O}=\phi_{DO}\phi_{C_{1}D}$. Similarly
$\phi_{C_{2}O}=\phi_{DO}\phi_{C_{2}D}$. Moreover, for any open cells $C$ and
$C^{\prime}$, one necessarily has $E_{C}(\mathcal{F})\cong
E_{C^{\prime}}(\mathcal{F})$. Observe that any cell $D$ of dimension one can
be dominated by exactly two open cells. Therefore image of $\phi_{C_{1}D}$ and
image of $\phi_{C_{2}D}$ will generate a subspace of $E_{D}(\mathcal{F})$ of
dimension at most two. Since $\mathcal{F}$ is irreducible,
$\mathcal{Q}(\mathcal{F})$ is irreducible (Theorem 2.5). Hence image of
$\phi_{C_{2}D}$ and $\phi_{C_{2}D}$ would generate $E_{D}(\mathcal{F})$.

∎

######  Remark 3.10.

Since the classification of irreducible perverse sheaves of Coxeter
arrangement of type $\mathcal{A}_{2}$ was given by Rowley under the assumption
that $\operatorname{dim}(E_{D}(\mathcal{F})\leq 2$ for any cell $D$ of
dimension one in $\mathcal{A}_{2}$. Using the above corollary we obtain that
this classification is a complete classification of irreducible perverse
sheaves in $\mathcal{A}_{2}$.

### Acknowledgements

Both the authors are thankful to Harish-Chandra Research Institute. The second
author is also thankful to KSCSTE-Kerala School of Mathematics for their
support.

## References

  * [Bap21] Asilata Bapat.  Recollement for perverse sheaves on real hyperplane arrangements.  J. Algebra, 568:61–90, 2021.
  * [BBD82] A. A. Beĭlinson, J. Bernstein, and P. Deligne.  Faisceaux pervers.  In Analysis and topology on singular spaces, I (Luminy, 1981), volume 100 of Astérisque, pages 5–171. Soc. Math. France, Paris, 1982.
  * [KS16] Mikhail Kapranov and Vadim Schechtman.  Perverse sheaves over real hyperplane arrangements.  Ann. of Math. (2), 183(2):619–679, 2016.
  * [MV86] Robert MacPherson and Kari Vilonen.  Elementary construction of perverse sheaves.  Invent. Math., 84(2):403–435, 1986.
  * [PS00] Alexander Postnikov and Richard P. Stanley.  Deformations of Coxeter hyperplane arrangements.  volume 91, pages 544–597. 2000.  In memory of Gian-Carlo Rota.
  * [Row] Peter Rowley.  Perverse sheaves and quiver representations.  Preprint.