# PRIORITY-BASED POST-PROCESSING BIAS MITIGATION USING UNFAIRNESS QUOTIENT

###### Abstract

Previous post-processing bias mitigation algorithms on both group and
individual fairness don’t work on regression models and datasets with multi-
class numerical labels. We propose a priority-based post-processing bias
mitigation on both group and individual fairness with the notion that similar
individuals should get similar outcomes irrespective of socio-economic factors
and more the unfairness, more the injustice. We establish this proposition by
a case study on tariff allotment in a smart grid. Our novel framework
establishes it by using a user segmentation algorithm to capture the
consumption strategy better. This process ensures priority-based fair pricing
for group and individual facing the maximum injustice. It upholds the notion
of fair tariff allotment to the entire population taken into consideration
without modifying the in-built process for tariff calculation. We also
validate our method and show superior performance to previous work on a real-
world dataset in criminal sentencing.

Index Terms: Priority-based, Post-processing fairness, Group fairness,
Individual fairness, Unfairness Quotient

##  1 Introduction

Over the past few years, there has been a rapid development in the domain of
machine learning and its application. As a consequence of that, machine
learning systems are now being used as a tool to make high-stakes decisions,
which could affect an individual’s daily life. However, it has been observed
that these machine learning systems sometimes produce an outcome that is
unfair or discriminatory for minorities, historically disadvantaged
populations, and other groups. For example, in COMPAS [dressel2018accuracy],
the algorithm used for recidivism prediction produces a much higher false-
positive rate for black people than white people, therefore being
discriminatory for black people.

Bias creeps into the machine learning model because of many reasons. Skewed
training sample, sample size disparity, and proxies are a few of the many
reasons which lead the system to be unfair towards one group. In general, the
assumption of one size fits all policy lead to discrimination among groups.
There are two central notions of fairness in decision making: individual
fairness and group fairness [8682620]. While individual fairness, in a broader
sense, requires similar individuals should be treated similarly whereas group
fairness seeks for some statistical measure to be equal among group defined by
protected attributes (such as age, gender, race, and religion). Disparate
impact (DI) is a standard measure for group fairness.

Pre-processing, in-processing, and post-processing are three stages for
performing debiasing in the machine learning model. Pre-processing involves
transforming the feature space into another feature space which, as a whole,
is independent of the protected attribute. The in-training algorithm adds a
regularization term in the objective function of the model to achieve
independence from a protected attribute. While in the post-processing
algorithm, the goal is to edit the outcome to achieve fairness. Several works
have been done on price fairness in a smart grid. In
[maestre2018reinforcement], the author has used Q-Learning with neural network
approximation to assign the right price to the individual of different groups.
In [han2014impact], the author shows a strong correlation between the socio-
economic factor and the load consumption pattern. In this paper, we first
propose a tariff allotment policy. The electricity load forecasting task is a
time-series forecasting problem. SVR has been found to perform better for
time-series forecasting [muller1997predicting]. We use SVR to predict day-
ahead aggregated load for each of the consumers for the entire day. The reason
for day-ahead allocation being that it makes the consumer aware of the power
consumption. The power market prefers tariff slab or bucketing for pricing
[sarker2014smart]. For creating slabs, we use the Gaussian bucketing method to
bin the predicted value and assign respective tariff to individuals.

An application-independent priority-based post-processing debiasing algorithm
with the notion of both group and individual fairness is used to remove the
bias associated with the previous step that uses machine learning as an
architecture. In most real scenarios, we won’t have access to the internals of
models. Therefore it is evident that the post-processing debiasing algorithm
with the notion of both group and individual fairness suits the most
[8682620]. The trade-off between Bias and Accuracy [feldman2015certifying]
limits the number of individual samples allowed to be debiased. This brings
the requirement of individuals facing more unfairness to be debiased in
priority [berk2017convex]. Using this approach, we can achieve fairness faster
both in time and number of samples whose label needs to be changed to achieve
fairness. To the best of our knowledge, all existing post-processing
algorithms don’t work on priority-based debiasing [8682620, KamiranKZ2012,
HardtPS2016, PleissRWKW2017, CanettiCDRSS2018]. The starting point for our
proposed approach is the individual bias detector of [aggarwal2019black],
which finds samples whose model prediction changes when only protected
attributes change and calculate _Unfairness Quotient_ , which is used to
identify the priority order of the samples.

We have two major contributions to this work: First, an application-
independent priority-based post-processing debiasing algorithm that improves
both individual and group fairness. Second, a case study to showcase a fair
tariff allocation strategy which charges a similar price to an individual with
similar load characteristics irrespective of socio-economic factors.

Compared to the randomized debiasing method used in [8682620], we have
superior performance. We validate our proposition on a real-world dataset in
criminal sentencing [sentencing]. The remainder of the paper is organized as
follows. First, we provide details on the tariff allocation policy using
[ISSDA] in Sec.3. Next, we propose a priority-based post-processing debiasing
algorithm in Sec.4 with results on real-world datasets [ISSDA] [sentencing] in
Sec.5. We have showcased the comparison result with [8682620]. Finally, we
conclude the paper in Sec.6.

##  2 Fairness

Before proposing a priority-based post-processing debiasing algorithm, we
first introduce the working definitions of two important notions of fairness
i.e. group and individual fairness. Consider a supervised classification
problem with features $\mathbf{X}\in\mathcal{X}$, protected attributes
$\mathbf{P}\in\mathcal{P}$, and labels $\mathbf{C}\in\mathcal{C}$. We are
given a set of training samples
$\\{(x_{1},p_{1},c_{1}),\ldots,(x_{n},p_{n},c_{n})\\}$ and would like to learn
a classifier $\hat{C}:\mathcal{X}\times\mathcal{P}\rightarrow\mathcal{C}$. For
ease of explanation, we will only consider a scalar binary protected
attribute, i.e. $\mathcal{P}=\\{0,1\\}$, and a binary classification problem,
i.e. $\mathcal{C}=\\{0,1\\}$. The value $p=1$ is set to correspond to the
_privileged / majority_ group (e.g. male as in this application) and $p=0$ to
_unprivileged / minority_ group (e.g. female). The value $c=1$ is set to
correspond to a _favorable_ outcome (e.g. receiving a loan or not being
arrested) and $c=0$ to an _unfavorable_ outcome.

###  2.1 Group Fairness

###### Definition 1

We define group fairness in terms of disparate impact [feldman2015certifying]
as follows. There is disparate impact if

$\frac{\mathbb{E}[\hat{c}(\mathbf{X},P)\mid
P=0]}{\mathbb{E}[\hat{c}(\mathbf{X},P)\mid P=1]}$ (1)

is less than $1-\epsilon$ or greater than $(1-\epsilon)^{-1}$, where a common
value of $\epsilon$ is 0.1 or 0.2. In our method, the value of $\epsilon$ is
0.1.

In our designed scheme, group fairness implies that the prediction for an
individual across different groups should be almost equiprobable.

###  2.2 Individual Fairness

###### Definition 2

From the data, a given sample $i$ has individual bias if
$\hat{c}(x_{i},p=0)\neq\hat{c}(x_{i},p=1)$.

In our designed scheme, individual fairness confirms that similar individuals
should be treated similarly i.e. prediction allotted to a particular
individual should not be sensitive to the protected attributes of the
individual [8682620].

##  3 Case study: Tariff Allotment

###  3.1 Dataset and Learning process:

For the evaluation purpose, The CER ISSDA dataset [ISSDA] is used which was
obtained by the Irish Commission for Energy Regulation (CER) for the purpose
to analyze the impact on consumer’s electricity consumption. It contains half-
hourly load consumption data points of around 5000 Irish households and SMEs.
In addition to the load data, the dataset also includes some survey
questionnaire which describes the socio-economic condition of the consumer.
The inputs features are past load values, temperature, calendar details, and
socio-economic factors. Our day-ahead load forecasting algorithm uses Adaboost
regressor [scikit-learn] with the base learner as support vector regression
(SVR). Adaboost regressor is a meta-estimator that begins by fitting the base
estimator which in this case is SVR. We use Root mean squared error (RMSE)
calculation to evaluate the model (Adaboost+SVR) and found to be better
performing with a value of 8.3 against 10.54 in the base estimator case.

###  3.2 Allotment Policy:

We are proposing a day-ahead tariff allocation policy to assign a tariff band
or slab to the individual [sarker2014smart]. The role of tariff bands is that
all the individuals who are assigned to the same tariff band are charged the
same amount. To distinguish the consumer, we use the Gaussian bucketing
technique. The reason behind choosing this method to represent tariff bands
was that the probability distribution of the dataset is Gaussian in nature.
Assume the prediction from model be
${\hat{y}_{1},\hat{y}_{2},\dots,\hat{y}_{n}}$, we calculate the mean $\mu$ and
the standard deviation $\rho$ and assign all the individual same tariff whose
predicted value lies in $\left[\mu-i\rho,\mu-(i-1)\rho\right)\text{\ or \
}[\mu+i\rho,\mu+(i+1)\rho)\ \ \forall i\in\mathbb{Z}$. The algorithm 1 is used
to assign tariff band. The input to algorithm is predicted load ($\hat{y}$)
while output is tagged tariff band ($tid$). The time complexity of the
algorithm to assign tariff to each individual is $\mathcal{O}(n)$ where $n$ is
the number of individual in the system.

Algorithm 1 Tariff allotment policy

$\tau$ = $\\{\langle id_{1},\hat{y}_{1}\rangle,\langle
id_{2},\hat{y}_{2}\rangle,\dots,\langle id_{n},\hat{y}_{n}\rangle\\}\subset
ID\times\hat{Y}$

$\\{\langle id_{1},tid_{1}\rangle,\langle id_{2},tid_{2}\rangle,\dots,\langle
id_{n},tid_{n}\rangle\\}$

function AssignTariff($\tau$)

tariffAllotlist $\leftarrow\\{\ \\}$

$\mu$, $\rho$ = mean$(\tau)$, stdDev$\left(\tau\right)$ $\triangleright$ mean
and stdDev of $\hat{y}\in\tau$

for all $\langle id,\hat{y}\rangle\in\tau$ do

tariffAllotlist.append($\langle id,\frac{x-\mu}{\rho}\rangle$)

end for

leastTariff = min(tariffAllotlist) $\triangleright$ return min value of second
element of tuples

for all $\langle id,tid\rangle\in\tariffAllotlist$ do

tid $\leftarrow tid-leastTariff$ $\triangleright$ ensures assigned tariff are
non negative

end for

return tariffAllotlist

end function

##  4 Priority-based Post-processing Mitigation

The policy described in the previous section doesn’t take into account the
biased behavior of the model concerning the protected attributes known at run-
time i.e. impact of socio-economic factors. Before we start discussing
priority-based post-processing methodology for removing group and individual
biases concerning the protected attribute (age, race, and gender), one may
argue that the debiasing phase would not be required if during model training
we would have removed these sensitive attributes as features. However, this
method poses this weakness because the non-sensitive attribute can behave as a
proxy for the sensitive attribute that may not be visible at first
[kusner2017counterfactual]. Therefore a post-processing debiasing scheme is
proposed. Another advantage which post-processing debiasing process provides
is that it can be applied to any black-box model.

Bias and Accuracy always have a trade-off [feldman2015certifying]. Post-
processing individual bias mitigation may result in drop in accuracy. While
performing the debiasing process, we always have to consider a bandwidth of
accuracy loss allowed and thereby limiting the number of individuals allowed
to be debiased. Hence, we are using group discrimination metric (Disparate
Impact) as a threshold to limit the number of individual samples to be
debiased. We terminate the debiasing process once the fair threshold is
reached or it gets terminated by itself [8682620]. We define _Unfairness
Quotient_ as the difference between the actual model prediction and the
prediction after perturbing. It signifies the amount of unfairness associated.
Priority-based debiasing is needed to ensure priority-based justice to the
individual facing maximum unfairness. This allows individuals facing more bias
to be debiased in priority. This algorithm can be implemented on N-nary and
continuous-valued protected attributes (shown in Figure 1) since they can
always be categorized into privileged and unprivileged i.e. binary situation.

###  4.1 Individual Bias detection and Unfairness Scoring

Consider the model $\hat{c}$ which comprises prediction followed by bucketing.
To determine whether the sample $(x_{i},d_{i})$, where $d_{i}$ is the
sensitive attributes and $x_{i}$ are the non-sensitive attributes, has
individual bias associated with it, we perturb the sensitive attribute $d_{i}$
to $\check{d_{i}}$. If $\hat{c}(x_{i},d_{i})$ is different from
$\hat{c}(x_{i},\check{d_{i}})$, we add this sample to individual biased sample
collection.

###### Definition 3

For each sample $(x_{i},d_{i})$, we calculate Unfairness Quotient
$b_{x_{i},d_{i}}$. Formally, Unfairness Quotient is defined as the difference
between the actual model prediction and the prediction after perturbing.i.e

$\displaystyle
b_{x_{i},d_{i}}=abs(\hat{c}(x_{i},\check{d_{i}})-\hat{c}(x_{i},d_{i}))$ (2)

The _Unfairness Quotient_ signifies the amount of bias associated with that
sample, i.e. more the value, more the injustice and hence higher the priority
during debiasing.

###  4.2 Overall Algorithm

The priority-based bias mitigation algorithm is applied after the model
prediction and band allotment for each sample. For each sample, in the
decreasing order of _Unfairness Quotient_ , we update the value of
$\hat{c}(x_{i},d_{i})$ to $\hat{c}(x_{i},\check{d_{i}})$ until the value of DI
is less than $1-\epsilon$. The proposed algorithm is summarized in Algorithm
2.

Algorithm 2 Priority-based post-processing bias mitigation algorithm

Given model $\hat{c}$ trained on training set
$\\{(\mathbf{x}_{i},d_{i},y_{i})\\}$ where ($d_{i}$ is sensitive attribute and
Test Sample $(\mathbf{X},\mathbf{D})$.)

minority = 0

$di=\frac{\mathbb{E}[\hat{c}(\mathbf{X},\mathbf{D})\mid
d=minority]}{\mathbb{E}[\hat{c}(\mathbf{X},d)\mid d=1\oplus minority]}$

if di $>$ 1 then

minority = 1

di = $\frac{1}{di}$

end if

for all run-time test samples $(\mathbf{x}_{k},d_{k})$ do

$b_{\mathbf{x}_{k},d_{k}}=$
abs($\hat{c}(\mathbf{x}_{i},d_{i}=0)-\hat{c}(\mathbf{x}_{i},d_{i}=1)$)
$\triangleright$ compute Unfairness Quotient

end for

Sort test-sample $(\mathbf{X},\mathbf{D})$ on the basis of
$b_{\mathbf{x}_{k},d_{k}}$ in decreasing order

for all ($\mathbf{x}_{k},d_{k})\in test-sample$ $(\mathbf{X},\mathbf{D})$ do

if $b_{\mathbf{x}_{k},d_{k}}>0\ \&\ d_{k}=minority$ then

$\hat{c}(\mathbf{x}_{k},d_{k})=\hat{c}(\mathbf{x}_{k},d_{k}=1\oplus minority)$

$di=\frac{\mathbb{E}[\hat{c}(\mathbf{X},\mathbf{D})\mid
d=minority]}{\mathbb{E}[\hat{c}(\mathbf{X},d)\mid d=1\oplus minority]}$

if di ≥$1-\epsilon$ then

break

end if

end if

end for

##  5 Empirical Results

We evaluated our proposed algorithm on the subset of the CER ISSDA dataset
described in subsection 3.1 for Jan 2010. We started by training an Adaboost +
SVR model on the first 20 days sample to predict the power consumption by the
individual followed by the Gaussian bucketing for tariff band allocation. We
empirically verified the distribution between average power consumption and
the number of individuals and found it to be Gaussian with mean 32.24 and
variance 94.67. The training samples contain two protected attributes i.e.
_Gender_ and _Age_ concerning which model can have group as well as individual
unfairness. Since our proposed priority-based post-processing algorithm is
application-independent, we verified the effectiveness of the algorithm on the
tariff allotment model. The notion of fairness requires the definitions of
group, i.e. privileged and unprivileged and output class labels, i.e.
favorable and unfavorable. For the _Gender_ attribute, the group comprises
Male and Female, and for the _Age_ attribute, we define the group as young i.e
with Age $\leq$ 45 and old i.e Age $>$ 45\. We used the percentage strategy
and chose lower 40% as favorable and upper 60% as unfavorable which makes
sense i.e. one is in a favorable zone if he/she is paying less than average.
Figure 1 showcases the result of priority-based algorithm for protected
attribute _Age_.

Figure 1: Variation of Disparate Impact value, with the protected attribute as
Age in the Tariff dataset, as the class label of individual samples is changed
(the individual samples are debiased) priority-based. The debiasing process
stops once the purple threshold line of 0.9 is reached.

###  5.1 Comparison with the baseline approach

We compared our priority-based debiasing approach with the baseline method in
[8682620]. In our case, daily in the post-processing stage, the model assigns
tariff to each individual. We start by calculating the initial Disparate
Impact which is a measure of group fairness discussed in Section 2.1 and if it
comes out to be less than 0.9 we uplift its value towards 0.9, if achievable
by debiasing the sample with individual bias. Due to the efficiency in
selecting the individual bias point i.e in decreasing order of _Unfairness
Quotient_ rather than randomly in [8682620], we found out that our approach
takes less time as well as a lesser number of class label changes takes place
compared to the existing algorithm. Due to the fewer number of changes in
class label, our algorithm kind of reduces the inescapable bias-accuracy
trade-off. Figure 2 shows the comparison plot for both the algorithm with the
protected attribute as _Gender_.

Figure 2: Variation of Disparate Impact value, with the protected attribute as
Gender in the Tariff dataset for multiple dates, as the class label of
individual samples is changed (the individual samples are debiased). The
orange line shows the variation according to the priority-based algorithm. The
blue line shows the variation according to the baseline-randomized approach.
The number of samples whose labels need to change to achieve fairness is less
in our priority-based approach. The debiasing process stops once the purple
threshold line of 0.9 is reached. Figure 3: Time taken by the proposed and the
baseline approach in the Tariff dataset with the protected attribute as Gender
over multiple dates. From all the bar plots, time taken is priority-based
approach is lesser.

###  5.2 Validation of the proposed algorithm

We extended our analysis to see how our algorithm performs on other publicly
available datasets with multi-class numerical labels. For the validation
purpose, we run the algorithm on Sentencing dataset [sentencing], which has
_Gender_ as a protected attribute. On studying the dataset, we found out the
charge imposed on Male was much higher than Female leading to some unfairness
towards Male. Using our proposed algorithm, we were able to remove this
unfairness by changing 784 class labels as compared to the 1163 class labels
in the case of baseline. Also, the time taken by the debiasing process using
the priority-based approach was 125s whereas using the baseline randomized
approach was 190s on average. Figure 4 showcases this analysis.

Figure 4: Variation of Disparate Impact value, with the protected attribute as
Gender in the Sentencing dataset, as the class label of individual samples is
changed (the individual samples are debiased). The orange line shows the
variation according to the priority-based algorithm. The blue line shows the
variation according to the baseline-randomized approach. The number of samples
whose labels need to change to achieve fairness is less in our priority-based
approach.

##  6 Conclusion

Algorithmic fairness has become a compulsory step to be taken into
consideration when building and deploying machine learning models. Bias-
mitigation algorithms that address the critical and important notion of
fairness are important. Accuracy and Bias are always in a trade-off. This
creates a limit on the number of individual samples to be debiased withholding
the accuracy. In this constraint individual debiasing process, past
randomization-based debiasing approach fails to give a validity on whether
individual samples facing maximum unfairness have been taken into
consideration for debiasing or not. In this paper, we have developed a novel
priority-based post-processing algorithm that ensures priority-based fairness
to the individual facing maximum unfairness. The remediation process work to
improve both individual and group fairness metrics. In this shifting paradigms
in the model development process, there is limited accessibility for deployers
to the internals of trained models. Therefore, post-processing algorithms that
treat models as complete black-box are necessary. In comparison to previous
work, our algorithm is faster and needs changing labels of a lesser number of
samples to achieve fairness. We have validated our method on multiple real-
world datasets.


# Permutation-Like Matrices

Steven R. Lippold  Department of Mathematics, Taylor University, Upland, IN
46989<EMAIL_ADDRESS>
###### Abstract.

Permutation Matrices are a well known class of matrices which encode the
elements of the symmetric group on $d$ elements as a square $d\times d$
matrix. Motivated by [4], we define a similar class of matrices which are a
generalization of Permutation Matrices. We give explicit formulas for the
multiplication of these matrices. Lastly, we discuss the spectral radius,
eigenvalues, and periodicity before giving a form of Birkhoff-Von Neumann’s
Theorem for Left Stochastic Matrices.

###### Key words and phrases:

binary matrices, permutation matrices, Birkhoff-Von Neumann’s Theorem,
eigenvalues, matrix multiplication

###### 2020 Mathematics Subject Classification:

Primary 15B51, Secondary 15A18, 52B11

##  1\. Introduction

One well known class of matrices is that of the Permutation Matrices (see for
example [3]). The Permutation Matrices are matrices with one 1 in each row and
column and zeroes elsewhere. These matrices are useful for a variety of
reasons. For one, they encode row and column permutation as left and right
multiplication, respectively. In addition, there exists a group isomorphism
between $d\times d$ Permutation Matrices under matrix multiplication and
$S_{d}$, the symmetric group on $d$ letters. Lastly, there are a variety of
algorithms that utilize Permutation Matrices and every Doubly Stochastic
Matrix can be written as a convex combination of Permutation Matrices.

[4] discussed an identification of edge $d$-partitions of the complete graph
on $2d$ verices $K_{2d}$ with $d\times d(2d-1)$ matrices. In particular, there
exists a matrix multiplication on $d\times d(2d-1)$ matrices that involves
splitting up each of the $d\times d(2d-1)$ matrices as an ordered collection
of $2d-1$ square $d\times d$ matrices, which can then be multiplied and
reconstructed as a new $d\times d(2d-1)$ matrix. In the case of edge
$d$-partitions of $K_{2d}$, these smaller $d\times d$ matrices were similar to
Permutation Matrices in that there was precisely one 1 in each column, with
the rest of the entries zero. However, unlike Permutation Matrices, there
could be more than one 1 in a given row. As such, in this paper we look to
examine such matrices closer, starting with characterizing the matrix
multiplication.

We would like to briefly explain the structure of the paper. In Section 2, we
introduce Permutation-Like Matrices, which form a monoid. Then, we recall the
symmetric group actions of row and column permutations which is useful for
this paper.

In Section 3, we classify multiplication for Permutation-Like Matrices. First,
we consider the case of $2\times 2$ Permutation-Like Matrices, of which there
are 3 non-identity matrices. Then, we consider the case of $3\times 3$
Permutation-Like Matrices. In doing this, we give definitions for certain
classes of these matrices, simplifying the possible cases. Lastly, we consider
the case of $d\times d$ Permutation-Like Matrices, with our approach modelled
on the case of $3\times 3$ Permutation-Like Matrices.

In Section 4, we consider several properties of Permutation-Like Matrices.
First, we show that in the case $d=2$ and $d=3$, we have that all Permutation-
Like Matrices are periodic or satisfy $A^{2}=R_{m}^{(d)}$, where $R_{m}^{(d)}$
is a special class of Permutation-Like Matrices. Then, we give an explicit
description of the eigenvalues in the case $d=2$ and $d=3$ before we compute
the spectral radius of all $d\times d$ Permutation-Like Matrices for $d\geq
2$. Lastly, we show that every Left Stochastic Matrix can be written as a
convex combination of Permutation-Like Matrices, which gives a form of the
classical Birkhoff-Von Neumann’s Theorem for Left Stochastic Matrices. In
Section 5, we have some remarks and open questions regarding the material
covered in this paper.

##  2\. Permutation-Like Matrices

Throughout this paper, let $d\geq 1$ and $k$ to be a field. We assume that all
matrices have coefficients in $k$. For a given $d\times d$ matrix $A$, let
$a_{i,j}$ denote the entry in the $i^{th}$ row and $j^{th}$ column of $A$.

###  2.1. Permutation-Like Matrices

We will start by define a type of matrix, which previously appeared in [4].

######  Definition 2.1.

Let $A$ be a $d\times d$ matrix such that $a_{i,j}=0$ or $1$ for all $1\leq
i,j\leq d$ and, for each $1\leq j\leq d$, there exists a unique $1\leq i\leq
d$ such that $a_{i,j}=1$.

Then, we call $A$ a Permutation-Like Matrix (PLM). We take $PL_{d}$ to be the
collection of $d\times d$ PLM.

######  Remark 2.2.

Notice that the leg submatrices of the $d\times d(2d-1)$ matrix associated
with an edge $d$-partition of $K_{2d}$ from [4] are all PLM.

######  Remark 2.3.

PLM are called Permutation-Like Matrices because they are share some of the
properties of Permutation Matrices but not all of them (every Permutation
Matrix is a PLM). One example of a property that holds for Permutation
Matrices but not PLM is the sum of each row. Indeed, the sum of the entries in
each row of a Permutation Matrix is 1, which is not true for every PLM. For
example, the matrix $\begin{pmatrix}1&1\\\ 0&0\end{pmatrix}$ is a PLM, but not
a Permutation Matrix. In this sense, PLM are a generalization of Permutation
Matrices.

######  Remark 2.4.

Notice that every PLM is a Left Stochastic Matrix. This will be further
explored in a later section.

######  Remark 2.5.

The Stochastic Group of [5] differs from $PL_{d}$ since the elements of
$PL_{d}$ are not necessarily invertible. It will become evident in a later
section that the only PLM that are in the Stochastic Group are the Permutation
Matrices.

In further studying $PL_{d}$, it would be helpful to have some notion of the
structure of $PL_{d}$, which is given by the following proposition.

######  Proposition 2.1.

$PL_{d}$ is a closed under matrix multiplication.

###### Proof.

Let $A,B\in PL_{d}$ for $d\geq 1$ and let $C=A\cdot B$. Then,

$c_{i,j}=\sum_{p=1}^{d}a_{i,p}b_{p,j}.$

However, since $B$ is a PLM, there exists a unique $p_{j}$ such that
$b_{p_{j},j}=1$ and $b_{i,j}=0$ for all $i\neq p_{j}$. Thus,
$c_{i,j}=a_{i,p_{j}}$.

Now, since $A$ is a PLM, we further know that given $1\leq j\leq d$, there
exists a unique $1\leq i\leq d$ such that $a_{i,j}=1$. In particular, for each
$1\leq j\leq d$, there exists a unique $1\leq i\leq d$ such that
$a_{i,p_{j}}=1$. Thus, for each $1\leq j\leq d$, there exists a unique $1\leq
i\leq d$ such that $c_{i,j}=a_{i,p_{j}}=1$. Hence, $C$ is a PLM. ∎

######  Remark 2.6.

There are non-invertible PLM, so $PL_{d}$ is not a subgroup of the General
Linear Group. We will discuss more on the invertibility of PLM in a later
section. However, it is important to note that there is an identity PLM (the
identity matrix) and so $PL_{d}$ is a monoid.

###  2.2. Symmetric Group Action on Permutation-Like Matrices

Before we focus on $PL_{d}$, there are two (left) group actions we would like
to focus on, which will simplify some later proofs.

Let $S_{d}$ be the symmetric group on $d$ letters. There are two group actions
on $m\times n$ matrices, one by $S_{m}$ and one by $S_{n}$.

Let $A$ be a $m\times n$ matrix. For $\sigma\in S_{m}$, we define $\sigma\ast
A$ to be the matrix given by permuting the rows of $A$ with $\sigma$. Second,
for $\tau\in S_{n}$, we define $\tau\star A$ to be the matrix given by
permuting the columns of $A$ by $\tau^{-1}$. This definition leads to the
following lemma.

######  Lemma 2.7.

Let $A$ be a $m\times n$ matrix, $B$ be a $n\times p$ matrix, $\sigma\in
S_{m}$ and $\tau\in S_{p}$. Then,

  1. (1)

$\sigma\ast(A\cdot B)=(\sigma\ast A)\cdot B$.

  2. (2)

$\tau\star(A\cdot B)=A\cdot(\tau\star B)$.

Notice that Lemma 2.7 immediately follows from basic linear algebra (see [3]
for example) with the identification of $S_{d}$ with Permutation Matrices. In
particular, row permutation is given by left multiplication of some
Permutation Matrix and column permutation is given by right multiplication of
some Permutation Matrix. These group actions will be important moving forward
and Lemma 2.7 will be implicitly used.

##  3\. Multiplication of Permutation-Like Matrices

In this section, we give explicit computations for multiplication of PLMs. We
will cover these computations using the cases of $d=2$, $d=3$, and $d>3$.

###  3.1. The Case $d=2$

Suppose that $d=2$ and consider $PL_{2}$. We would like to give multiplication
of all of these matrices. Besides the identity matrix $I$, there are three
other PLM.

  1. (1)

$R_{1}^{(2)}=\displaystyle\begin{pmatrix}1&1\\\ 0&0\end{pmatrix}$

  2. (2)

$R_{2}^{(2)}=\displaystyle\begin{pmatrix}0&0\\\ 1&1\end{pmatrix}$

  3. (3)

$P_{2}=\displaystyle\begin{pmatrix}0&1\\\ 1&0\end{pmatrix}$.

######  Remark 3.1.

We will examine the multiplication closer, but $P_{2}$ is the matrix whose
left multiplication is identified with matrix transposition.

First, we present the following proposition.

######  Proposition 3.1.

Let $m=1$ or $m=2$ and $A\in PL_{2}$. Then, $R_{m}^{(2)}\cdot A=R_{m}^{(2)}$.

###### Proof.

This proof follows by direct computation, but we give an alternative proof
that is illustrative for later sections.

Let $B=R_{m}^{(2)}\cdot A$. Notice that

$b_{i,j}=r_{i,1}b_{1,j}+r_{i,2}b_{2,j}.$

However, if $i\neq m$, we know that $r_{i,p}=0$ for $p=1$ and $p=2$. Thus,
$b_{i,j}=0$ for all $i\neq m$. Further, we know that there is at least one 1
in each column, so $b_{m,j}=1$ for $j=1$ and $j=2$. Thus,

$b_{i,j}=\begin{cases}0&\quad i\neq m\\\ 1&\quad i=m\end{cases}$

and hence $B=R_{m}^{(2)}$. ∎

Next, we cover the remaining case, which fully classifies multiplication in
the case $d=2$.

######  Proposition 3.2.

Let $d=2$. Then,

  1. (1)

$P_{2}\cdot R_{1}^{(2)}=R_{2}^{(2)}$.

  2. (2)

$P_{2}\cdot R_{2}^{(2)}=R_{1}^{(2)}$.

  3. (3)

$P_{2}\cdot P_{2}=I$.

Notice that the proof for Proposition 3.2 follows computationally.

###  3.2. The Case $d=3$

Next, we will consider the case of $d=3$. First, notice that in $PL_{3}$ there
are 27 matrices, with one of them being the identity matrix. We start with a
special class of PLM called the row PLMs.

######  Definition 3.2.

For $1\leq m\leq 3$, let $R_{m}^{(3)}$ be the matrix where $r_{i,j}=0$ if
$i\neq m$ and $r_{i,j}=1$ if $i=m$ for all $1\leq j\leq d$. We call
$R_{m}^{(3)}$ the Row Permutation-Like Matrices (row PLM).

We would like to consider $A\cdot B$, where $A,B$ are PLM. We will start with
the case where $A$ is a row PLM.

######  Proposition 3.3.

Take $1\leq m\leq 3$ and $A\in PL_{3}$. Then, $R_{m}^{(3)}\cdot
A=R_{m}^{(3)}$.

###### Proof.

This proof follows similarly to Proposition 3.1.

Let $B=R_{m}^{(3)}\cdot A$. Notice that

$b_{i,j}=r_{i,1}b_{1,j}+r_{i,2}b_{2,j}+r_{i,3}b_{3,j}.$

However, if $i\neq m$, we know that $r_{i,p}=0$ for $1\leq p\leq 3$. Thus,
$b_{i,j}=0$ for all $i\neq m$. Further, we know that there is at least one 1
in each column, so $b_{m,j}=1$ for $1\leq j\leq 3$. Thus,

$b_{i,j}=\begin{cases}0&\quad i\neq m\\\ 1&\quad i=m\end{cases}$

and hence $B=R_{m}^{(3)}$. ∎

Next, we will consider the case of $A\cdot B$ where $B$ is a row PLM.

######  Proposition 3.4.

Let $A$ be a PLM and let $1\leq m\leq 3$. Then,

$A\cdot R_{m}^{(3)}=\begin{pmatrix}a_{1,m}&a_{1,m}&a_{i,m}\\\
a_{2,m}&a_{2,m}&a_{2,m}\\\ a_{3,m}&a_{3,m}&a_{3,m}\end{pmatrix}$

###### Proof.

Let $B=A\cdot R_{m}^{(3)}$. Recall that

$r_{i,j}=\begin{cases}1,&\ \ i=m\\\ 0,&\ \ \textrm{otherwise}\end{cases}$

Therefore,

$b_{i,j}=a_{i,1}r_{1,j}+a_{i,2}r_{2,j}+a_{i,3}r_{3,j}=a_{i,m}r_{m,j}=a_{i,m}.$

∎

We have exhausted the cases of $A\cdot B$, where either $A$ or $B$ is a row
PLM. Next, we would like to consider several other cases, which all focus on a
different type of PLM.

######  Definition 3.3.

We say that $A\in PL_{3}$ is a canonical Permutation-Like Matrix (CPLM) if it
is a block matrix of the form

$A=\begin{pmatrix}\boxed{a_{1,1}}&\boxed{0\ 0}\\\
\boxed{v}&\boxed{A_{1}}\end{pmatrix}$

where $v\in k^{2}$ and $A_{1}\in PL_{2}$. We will call $A_{1}$ the
Permutation-Like Component (PLC) of $A$. If $a_{1,1}=1$, we say that $A$ is a
leading CPLM.

With this definition, we have the following lemma, which will simplify the
number of cases.

######  Lemma 3.4.

Let $A\in PL_{3}$. Then, there exists $\sigma\in S_{3}$ and CPLM $B$ such that
$\sigma\ast A=B$. In other words, any PLM is a CPLM up to swapping rows.

###### Proof.

First, if $A$ is a row PLM, then $A$ is either a CPLM with a leading element
of zero or $(1,2)\ast A$ is a CPLM with a leading element of zero. Indeed,
$R_{m}^{(3)}$ is a CPLM for $m>1$ with PLC given by $R_{m-1}^{(2)}$. Further,
in the case of $R_{1}^{(3)}$, it follows that $(1,2)\ast
R_{1}^{(3)}=R_{2}^{(3)}$. Next, suppose $A$ is not a row PLM.

If we consider the $d\times d-1$ matrix $\tilde{A}$ given by
$\tilde{a}_{i,j}=a_{i,j+1}$ for $1\leq i\leq d$ and $1\leq j\leq d-1$, we have
that at least one row will be all zeros, as there is at most 1 nonzero entry
in each column. Let $r^{\prime}$ be the row of $\tilde{A}$ with all zeros and
take $\sigma=(1,r^{\prime})\in S_{d}$. So, $B=\sigma\ast A$ is the matrix
given by $A$ with rows $1$ and $r^{\prime}$ swapped. Notice that the only
column that could have a nonzero element in the first row of $B$ is the first
column by the construction of $r^{\prime}$. Thus, $A$ is a CPLM with PLC given
by $\sigma\ast\tilde{A}$ with the first row removed. ∎

With Lemma 3.4 in mind, we will be able to reduce our cases down to $A\cdot B$
where $A$ is a CPLM and $B$ is a PLM. First, we will consider the cases where
$B$ is also a CPLM. We will start with the case where $B$ is not a leading
CPLM.

######  Proposition 3.5.

Let $A,B$ be CPLM with PLC $A_{1}$ and $B_{1}$, respectively. Suppose that
$b_{x,1}=1$ for $x>1$. Then, $A\cdot B$ is given by the block matrix

$A\cdot B=\begin{pmatrix}0&\begin{matrix}0&0\end{matrix}\\\
\begin{matrix}a_{2,x}\\\ a_{3,x}\end{matrix}&A_{1}\cdot B_{1}\end{pmatrix}.$

###### Proof.

First, let $A\cdot B=C$ and take the $i^{th}$ row and $j^{th}$ column of $A$,
$B$ and $C$ to be denoted by $a_{i,j}$, $b_{i,j}$ and $c_{i,j}$, respectively.
We will compute $c_{i,j}$ for all $1\leq i,j\leq 3$.

Since $A$ is a CPLM, we know that $a_{1,2}=0$ and $a_{1,3}=0$. In particular,
we know that

$c_{1,j}=a_{1,1}b_{1,j}+a_{1,2}b_{2,j}+a_{1,3}b_{3,j}=a_{1,1}b_{1,j}$

for all $1\leq j\leq 3$. However, notice that since $B$ is a CPLM so
$b_{1,j}=0$ for $j>1$. Further, $b_{x,1}=1$ for some $x>1$, so we know that
$b_{1,1}=0$, as there is at most one 1 in each column. Thus, $c_{1,j}=0$ for
all $1\leq j\leq 3$.

Next, consider $c_{i,1}$ for $i=2$ and $i=3$. We know that $a_{1,3}=0$,
$b_{x,1}=1$, and $b_{i,1}=0$ for $i\neq x$. Therefore,

$c_{i,1}=a_{i,1}b_{1,1}+a_{i,2}b_{2,1}+a_{i,3}b_{3,1}=a_{i,x}b_{x,1}=a_{i,x}.$

In particular, $c_{2,1}=a_{2,x}$ and $c_{3,1}=a_{3,x}$.

Lastly, since $a_{2,1}=a_{3,1}=0$, it follows for $2\leq i,j\leq 3$ that

$c_{i,j}=a_{i,1}b_{1,j}+a_{i,2}b_{2,j}+a_{i,3}b_{3,j}=a_{i,2}b_{2,j}+a_{i,3}b_{3,j}.$

Notice that $\begin{pmatrix}c_{2,2}&c_{2,3}\\\ c_{3,2}&c_{3,3}\end{pmatrix}$
is precisely $A_{1}\cdot B_{1}$ since

$A_{1}=\begin{pmatrix}a_{2,2}&a_{2,3}\\\ a_{3,2}&a_{3,3}\end{pmatrix}$

and

$B_{1}=\begin{pmatrix}b_{2,2}&b_{2,3}\\\ b_{3,2}&b_{3,3}\end{pmatrix}.$

Therefore, $C$ is of the form $\begin{pmatrix}0&0\ 0\\\
\begin{matrix}a_{2,x}\\\ a_{3,x}\end{matrix}&A_{1}\cdot B_{1}\end{pmatrix}.$ ∎

Next, we consider the case where $B$ is a leading PLM.

######  Proposition 3.6.

Let $A,B$ be CPLM with PLC $A_{1}$ and $B_{1}$, respectively. If $B$ is a
leading CPLM, then $C=A\cdot B$ is a CPLM with PLC $A_{1}\cdot B_{1}$.
Further, $c_{i,1}=a_{i,1}$ for all $1\leq i\leq 3$.

###### Proof.

First, notice that since $B$ is a leading CPLM, we know that $b_{1,1}=1$ and
$b_{2,1}=b_{3,1}=0$.

Next, let’s compute the first column of $C$. Since $b_{1,1}=1$ and
$b_{2,1}=b_{3,1}=0$, we know

$c_{1,1}=a_{1,1}b_{1,1}+a_{1,2}b_{2,1}+a_{1,3}b_{3,1}=a_{1,1},$
$c_{2,1}=a_{2,1}b_{1,1}+a_{2,2}b_{2,1}+a_{1,3}b_{3,1}=a_{2,1},$

and

$c_{3,1}=a_{3,1}b_{1,1}+a_{3,2}b_{2,1}+a_{3,3}b_{3,1}=a_{3,1}.$

In particular, we have that for all $1\leq i\leq 3$ that $c_{i,1}=a_{i,1}$.

Next, consider the other entries in the first row of $C$. This is given by

$c_{1,2}=a_{1,1}b_{1,2}+a_{1,2}b_{2,2}+a_{1,3}b_{3,2}=0$

and

$c_{1,3}=a_{1,1}b_{1,3}+a_{1,2}b_{2,3}+a_{1,3}b_{3,3}=0$

since $a_{1,2}=a_{1,3}=b_{1,2}=b_{1,3}=0$.

Lastly, consider $c_{i,j}$ for $2\leq i,j\leq 3$. Since $b_{1,j}=0$ for $2\leq
j\leq 3$, it follows that

$c_{i,j}=a_{i,1}b_{1,j}+a_{i,2}b_{2,j}+a_{i,3}b_{3,j}=a_{i,2}b_{2,j}+a_{i,3}b_{3,j}.$

Further, notice that

$A_{1}=\begin{pmatrix}a_{2,2}&a_{2,3}\\\ a_{3,2}&a_{3,3}\end{pmatrix}$

and

$B_{1}=\begin{pmatrix}b_{2,2}&b_{2,3}\\\ b_{3,2}&b_{3,3}\end{pmatrix}$

so the entries making up the block $c_{i,j}$ where $2\leq i,j\leq 3$ give
$A_{1}\cdot B_{1}$ precisely. Therefore, $C$ is a PLM with PLC $A_{1}\cdot
B_{1}$. ∎

Note Propositions 3.5 and 3.6 completely determine multiplication of two CPLM
matrices. In particular, we have the following immediate corollary.

######  Corollary 3.5.

$3\times 3$ Canonical Permutation-Like Matrices are closed under matrix
multiplication.

Before we consider some other cases of matrix multiplication, we want to give
the following special case that follows as a corollary to Proposition 3.5.

######  Corollary 3.6.

Let $A,B$ be CPLM with PLC $A_{1}$ and $B_{1}$, respectively. Further, suppose
that $A_{1}=R_{m}^{(2)}$ for $1\leq m\leq 2$ and that $B$ is not a leading
CPLM. Then, $A\cdot B=R_{m+1}^{(3)}$.

######  Remark 3.7.

Notice as a result of Corollary 3.6 that if $A$ is a CPLM with leading element
zero and PLC $R_{m}^{(2)}$, then $A^{2}=R_{m+1}^{(3)}$. This computation will
be helpful for approaching the problem of periodicity in Section 4.

Next, we want to consider some other cases of matrix multiplication. We start
with a definition.

######  Definition 3.8.

We say that $A\in PL_{3}$ is a pre-canonical Permutation-Like Matrix (PCPLM)
if there exists a column permutation $\tau\in S_{3}$ such that $\tau\star A$
is a CPLM.

######  Remark 3.9.

Notice that every PLM with zero 1s or only one 1 in the first row is either a
CPLM or a PCPLM.

Now, the following comes immediately from the definition with Lemma 2.7.

######  Proposition 3.7.

Let $A,B\in PL_{3}$ such that $A$ is a CPLM and $B$ is a PCPLM such that
$\tau\star B$ is a CPLM for some $\tau\in S_{d}$. Then,

$A\cdot B=\tau^{-1}\star(A\cdot(\tau\star B))$

In particular, using Propositions 3.5 and 3.6, we have explicit formulas that
arise from Proposition 3.7.

The last class of PLM we will focus on is related to when we are not able to
get a PLM in the form of a CPLM.

######  Definition 3.10.

We say that $A\in PL_{3}$ is an irregular Permutation-Like Matrix (IPLM) if it
is not a CPLM, PCPLM, or row PLM.

This definition leads into the following proposition.

######  Proposition 3.8.

Let $A,B\in PL_{3}$ such that $A$ is a CPLM with PLC $A_{1}$ and $B$ is an
IPLM. Then, we have the following cases for their multiplication:

  1. (1)

$\displaystyle\begin{pmatrix}a_{1,1}&0&0\\\ a_{2,1}&a_{2,2}&a_{2,3}\\\
a_{3,1}&a_{3,2}&a_{3,3}\end{pmatrix}\cdot\begin{pmatrix}1&1&0\\\ 0&0&b\\\
0&0&c\end{pmatrix}=\begin{pmatrix}1&1&0\\\ 0&0&a_{2,2}b+a_{2,3}c\\\
0&0&a_{3,2}b+a_{3,3}c\end{pmatrix}$

  2. (2)

$\displaystyle\begin{pmatrix}a_{1,1}&0&0\\\ a_{2,1}&a_{2,2}&a_{2,3}\\\
a_{3,1}&a_{3,2}&a_{3,3}\end{pmatrix}\cdot\begin{pmatrix}1&0&1\\\ 0&b&0\\\
0&c&0\end{pmatrix}=\begin{pmatrix}1&0&1\\\ 0&a_{2,2}b+a_{2,3}c&0\\\
0&a_{3,2}b+a_{3,3}c&0\end{pmatrix}$

  3. (3)

$\displaystyle\begin{pmatrix}a_{1,1}&0&0\\\ a_{2,1}&a_{2,2}&a_{2,3}\\\
a_{3,1}&a_{3,2}&a_{3,3}\end{pmatrix}\cdot\begin{pmatrix}0&1&1\\\ b&0&0\\\
c&0&0\end{pmatrix}=\begin{pmatrix}0&1&1\\\ a_{2,2}b+a_{2,3}c&0&0\\\
a_{3,2}b+a_{3,3}c&0&0\end{pmatrix}$

###### Proof.

Let $B$ be an IPLM. If there are three 1s in the first row, it is
$R_{1}^{(3)}$ (and hence not a IPLM). So, $B$ has zero, one, or two 1s in the
first row.

If $B$ has zero 1s in the first row, then it is of the form

$\begin{pmatrix}0&0&0\\\ \ast&\ast&\ast\\\ \ast&\ast&\ast\end{pmatrix}$

Since there is exactly one 1 in each column, that means that the 1 for the
second and third column appears in the second or third row. This means that we
have

$\begin{pmatrix}0&\begin{matrix}0&0\end{matrix}\\\ \begin{matrix}\ast\\\
\ast\end{matrix}&B_{1}\end{pmatrix}$

where $B_{1}\in PL_{2}$. Therefore, $B$ would have to be a CPLM (which
contradicts that it is an IPLM).

Similarly, we can suppose that $B$ has one 1 in the first row, so up to column
permutation it is of the form

$\begin{pmatrix}1&0&0\\\ 0&\ast&\ast\\\ 0&\ast&\ast\end{pmatrix}$

so we know there are two 0s and two 1s the fill in the remaining positions
(one of each in each column) and hence $B$, up to column permutation, is a
CPLM (i.e. $B$ is a CPLM or PCPLM, which contradicts that it is an IPLM).
Therefore, if $B$ is an IPLM, there is exactly two 1s in the first row. These
are covered in the three cases.

Given this, case 1 results by direct computation and cases 2 and 3 result from
a column permutation of case 1. ∎

Lastly, the claim is that we have covered all of the possible cases.

######  Theorem 3.11.

Let $A,B\in PL_{3}$. Then, $A\cdot B$ is given, up to row permutation, by
Propositions 3.3-3.8.

###### Proof.

Notice that if $A$ is not a row PLM (a case covered by Proposition 3.3), we
can assume that $A$ is a CPLM without loss of generality by Lemma 3.4. By the
definition of IPLM, we know that every PLM is a row PLM, CPLM, PCPLM, or IPLM.
All of these cases are covered by Propositions 3.4-3.8. ∎

###  3.3. The Case $d>3$

Next, we will consider the case $d>3$. This section will follow in parallel
with the case $d=3$.

######  Definition 3.12.

Let $R_{m}^{(d)}$ be the $d\times d$ matrix with entry $r_{i,j}$ in row $i$
and column $j$, where $r_{i,j}=1$ if $i=m$ and $r_{i,j}=0$ otherwise. We call
$R^{(d)}_{m}$ a row Permutation-Like Matrix (row PLM).

Related to this special matrix, we have the following proposition in parallel
with Proposition 3.3.

######  Proposition 3.9.

Let $d\geq 1$ and $1\leq m\leq d$. If $A\in PL_{d}$ then $R_{m}^{(d)}\cdot
A=R_{m}^{(d)}$.

###### Proof.

The proof of Proposition 3.9 follows similarly to Propositions 3.1 and 3.3.

Let $B=R_{m}^{(d)}\cdot A$. Then, since $r_{i,j}=1$ if $i=m$ and $r_{i,j}=0$
otherwise, if $i\neq m$ we have

$b_{i,j}=\sum_{p=1}^{d}r_{i,p}a_{p,j}=0.$

Further, since PLM are closed under multiplication, we know $B$ is a PLM.
Thus, $B$ has exactly one 1 in each column. Hence, because $b_{i,j}=0$ for all
$i\neq m$, we have that $b_{m,j}=1$ for all $1\leq j\leq d$. ∎

Similar to the case $d=3$, we can also consider matrix multiplication of
$A\cdot R_{m}^{(d)}$, where $1\leq m\leq d$..

######  Proposition 3.10.

Let $A$ be a PLM and let $1\leq m\leq d$. If $B=A\cdot R^{(d)}_{m}$, then
$b_{i,j}=a_{i,m}$ for all $1\leq i,j\leq d$.

###### Proof.

This follows a similar proof as Proposition 3.4, which we give for
completeness.

Let $B=A\cdot R_{m}^{(d)}$. Recall that

$r_{i,j}=\begin{cases}1,&\ \ i=m\\\ 0,&\ \ \textrm{otherwise}\end{cases}$

Therefore, for all $1\leq i,j\leq d$,

$b_{i,j}=\sum_{p=1}^{d}a_{i,p}r_{p,j}=a_{i,m}r_{m,j}=a_{i,m}.$

∎

Since we have considered the case of row PLM, we now define CPLM for $d>3$.

######  Definition 3.13.

We say that $A\in PL_{d}$ is a canonical Permutation-Like Matrix (CPLM) if it
is a block matrix of the form

$A=\begin{pmatrix}\boxed{a_{1,1}}&\boxed{0\ 0\ \ldots\ 0}\\\
\boxed{\begin{matrix}a_{2,1}\\\ a_{3,1}\\\ \vdots\\\
a_{d,1}\end{matrix}}&\boxed{A_{1}}\end{pmatrix}$

where $A_{1}\in PL_{d-1}$. We call $A_{1}$ the permutation-like component
(PLC) of $A$. We say $A$ is a leading CPLM if $a_{1,1}=1$.

######  Remark 3.14.

Notice that $R^{(d)}_{m}$ are CPLM for $m>1$.

Similar to the case $d=3$, we have the following lemma that reduces the number
of cases.

######  Lemma 3.15.

Let $A\in PL_{d}$. Then, there exists $\sigma\in S_{d}$ and CPLM $B$ such that
$\tau\ast A=B$.

Lemma 3.15 follows a similar proof as Lemma 3.4, which we give for
completeness.

###### Proof.

First, if $A$ is a row PLM, then either it is a CPLM with a leading element of
zero or $(1,2)\ast A$ is a CPLM with a leading element of zero. Indeed,
$R_{m}^{(d)}$ is a CPLM for $m>1$ with PLC $R_{m-1}^{(d-1)}$. Further, in the
case of $R_{1}^{(d)}$, it follows that $(1,2)\ast R_{1}^{(d)}=R_{2}^{(d)}$.
Next, suppose $A$ is not a row PLM.

If we look at the $d\times d-1$ matrix $\tilde{A}$ given by
$\tilde{a}_{i,j}=a_{i,j+1}$ for $1\leq i\leq d$ and $1\leq j\leq d-1$, we have
at least one row will be all zeros, as there is at most 1 nonzero element in
each column. Let $r^{\prime}$ be the row of $\tilde{A}$ with all zeros and
take $\sigma=(1,r^{\prime})$. So, $\sigma\ast A$ is the matrix given by
swapping rows 1 and $r^{\prime}$ in $A$. Further, by construction, we know
that the first row of $\sigma\ast A$ in columns $2,3,\ldots,d$ are all zero.
Thus, $\sigma\ast A$ is a CPLM. ∎

With Lemma 3.15, we now reduce the problem down to $A\cdot B$, where $A$ is a
CPLM and $B\in PL_{d}$. In parallel with the case $d=3$, we will start with
considering where $B$ is a CPLM. This is broken down into the cases where $B$
is a leading CPLM and $B$ is not a leading CPLM. We start with the latter.

######  Proposition 3.11.

Let $A,B$ be CPLM with PLC $A_{1}$ and $B_{1}$, respectively. Then, if the
leading element of $B$ is zero and $b_{x,1}=1$,

$A\cdot B=\begin{pmatrix}0&0\ 0\ \ldots\ 0\\\ v&A_{1}\cdot B_{1}\end{pmatrix}$

where $v$ is the $(x-1)^{st}$ column of $A_{1}$.

###### Proof.

Let $A\cdot B=C$ and denote the $i^{th}$ row and $j^{th}$ column of $A$, $B$,
and $C$ by $a_{i,j},b_{i,j},$ and $c_{i,j},$ respectively. Notice that the
$(x-1)^{st}$ column of $A_{1}$ is given by the entries $a_{i+1,x}$ for $1\leq
i\leq d-1$.

Now, since $A$ and $B$ are CPLM, we know that $a_{1,j}=b_{1,j}=0$ for all
$2\leq j\leq d$. In particular, we know that

$c_{1,j}=\sum_{p=1}^{d}a_{1,p}b_{p,j}=a_{1,1}b_{1,j}$

for all $1\leq j\leq d$. However, if $j>1$, then $c_{1,j}=0$ since
$b_{1,j}=0$, as $B$ is a CPLM. Further, since the leading element of $B$ is
zero, we know that $c_{1,1}=0$, as $b_{1,1}=0$.

Next, consider the remaining terms in the first column. By assumption, we took
that $b_{x,1}=1$ and $b_{i,1}=0$ for all $i\neq x$. Thus,

$c_{i,1}=\sum_{p=1}^{d}a_{i,p}b_{p,1}=a_{i,x}b_{x,1}=a_{i,x}$

for all $2\leq i\leq d$. In particular, notice that $a_{i,x}$ is the
$(i-1)^{st}$ row and $(x-1)^{st}$ column of $A_{1}$. Thus, the vector
$v=\begin{pmatrix}c_{2,1}\\\ c_{3,1}\\\ \vdots\\\ c_{d,1}\end{pmatrix}$ gives
the $(x-1)^{st}$ column of $A_{1}$.

Lastly, consider the terms $c_{i,j}$, where $2\leq i,j\leq d$. Remember that
$b_{1,j}=0$ for all $j\geq 2$, so

$c_{i,j}=\sum_{p=1}^{d}a_{i,p}b_{p,j}=\sum_{p=2}^{d}a_{i,p}b_{p,j}.$

However, since $a_{i+1,j+1}$ and $b_{i+1,j+1}$ for $1\leq i,j\leq d-1$
determines $A_{1}$ and $B_{1}$, respectively, we know that $c_{i,j}$ is given
by the $(i-1)^{st}$ row and $(j-1)^{st}$ column of $A_{1}\cdot B_{1}$ for
$2\leq i,j\leq d$. Therefore, $C$ is a CPLM and satisfies the statement of the
proposition. ∎

Next, we give the parallel proposition to Proposition 3.6.

######  Proposition 3.12.

Let $A,B$ be CPLM with PLC $A_{1}$ and $B_{1}$, respectively. If $B$ is a
leading CPLM, then $C=A\cdot B$ is a CPLM with PLC $A_{1}\cdot B_{1}$. Further
if $a_{i,j}$ and $c_{i,j}$ denote the $i^{th}$ row and $j^{th}$ column of $A$
and $C$, respectively, then $a_{m,1}=c_{m,1}$ for all $1\leq m\leq d$.

###### Proof.

First, consider $c_{1,j}$ for $1\leq j\leq d$. Since $B$ is a leading CPLM, we
know that $b_{1,1}=1$ and $b_{1,j}=0$ for all $j>1$. Further, since $A$ is a
CPLM, we know that $a_{1,j}=0$ for $j>1$. Thus,

$c_{1,j}=\sum_{p=1}^{d}a_{1,p}b_{p,j}=a_{1,1}b_{1,j}.$

This gives us that $c_{1,j}=0$ for $j>1$ and $c_{1,1}=a_{1,1}$.

Next, consider $c_{i,1}$ for $1\leq i\leq d$. Since $B$ is a leading CPLM, we
know that $b_{i,1}=0$ for all $i>1$ with $b_{1,1}=1$. Thus,

$c_{i,1}=\sum_{p=1}^{d}a_{i,p}b_{p,1}=a_{i,1}b_{1,1}.$

Hence, $c_{i,1}=a_{i,1}$ for all $1\leq i\leq d$.

Lastly, consider $c_{i,j}$ for all $1<i,j\leq d$. Notice that

$A_{1}=\begin{pmatrix}a_{2,2}&a_{2,3}&\ldots&a_{2,d}\\\
a_{3,2}&a_{3,3}&\ldots&a_{3,d}\\\ \vdots&\vdots&\ddots&\vdots\\\
a_{d,2}&a_{d,3}&\ldots&a_{d,d}\end{pmatrix}$

and

$B_{1}=\begin{pmatrix}b_{2,2}&b_{2,3}&\ldots&b_{2,d}\\\
b_{3,2}&b_{3,3}&\ldots&b_{3,d}\\\ \vdots&\vdots&\ddots&\vdots\\\
b_{d,2}&b_{d,3}&\ldots&b_{d,d}\end{pmatrix}.$

Now, since $a_{i,1}=b_{1,j}=0$ for all $1<i,j\leq d$, as $A$ is a CPLM and $B$
is a leading CPLM, we know that

$c_{i,j}=\sum_{p=1}^{d}a_{i,p}b_{p,j}=\sum_{p=2}^{d}a_{i,p}b_{p,j}.$

Notice that the matrix $C_{1}=\begin{pmatrix}c_{2,2}&c_{2,3}&\ldots&c_{2,d}\\\
c_{3,2}&c_{3,3}&\ldots&c_{3,d}\\\ \vdots&\vdots&\ddots&\vdots\\\
c_{d,2}&c_{d,3}&\ldots&c_{d,d}\end{pmatrix}$ is precisely $A_{1}\cdot B_{1}$.
Therefore, $C$ is a CPLM with PLC $C_{1}=A_{1}\cdot B_{1}$. ∎

Propositions 3.9 and 3.12 yield the following corollary.

######  Corollary 3.16.

Let $A,B$ be CPLM with PLC $A_{1}$ and $B_{1}$, respectively. Further, suppose
that $A_{1}=R_{m}^{(d-1)}$ for $1\leq m\leq d-1$ and that $B$ is not a leading
CPLM. Then, $A\cdot B=R_{m+1}^{(d)}$.

Now, we have covered the case of CPLM, so we will consider the parallel case
to that covered in Proposition 3.7.

######  Definition 3.17.

Let $A\in PL_{d}$. Then, we say that $A$ is a pre-Canonical Permutation-Like
Matrix (PCPLM) if there exists $\tau\in S_{d}$ such that $\tau\star A$ is a
CPLM.

Now, the definition of PCPLM leads immediately to the following.

######  Proposition 3.13.

Let $A,B\in PL_{d}$ such that $A$ is a CPLM and $B$ is a PCPLM such that
$\tau\star B$ is a CPLM for some $\tau\in S_{d}$. Then,

$A\cdot B=\tau^{-1}\star(A\cdot(\tau\star B)).$

Lastly, we would like to consider the following case.

######  Definition 3.18.

Let $A\in PL_{d}$. Then, we say that $A$ is an Irregular Permutation-Like
Matrix (IPLM) if it is not a row PLM, CPLM, or PCPLM.

For $B\in PL_{d}$, if $B$ is irregular and we take $\zeta(B)$ to be the number
of nonzero entries in the first row of $B$, then this definition of IPLM
implies that $\zeta(B)>1$. This follows by a similar proof as the argument in
the proof of Proposition 3.8, since $B$ is not CPLM or PCPLM. Further, if all
of the entries in the first row are 1, then $B$ is a row PLM, hence not an
IPLM. So, the only case left to consider is that of $1<\zeta(B)<d$.

######  Remark 3.19.

We use $\zeta(B)$ because it is related to the number of zero entries in the
first row. Indeed, $d-\zeta(B)$ is the number of zero entries in the first row
of $B$.

######  Proposition 3.14.

Let $X(A,n)$ be the $d-1\times d-1$ matrix given by

$X(A,n)=\begin{pmatrix}a_{2,1}&a_{2,1}&\ldots&a_{2,1}&0&0&\ldots&0\\\
a_{3,1}&a_{3,1}&\ldots&a_{3,1}&0&0&\ldots&0\\\
a_{4,1}&a_{4,1}&\ldots&a_{4,1}&0&0&\ldots&0\\\
\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots\\\
a_{d,1}&a_{d,1}&\ldots&a_{d,1}&0&0&\ldots&0\end{pmatrix}$

where the first n columns of row i have the entries $a_{i+1,1}$.

Suppose that $A,B\in PL_{d}$ such that $A$ is a CPLM with PLC $A_{1}$. Further
suppose $B$ is an IPLM with $1<\zeta(B)<d$.

  1. (1)

Suppose $B$ is a block matrix of the form $B=\begin{pmatrix}1\ 1\ \ldots\ 1&0\
0\ \ldots\ 0\\\ \textbf{0}&B_{1}\end{pmatrix}$ where 0 is the
$d\times\zeta(B)$ zero matrix and $B_{1}$ is a $d-1\times d-\zeta(B)$ matrix.
Take $B_{2}$ to be the $d-1\times d-1$ matrix given by augmenting $B_{1}$ on
the left by the $d-1\times\zeta(B)-1$ zero matrix. Then $A\cdot B$ is given by
the block matrix

$A\cdot
B=\begin{pmatrix}\begin{matrix}a_{1,1}&a_{1,1}&\ldots&a_{1,1}\end{matrix}&\begin{matrix}0&0&\ldots&0\end{matrix}\\\
&\\\ \begin{matrix}v&v&\ldots&v\end{matrix}&X(A,\zeta(B)-1)+A_{1}\cdot
B_{2}\end{pmatrix}$

where $v=\begin{pmatrix}a_{2,1}\\\ a_{3,1}\\\ \vdots\\\ a_{d,1}\end{pmatrix}$.

  2. (2)

Otherwise, there exists a $\tau\in S_{d}$ such that $\tilde{B}=\tau\star B$ is
of the form of the previous case and

$A\cdot
B=\tau^{-1}\star\begin{pmatrix}\begin{matrix}a_{1,1}&a_{1,1}&\ldots&a_{1,1}\end{matrix}&\begin{matrix}0&0&\ldots&0\end{matrix}\\\
&\\\
\begin{matrix}v&v&\ldots&v\end{matrix}&X(A,\zeta(\tilde{B})-1)+A_{1}\cdot\tilde{B}_{2}\end{pmatrix}$

where $v=\begin{pmatrix}a_{2,1}\\\ a_{3,1}\\\ \vdots\\\ a_{d,1}\end{pmatrix}$.

###### Proof.

The latter statement is immediate since for all IPLM $B$, we know
$1<\zeta(B)<d$ and hence we can put $B$ in the form of the former case, up to
column permutations. So, it suffices to prove the former.

Suppose that $B=\begin{pmatrix}1\ 1\ \ldots\ 1&0\ 0\ \ldots\ 0\\\
\textbf{0}&B_{1}\end{pmatrix}$ and let $C=A\cdot B$. Take $B_{2}$ to be the
$d-1\times d-1$ matrix given by augmenting $B_{1}$ on the left by the zero
matrix. We will compute $c_{i,j}$ for $1\leq i,j\leq d$.

First, consider $c_{i,1}$ for all $1\leq i\leq d$. Now, there exists some
$1\leq m\leq d$ such that $a_{m,1}=1$ and $a_{i,1}=0$ for $i\neq m$. Further,
we know that $b_{1,1}=1$ and $b_{i,1}=0$ for $i>1$. Thus,

$c_{i,1}=\sum_{p=1}^{d}a_{i,p}b_{p,1}=a_{i,1}.$

So, $c_{m,1}=1$ and $c_{i,1}=0$ for $i\neq m$.

Next, consider $c_{1,j}$ for all $1<j\leq d$. Since $A$ is a CPLM, we know
that $a_{1,j}=0$ for $j>1$. So,

$c_{1,j}=\sum_{p=1}^{d}a_{1,p}b_{p,j}=a_{1,1}b_{1,j}$

However, there exists $N>1$ such that $b_{1,j}=0$ if $j>N$ and $b_{1,j}=1$ if
$j\leq N$. Thus, $c_{1,j}=0$ if $j>N$ and $c_{1,j}=a_{1,1}$ if $j\leq N$.

Now we will consider $c_{i,j}$ for all $1<i,j\leq d$. Since $b_{1,j}=0$ for
$j>N$, we know that

$c_{i,j}=\sum_{p=1}^{d}a_{1,p}b_{p,j}=\sum_{p=2}^{d}a_{i,p}b_{p,j}$

for $j>N$. Also, since $b_{1,j}=1$ for $j\leq N$, we know that

$c_{i,j}=a_{i,1}+\sum_{k=2}^{d}a_{i,k}b_{k,j}.$

In particular, notice that, up to addition by an element of $A$ in the first
$\zeta(B)-1$ columns, the matrix
$C_{1}=\begin{pmatrix}c_{2,2}&c_{2,3}&\ldots&c_{2,d}\\\
c_{3,2}&c_{3,3}&\ldots&c_{3,d}\\\ \vdots&\vdots&\ddots&\vdots\\\
c_{d,2}&c_{d,3}&\ldots&c_{d,d}\end{pmatrix}$ corresponds to $A_{1}\cdot
B_{2}$. Further, this element of $A$ is explicitly given in $X(A,\zeta(B)-1)$
and since addition is pointwise, $C_{1}=X(A,\zeta(B)-1)+A_{1}\cdot B_{2}$.
Therefore, we have computed $C$ explicitly and the statement holds. ∎

Proposition 3.14 covers our final case, culminating in the following theorem.

######  Theorem 3.20.

Let $A,B\in PL_{d}$ for $d>3$. Then, $A\cdot B$ is given, up to row
permutation, by Propositions 3.9-3.14.

###### Proof.

This follows similarly to the case of $d=3$. If $A$ is a row PLM, we can apply
Proposition 3.9. Otherwise, we can assume that $A$ is a CPLM by Lemma 3.15. By
the definition of IPLM, we know that every PLM is a row PLM, CPLM, PCPLM, or
IPLM. All of these cases are covered by Propositions 3.11-3.14. ∎

##  4\. Properties of Permutation-Like Matrices

In this section, we will give some properties of PLM, focusing on $A\in
PL_{d}$ for $d=2$ or $d=3$. Throughout this section, assume that $k$ has
characteristic 0.

###  4.1. Periodicity of Permutation-Like Matrices

First, we will look at the periodicity of PLM. Recall that a periodic matrix
$A$ is a square matrix such that $A^{k+1}=A$. The minimal such $k$ is called
the index of $A$ [1].

######  Proposition 4.1.

Let $A\in PL_{d}$ for $d=2$ or $d=3$. Then, $A$ is a periodic matrix or there
exists $k\geq 1$ such that $A^{2}$ is a row PLM.

Proposition 4.1 can be verified computationally, where either $A^{2}$ is a row
PLM or $A^{2}$, $A^{3}$, or $A^{4}$ is $A$. Further, since row PLM absorb
right multiplication in $PL_{d}$, we know have a distinction here between
these two classes of PLM: these ones that are periodic and the ones that have
$A^{k}$ are row PLM for sufficiently large $k$. With this in mind, we have the
following definition.

######  Definition 4.1.

Let $A\in PL_{d}$ for $d>1$. If there exists $k\geq 1$ such that $A^{k+1}$ is
a row PLM, we say that $A$ is a pre-row Permutation-Like Matrix (pre-row PLM).

######  Remark 4.2.

Notice that every row PLM is a pre-row PLM.

######  Remark 4.3.

If $A$ is pre-row and not a row PLM, then $A$ is not periodic. This arises due
to Proposition 3.9. For example,

$A=\begin{pmatrix}0&0&0\\\ 1&0&0\\\ 0&1&1\end{pmatrix}$

is pre-row since

$A^{2}=\begin{pmatrix}0&0&0\\\ 0&0&0\\\ 1&1&1\end{pmatrix}$

is a row PLM. Further, $A^{m}=A^{2}\cdot A^{m-2}=R_{3}^{(3)}\cdot
A^{m-2}=R_{3}^{(3)}$ for all $m>2$. In particular, there is no $m$ such that
$A^{m+1}=A$.

######  Remark 4.4.

If we consider the case $d=3$, note that if $A$ is a CPLM that is not a
leading CPLM and has a row PLM $R_{m}^{(d-1)}$ for its PLC, then
$A^{2}=R_{m+1}^{(d)}$. This extends for $d>3$, as stated in Corollary 3.16,
but it is not immediate that these are the only pre-row PLM.

###  4.2. Eigenvalues of PLM

Next, we would like to consider the eigenvalues of PLM. As a result of
Proposition 4.1, we have the following corollary related to eigenvalues.

######  Corollary 4.5.

Let $A\in PL_{d}$ be a PLM for $d=2$ or $d=3$. Then every eigenvalues of $A$
is either 0 or a root of unity.

###### Proof.

By Proposition 4.1, we know that every $PL_{d}$ for $d=2$ or $d=3$ is a pre-
row PLM or periodic.

Suppose $A$ is periodic. Then, there exists $m$ such that $A^{m+1}-A=0$. In
particular, we know that the eigenvalues of $A$ are roots of the polynomial
$y=x^{m+1}-x$. The only possibilities are $m^{th}$ roots of unity and 0.

Now, suppose $A$ is a pre-row PLM. Then, there exists $m$ such that $A^{m}$ is
a row PLM. Further, for every row PLM $R^{(d)}_{n}$, it follows by Proposition
3.9 that $\left(R^{(d)}_{n}\right)^{2}=R^{(d)}_{n}$. In particular,
$A^{2m}-A^{m}=0$, so the eigenvalues of $A$ are roots of the polynomial
$y=x^{2m}-x^{m}$. The only possibilities are $m^{th}$ roots of unity and 0. ∎

We do not currently have a result concerning the eigenvalues of PLM for $d>3$,
except for certain cases. For pre-row PLM, we do have the following result
that comes from the definition of pre-row PLM.

######  Proposition 4.2.

Let $A$ be a $d\times d$ pre-row PLM for $d>1$. If $\lambda$ is an eigenvalue
of $A$, then $\lambda=0$ or $\lambda$ is a roots of unity.

###### Proof.

Since $A$ is a pre-row PLM there exists $k$ such that $A^{k}$ is a row PLM.
Further, for every row PLM $R^{(d)}_{m}$, it follows by Proposition 3.9 that
$\left(R^{(d)}_{m}\right)^{2}=R^{(d)}_{m}$. In particular, $A^{2k}-A^{k}=0$,
so the eigenvalues of $A$ are roots of the polynomial $y=x^{2k}-x^{k}$. The
only possibilities are $k^{th}$ roots of unity and 0. ∎

This leads to the following corollary.

######  Corollary 4.6.

Let $A$ be a $d\times d$ CPLM with PLC $A_{1}$ for $d>1$. Further suppose
$A_{1}$ is a row PLM and $A$ is not a leading PLM. Then, the eigenvalues of
$A$ are zero or roots of unity.

Notice that Corollary 4.6 follows immediately from previous discussion that
CPLM with leading element zero and PLC given by a row PLM are pre-row PLM.

Instead of giving a concrete answer to the eigenvalues of PLM in general, we
will give a partial answer by computing the spectral radius of such matrices.

Recall that given complex eigenvalues
$\lambda_{1},\lambda_{2},\ldots,\lambda_{d}$ for a $d\times d$ matrix $A$, the
spectral radius is given by
$\rho(A)=max\\{|\lambda_{1}|,|\lambda_{2}|,\ldots,|\lambda_{d}|\\}$, where
$|z|$ is the usual norm on the complex numbers. Further, recall given a matrix
norm $||\cdot||$, we know that $\rho(A)\leq||A||$. This leads to the following
proposition.

######  Proposition 4.3.

Let $A\in PL_{d}(\mathbb{C})$ for all $d\geq 1$. Then, $\rho(A)\leq 1$.

###### Proof.

This easily follows using the 1-norm. Recall that the 1-norm of $A$ to be
given by

$||A||_{1}=max_{1\leq j\leq d}\sum_{i=1}^{d}a_{i,j}.$

However, since $A$ is a PLM, for each $1\leq j\leq d$, there exists a unique
$1\leq m\leq d$ such that $a_{m,j}=1$, with all other entries in that column
zero. Thus, $||A||_{1}=1$ and hence $\rho(A)\leq 1$. ∎

As a last note on eigenvalues, we have the following proposition and the
related corollary.

######  Proposition 4.4.

Let $A\in PL_{d}$ for $d>1$. If $A$ is not a Permutation Matrix, then $0$ is
an eigenvalue for $A$.

###### Proof.

Suppose that $A$ is not a Permutation Matrix. Notice that since $A$ is PLM, it
has exactly $d$ nonzero entries, which are all equal to 1 and in different
columns. Let the vector $c\in\mathbb{R}^{d}$ be the vector whose $n^{th}$
component, denoted $c_{n}$, corresponds to the row of $A$ such that
$a_{c_{n},n}=1$. Since $A$ is not a Permutation Matrix, we know that not every
row sums to 1. In particular, there exists $1\leq m\neq n\leq d$ such that
$c_{m}=c_{n}$. However, there are $d$ rows and $d$ columns, which implies
there exists some $1\leq n_{0}\leq d$ such that $n_{0}$ does not appear as a
component in the vector $c$. Thus, in the matrix $A$, the row $n_{0}$ consists
of all zeros and hence the determinant is zero. Therefore, $0$ is an
eigenvalue of $A$. ∎

This immediately yields the following corollary. Note that the identity matrix
is considered to be a permutation matrix.

######  Corollary 4.7.

The only invertible elements of $PL_{d}$ for $d>1$ are the Permutation
Matrices.

######  Remark 4.8.

Corollary 4.7 implies that the only elements of the Stochastic Group that are
in $PL_{d}$ are the Permutation Matrices.

###  4.3. Left Stochastic Matrices

Lastly, we would like to visit the idea of Stochastic Matrices and how it
relates to PLM. Recall that a matrix $A$ with non-negative entries $a_{i,j}$
is Left (Column) Stochastic if for each $1\leq j\leq d$, it follows that
$\displaystyle\sum_{i=1}^{d}a_{i,j}=1$. Similarly, $A$ is Right (Row)
Stochastic if for each $1\leq i\leq d$, it follows that
$\displaystyle\sum_{j=1}^{d}a_{i,j}=1$. Lastly, we say that a matrix is Doubly
Stochastic if it is both Left and Right Stochastic ([3]).

There is a classical result, called Birkhoff-Von Neumann’s Theorem ([2]),
which says that a matrix $A$ is Doubly Stochastic if and only if there exists
$m\geq 1$ and $\lambda_{i}\in[0,1]$ for $1\leq i\leq m$ such that
$\displaystyle\sum_{i=1}^{m}\lambda_{i}=1$ and
$A=\displaystyle\sum_{i=1}^{m}\lambda_{i}P_{i}$, where $P_{i}$ are Permutation
Matrices. Recall that the condition that there exists $m\geq 1$ and
$\lambda_{i}\in[0,1]$ for $1\leq i\leq m$ such that
$\displaystyle\sum_{i=1}^{m}\lambda_{i}=1$ and
$A=\displaystyle\sum_{i=1}^{m}\lambda_{i}P_{i}$, where $P_{i}$ are Permutation
Matrices means that every Doubly Stochastic Matrix is a convex combination of
Permutation Matrices. We would like to state a similar result for PLM
regarding Left Stochastic Matrices. First, notice the following comes
immediately from the definition of left stochastic with the definition of PLM.

######  Lemma 4.9.

Every Permutation-Like Matrix is a Left Stochastic Matrix.

Next, we would like to prove a similar result as Birkhoff-Von Neumann’s
Theorem, but for Left Stochastic Matrices.

######  Lemma 4.10.

Let $\lambda_{i}\in[0,1]$ for $1\leq i\leq k$ such that
$\displaystyle\sum_{i=1}^{k}\lambda_{i}=1$ and let $A_{i}$ for $1\leq i\leq k$
be Left Stochastic Matrices. Then,
$\lambda_{1}A_{1}+\lambda_{2}A_{2}+\ldots+\lambda_{k}A_{k}$ is a Left
Stochastic Matrix.

###### Proof.

For every $1\leq i\leq k$, notice that the sum of every column of $A_{i}$ is 1
by definition of left stochastic, so the sum of every column of
$\lambda_{i}A_{i}$ is $\lambda_{i}$. Further, since matrix addition is
pointwise, we have that the sum of every column of
$\lambda_{1}A_{1}+\lambda_{2}A_{2}+\ldots+\lambda_{k}A_{k}$ is
$\lambda_{1}+\lambda_{2}+\ldots+\lambda_{k}=1$. Therefore,
$\lambda_{1}A_{1}+\lambda_{2}A_{2}+\ldots+\lambda_{k}A_{k}$ is a Left
Stochastic Matrix. ∎

Notice that Lemma 4.10 implies that the convex combination of PLM is Left
Stochastic. We will utilize this in the following theorem.

######  Theorem 4.11.

Let $A$ be a $d\times d$ matrix. Then, $A$ is left stochastic if and only if
$A$ is a convex combination of Permutation-Like Matrices.

###### Proof.

The reverse implication follows immediately from Lemma 4.10. Thus, we will
focus on the forward implication.

Given a $d\times d$ matrix $B$ and $1\leq j\leq d$, let $r(B)\in k^{d}$ be the
vector that gives the row of the first strictly positive entry in each column
of $B$. Let $r(B)_{j}$ be the $j^{th}$ component of $r(B)$, i.e. the row of
the first strictly positive entry in column $j$. Lastly, let $P(B)\in PL_{d}$
be the PLM such that for each $1\leq j\leq d$, $P(B)$ has a 1 in $r(B)_{j}$
row and $j^{th}$ column, with zeros elsewhere. For example, if we take $B$ to
be the Left Stochastic Matrix

$B=\begin{pmatrix}0.1&0&0.2\\\ 0.9&0.5&0.8\\\ 0&0.5&0\end{pmatrix}$

then, $P(B)$ is given by

$P(B)=\begin{pmatrix}1&0&1\\\ 0&1&0\\\ 0&0&0\end{pmatrix}.$

Let $A$ be a $d\times d$ Left Stochastic Matrix with entries $a_{i,j}$. In
particular, we know that for all $1\leq j\leq d$ that
$\displaystyle\sum_{i=1}^{d}a_{i,j}=1$. If $A\in PL_{d}$, we are done. Suppose
that $A$ is not a PLM.

First, let $\lambda_{1}=min_{1\leq j\leq d}\\{a_{r(A)_{j},j}|1\leq j\leq
d\\}$. Notice that $\lambda_{1}<1$ since the columns are non-negative, sum to
1, and $A$ is not a PLM so there exists at least two strictly positive terms
in some column. Then, $A_{1}=A-\lambda_{1}P(A)$ is a $d\times d$ matrix with
at least 1 more zero than $A$. Notice that the sum of the columns of $A_{1}$
are all $1-\lambda_{1}$.

Next, suppose that for some $n\geq 1$, we have
$A_{n}=A-\sum_{i=1}^{n}\lambda_{i}P_{i}$ for PLM $P_{i}$. Take
$\lambda_{n+1}=min_{1\leq j\leq d}\\{a_{r(A_{n})_{j},j}|1\leq j\leq d\\}$.
Notice that the columns of $A_{n}$ sum to $1-\sum_{i=1}^{n}\lambda_{i}$, so
$\lambda_{n+1}\leq 1-\sum_{i=1}^{n}\lambda_{i}$. Now, if we take
$A_{n+1}=A_{n}-\lambda_{n+1}P(A_{n})$, we have at least 1 more zero in
$A_{n+1}$ than $A_{n}$. Further, the columns of $A_{n+1}$ sum to
$1-\sum_{i=1}^{n+1}\lambda_{i},$ strictly less than the sum of each column of
$A_{n}$.

Either $A_{n+1}$ is the zero matrix or we can iterate this process. Since
there are finitely many positions, this process terminates. Further, we are
reducing each column by $0<\lambda_{n+1}<1$ each time, so this process will
terminate for all columns at the same step. Lastly, because we are taking
$\lambda_{n+1}$ to be a minimum across the first strictly positive entries in
each column (ordering the rows using the usual ordering on the integers), we
never end up with any negative entries. Therefore, there exists some $N\geq 1$
such that

$A-\sum_{i=1}^{N}\lambda_{i}P_{i}=0$

where $P_{i}\in PL_{d}$ and $0<\lambda_{i}<1$ for all $1\leq i\leq N$. Notice
that $\sum_{i=1}^{N}\lambda_{i}=1$, since following the last step the columns
sum to $0=1-\sum_{i=1}^{N}\lambda_{i}$. Thus, by Lemma 4.10, we know that
$\sum_{i=1}^{N}\lambda_{i}P_{i}$ is a Left Stochastic Matrix and

$A=\sum_{i=1}^{N}\lambda_{i}P_{i}.$

∎

######  Remark 4.12.

Stated another way, this theorem says that we know that the polytope in
$k^{d^{2}}$ formed by Left Stochastic Matrices has $PL_{d}$ as its vertices. A
similar proof could be used to show that the polytope in $k^{d^{2}}$ by Right
Stochastic Matrices has its vertex set as the set of matrices whose transpose
is a PLM. We will not go in this direction in this paper because we are
focused explicitly on PLM.

##  5\. Remarks on Permutation-Like Matrices

We would like to end on a handful of remarks and open questions concerning
PLM.

First, notice that the motivation for studying PLM was to determine a general
pattern for leg identifying multiplication on edge $d$-partitions of $K_{2d}$.
However, as seen in the case $d>3$, the descriptions of the multiplication of
PLM although explicit are not as straightforward to use in a general rule. For
that reason, we have the following open problem.

######  Open Problem 5.1.

Obtain an explicit description of the multiplication of edge $d$-partitions of
$K_{2d}$ using the results of this paper.

Also, recall that the eigenvalues of the Permutation Matrices are all roots of
unity. It is interesting that the eigenvalues of PLM for $d=2$ and $d=3$ are
roots of unity and 0 (for PLM that are not Permutation Matrices or the
identity). This fits into the notion that PLM generalize the Permutation
Matrices, as the eigenvalues of the Permutation Matrices are roots of unity.
Therefore, we have the following open conjecture.

######  Conjecture 5.2.

Let $A\in PL_{d}$ be a PLM for $d>1$. Then, the eigenvalues of $A$ are zeros
or roots of unity. Further, zero is an eigenvalue if and only if $A$ is not a
Permutation Matrix or the identity matrix.

Notice that the second half of this conjecture has been answered, whereas the
former part has only been answered for $d\leq 3$.

Third, a constructive formulation was obtained for Theorem 4.11 and a similar
formulation can be obtained for the Right Stochastic version (as previously
remarked). One open question follows since the polytope (Birkoff Polytope)
formed by Doubly Stochastic Matrices is the intersection of the polytopes
formed by Left and Right Stochastic Matrices.

######  Open Problem 5.3.

Given a doubly stochastic matrix $A$, determine if its convex combination of
PLM constructed in Theorem 4.11 and convex combination of transposes of PLM
constructed in a similar way can be used to write $A$ as a convex combination
of Permutation Matrices (as stipulated in Birkhoff-Von Neumann’s Theorem).

Fourth, recall the Stochastic Group (introduced in [5]) is defined as the
group of $d\times d$ invertible Left Stochastic Matrices. We know from Theorem
4.11 that every Left Stochastic Matrix can be written as a convex combination
of PLM. This leads to the following problem.

######  Open Problem 5.4.

Obtain a computational formula for writing elements of the Stochastic Group as
convex combinations of PLM.

Fifth, $A$ is a $d\times d$ pre-row PLM for $d=2$ or $d=3$ if and only if $A$
is a CPLM with leading element zero and PLC $R_{m}^{(d-1)}$ for some $1\leq
m\leq d-1$. The reverse implication of this statement holds for $d>3$, but the
forward implication is still an open problem.

######  Open Problem 5.5.

For all $d>1$, show that every $d\times d$ pre-row PLM is a CPLM with leading
element zero and PLC $R_{m}^{(d-1)}$ for some $1\leq m\leq d-1$.

Lastly, one nice property of Permutation Matrices is the identification with
the symmetric group. Further, we know PLM are closed under multiplication,
have an identity, but are not necessarily invertible (thus has a monoid
structure). This leads to the following problem.

######  Open Problem 5.6.

Determine if there exists a monoid which generalizes the symmetric group and
is isomorphic to $PL_{d}$.

## Acknowledgment

We thank Jeremy Case for discussion regarding this paper as well as his
comments towards the presentation of the paper.

## References

  * [1] F. Ayres Jr., Theory and Problems of Matrices. McGraw-Hill, (1962).
  * [2] G. Birkhoff, Tres observaciones sobre el algebra lineal. Univ. Nac. Tucumán Rev, Ser. A, 5, 147–-151. (1946).
  * [3] R. A. Horn and C. R. Johnson, Matrix analysis. Cambridge university press, (2012).
  * [4] S. R. Lippold, The Algebra of $S^{2}$ Upper Triangular Matrices. arXiv:2310.00494 (2023).
  * [5] D. G. Poole, The Stochastic Group. Am. Math. Mon., 102 (1995), no. 9, 798–801.