Canonical form of linear subspaces and coding invariants: the poset metric point of view
Jerry~Anderson~Pinheiro and Marcelo~Firer% \thanks{The authors are at Institute of Mathematics
Statistics and Scientific Computing
University of Campinas
Brazil
e-mail: jerryapinheiro@gmail.com
mfirer@ime.unicamp.br.
In this work we introduce the concept of a sub-space decomposition, subject to a partition of the coordinates. Considering metrics determined by partial orders in the set of coordinates, the so called poset metrics, we show the existence of maximal decompositions according to the metric. These decompositions turns to be an important tool to obtain the canonical form for codes over any poset metrics and to obtain bounds for important invariants such as the packing radius of a linear subspace. Furthermore, using maximal decompositions, we are able to reduce and optimize the full lookup table algorithm for the syndrome decoding process.
decomposicao_junho.tex
\documentclass[journal,draftcls,onecolumn,12pt,twoside]{IEEEtran}

\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{pdfpages}
\usepackage{mathrsfs}

\usepackage{hyperref}

\interdisplaylinepenalty=2500


\usepackage[cmintegrals]{newtxmath}


%\theoremstyle{definition}
\newtheorem{theorem}{Theorem}
\newtheorem{conjecture}{Conjecture}
\newtheorem{corollary}{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}
\newtheorem{lemma}{Lemma}
\newtheorem{observation}{Observation}
\newtheorem{proposition}{Proposition}
\newtheorem{remark}{Remark}

%\newtheorem{definition2}{Definition}






%\hyphenation{op-tical net-works semi-conduc-tor}


\begin{document}

\title{Canonical form of linear subspaces and coding invariants: the poset metric point of view}

\author{Jerry~Anderson~Pinheiro and Marcelo~Firer%
\thanks{The authors are  at Institute of Mathematics, Statistics and Scientific Computing, University of Campinas, Brazil, e-mail: jerryapinheiro@gmail.com, mfirer@ime.unicamp.br.}% <-this % stops a space
%\thanks{Marcelo Firer  is with Institute of Mathematics, Statistics and Scientific Computing, University of Campinas, Brazil, e-mail: mfirer@ime.unicamp.br}% <-this % stops a space
%\thanks{Manuscript received April 19, 2005; revised August 26, 2015.}
}
%% The paper headers
%\markboth{Journal of \LaTeX\ Class Files,~Vol.~14, No.~8, August~2015}%
%{Shell \MakeLowercase{\textit{et al.}}: Bare Demo of IEEEtran.cls for IEEE Communications Society Journals}

\maketitle


\begin{abstract}
In this work we introduce the concept of a sub-space decomposition, subject to a partition of the coordinates. Considering metrics determined by partial orders in the set of coordinates, the so called poset metrics, we show the existence of maximal decompositions according to the metric. These decompositions turns to be an important tool to obtain the canonical form for codes over any poset metrics and to obtain bounds for important invariants such as the packing radius of a linear subspace. Furthermore, using maximal decompositions, we are able to reduce and optimize the full lookup table algorithm for the syndrome decoding process.
\end{abstract}

\begin{IEEEkeywords}
Canonical form, poset codes, poset metrics, syndrome decoding, packing radius. \\
	\textbf{MSC2010}: 15A21, 94B05, 52C17  
\end{IEEEkeywords}



\IEEEpeerreviewmaketitle

\tableofcontents

\section{Introduction}

%{\color{blue} O CORRETO SERIA MUDARMOS A NOMENCLATURA, DE CODIGOS PARA SUBESPACOS, APENAS NA SESSAO IV, ONDE TRATAMOS DE QUESTOES LIGADAS A CODIGOS, PASSARIAMOS A TRATAR COMO TAIS. NO ENTANTO, TENHO SERIO RECEIO DE ACABARMOS PULANDO COISAS, DE NAO CONSEGUIRMOS MUDAR TUDO. ALGO PARA PENSARMOS}

Coding theory is a mathematical theory that deals with many different aspects that emerges in the engineering of communication. A significant and classical part of it, the study of block-codes, is a subject that deals with many geometric and computational aspects of linear subspaces of finite dimensional vector spaces over finite fields.   

The most classic metric considered in this context is a metric that counts the number of different coordinates between two vectors, and it is named after R. W. Hamming, which introduced it in a seminal work \cite[ 1950]{ham}.  Later, in (\cite{ul}, 1957) and (\cite{lee}, 1958), another well-known metric was proposed, the Lee metric.


 
%In some cases (large $q$-ary alphabets), the Lee metric may be an interesting alternative to the Hamming metric.
%Metrics are mathematical structures of interest in coding theory. The best known and most investigated metric in the context of coding theory is the Hamming metric. It was suggested by R. W. Hamming in \cite{ham} during the description of a code geometric model. Later, in (\cite{ul}, 1957) and (\cite{lee}, 1958), the Lee metric was defined, and became an interesting alternative when non-binary alphabets are used.
Up to our knowledge, the first work considering metrics in a general approach is a short communication of S. W. Golomb (\cite{golomb1969general}, 1969). In that work, Golomb described a family of additive metrics (metrics defined over an alphabet and additively extended to a set of words with a fixed length) which are still being investigated nowadays, as we can see in \cite{qureshiperfect}. Recently, due to the development of new communication channels and models, new families of metrics has been studied in the context of coding theory, as can be seen, for example, in \cite{brualdi1995codes}, \cite{alves2008error}, \cite{gab} and \cite{deza2009encyclopedia}.% This is partially motivated by the fact that, in some cases (when metrics and channels are matched), minimum distance is a Maximum a Posteriori (MAP) decoder. Furthermore, Minimum Distance (MD) decoders may be used to add manageability to the decoding process, what can be achieved by the use, for example, of a Syndrome decoding algorithm. 


The family of \textit{poset metrics} was defined by Brualdi, Graves and Lawrence, in (\cite{brualdi1995codes}, 1995) as an extension of the metrics proposed by Niederreiter in \cite{niederreiter1991combinatorial} and \cite{niederreiter1992orthogonal}. This is a large family of metrics which are determined by partial orders and generalizes the classical Hamming metric. Since then, it has been studied intensively, in order to understand the behaviour of metric invariants that are relevant to coding theory. 

As it frequently happens with generalizations, besides the possible inherent merits, some side effects may arise, either by giving a more profound understanding about the nature of previously established knowledge or by posing some new interesting (and difficult) questions. This is the case of poset metrics.

Postponing the details for the next section, a poset metric depends on the non-zero positions of a vector and also on the level of these positions in a partial order (or the level in the Hasse diagram). A significant part of the knowledge available for poset metrics can be understood once we consider a decomposition of a code (a vector subspace) which depend on the levels of the poset.  

Considering the metrics determined by the family of the so-called hierarchical posets, one can fully grasp the role of such decompositions. Being studied since the 90's, results previously proved\footnote{Results concerning the MacWilliams identity  \cite{classification:macwilliamsidentity}, association schemes \cite{classification:schemes}, extension of isometries  \cite{extensiontheoremforfiniterings3} (MacWilliams Extension Theorem)  and the relation between the packing radius and the minimum distance \cite{felix2012canonical}.} by many researchers were restated in an alternative and simple way \cite{MachadoPinheiroFirer}, all the proofs were derived from the existence of a canonical decomposition. 
 


% under the setting of a partially ordered set. It was shown, in \cite{d2015packing}, that even for the smaller case ($1$-dimensional codes), the complexity to solve the packing radius problem for this family of metrics is NP-hard. However, as we can see in \cite{machado2015characterization}, for the family of hierarchical poset metrics, classical coding invariants are ``easy'' (as easy as in the Hamming case) to obtain by using the canonical-systematic form \cite{felix2012canonical}. For example, the $1$-dimensional packing radius problem with NP-hard complexity turns out to be trivial in the hierarchical case, see \cite{machado2015characterization}. Furthermore, once the minimum distance is known, the $n$-dimensional case (hierarchical) is also trivial. 



%Representations of linear codes by generator matrices, similar to the ones obtained by the canonical-systematic form, depends not only on the choice of a particular basis, but also on the choice of a linear isometry. The election of a standard, and relatively clean representation for codes is motivated by the fact that it can be useful to determine some code parameters. For example, the \emph{standard form} of a code endowed with the Hamming metric provides an easy way to obtain the parity check matrix of this code and allows the characterization of MDS codes and the singleton defect in general (hence, the minimum distance and the packing radius), see \cite{viswanath2006matrix}. The form is called standard because every code has, up to equivalence, a unique such representation. 



Besides the canonical-systematic form introduced in \cite{felix2012canonical} for hierarchical poset metrics, the only known attempt to construct standard forms for poset metrics was made in \cite{alves2011standard}, where a standard form for a particular case (Niederreiter-Rosenbloom-Tsfasman (NRT), or metrics induced by orders consisting of multiple disjoint chains with same cardinality) is presented. In that work, one can see that the standard form is not unique (in any possible sense). In a matter of fact,  unicity of such a pre-established form is a characteristic of hierarchical posets \cite[Theorem 3]{MachadoPinheiroFirer}. 

Since unicity of the form is not available, we strives for the best possible option:  canonical forms determined by maximal decompositions, whose unicity is obtained according to the degree of the decomposition. Hence, the main subject of this work is how to decompose a  subspace ``respecting'' the metric structure. For the reader that is not particularly interested in coding theory, despite the use of a terminology from coding theory, there is essentially a very short lexicon that needs to be translated: instead of ``code'' and ``$[n,k]_q$''-code, one should read ``vector subspace'' and ``$k$-dimensional vectors subspace of $\mathbb{F}_q^n$'', respectively; instead of ``$\mathcal{C}\subseteq\mathbb{F}_q^n$'', simply writes ``$V\subseteq\mathbb{F}_q^n$''.

%of translations: the whole work is developed considering only basic definitions of linear algebra. The applications to coding theory, and the term ``code'' will be mentioned again only in last section.

This work is organized as follows. In Section \ref{secposet} we introduce the basic concepts of this work (poset metrics and $P$-decomposition) and describe an algorithm for decomposing a code.  In Section \ref{sec:refinement} we show that the decomposition of a subspace is ``well behaved'' in the sense that when different posets are comparable, so are the corresponding decompositions. Using this fact and the knowledge about hierarchical poset metrics, in part \ref{sub:hierar_bouds} we produce bounds for the degree of a maximal $P$-decomposition of a code, where $P$ is an arbitrary poset. Finally, on Section \ref{sec:applications} we go back to the coding ambient and give some applications: the determination of the packing radius (part \ref{sub:pack}) and the possible simplification of syndrome decoding algorithm  (part \ref{sub:syndrome}).




%In the referred cases of NRT and hierarchical posets, by operating with the columns of a generator matrix (performing operations determined by the group of linear isometry), we can get a generator matrix that in many senses may be called \emph{canonical}. The canonical matrix determines a \emph{canonical decomposition} of a code into a direct sum of sub-codes with dimension and support uniquely prescribed by the code weight hierarchy, see Corollary 1 of Theorem 1 in \cite{felix2012canonical}. For a general poset, there is no such canonical decomposition, but there is a decomposition that is canonical in other sense, namely, it is maximal in the number of components. 
%In the sequence, we will define and determine what we call by a maximal $P$-decomposition. 
%This decomposition is what allows to define canonical forms for linear codes over any poset metric and to produce bounds for invariants that cannot be related or produced by explicit expressions as in the hierarchical case.






\section{Poset Metrics and Decomposition of Subspaces}\label{secposet}

This section has three parts. In the first part we summarize the basic concepts about poset metrics. In the second we introduce a new concept, object of study of this work: how different poset metrics allow different decompositions of a subspace. After doing so, we introduce the maximal and the primary $P$-decompositions of a subspace. The third part is devoted to an algorithm to find a maximal $P$-decompositions.

%the decompositions of a subspace allowed results of this work: We start this section defining  introducing the concept of poset metrics. s section we introduce the basic concepts and definitions needed in this work, concerning finite partial ordered sets (posets) and the metrics induced by posets on finite dimensional vector spaces over finite fields.

\subsection{Posets and Metrics}  \label{sub:poset}

Let $P=([n],\leqslant_P)$ be a partially ordered set (or poset), where  $[n]:=\{1,\ldots,n\}$ and $\leqslant_P$ is an order relation. We may denote the order relation only as $a\leqslant b$ if the poset is immaterial or clear in the context. A set $I\subset [n]$ is an \textit{order ideal} of $P$ if for every $x\in I$ and $y\in[n]$ with $y\leqslant_P x$ implies $y\in I$. Given  $E \subseteq [n]$, the smallest ideal  of $P$ containing $E$ is denoted by $\langle E \rangle_P$ and called the \textit{ideal generated by} $E$. The maximal elements (according to $P$) of $E$ will be denoted by $\mathcal{M}(E)$. In case $E=\{a\}$ is a singleton, we denote $\langle E \rangle_P=\langle a \rangle_P$.

An \emph{order isomorphism}  $f:P\rightarrow Q$ between posets $P$ and $Q$ over $[n]$ is a bijection $f:[n]\rightarrow [n]$ such that $a\leqslant_P b$ if, and only, if $f(a)\leqslant_Q f(b)$, for all  $a,b\in [n]$.   In the case $P=Q$, $f$ is said to be a $P$-automorphism. The group of all automorphisms of $P$ will be denoted by $Aut(P)$.

Given a poset  $P=([n],\leqslant_P)$ and a subset $X\subset [n]$, considering the order on $X$ inherited from $P$, we say that $(X,\leqslant_P) $ is a \emph{sub-poset} of $P$ and denote $X\subseteq P$.
A \emph{chain} is a poset that is totally ordered, that is, for any $a,b\in [n]$, either $a\leqslant b$ or $b\leqslant a$. An \emph{anti-chain} is a poset with no relations excepts the trivial relations $a\leqslant a$. 


Given $a\in P$, the \emph{height} of $a$ according to $P$ is the maximal length of a chain in $P$ that has $a$ as a maximal element, i.e.,
\[
	h(a)=\max \{|C| \ : \ C\subseteq P \text{ is a chain }  \text{ and } b\leqslant_P a \ \forall \ b\in C\},
\] 
and the \emph{height of $P$} is $h(P)=\max \{h(a):a\in[n]\}$.
The $i$-th level $\Gamma_P^i$ of P is the set of all elements with height $i$, i.e.,
$$\Gamma_P^i = \{a \in P : h(a) = i\}.$$

We remark that each level  $\Gamma_P^i$ is a chain  and the extremal condition of chains can be grasped from the fact that $h(P)=n$ if, and only if, $P$ is a chain or, equivalently, if every level satisfies  $| \Gamma_P^i|=1$. Similarly, for an anti-chain, we have $h(P)=1$ and $| \Gamma_P^1|=n$. If $X\subseteq P$ is a chain or an anti-chain, we say that $X$ is a chain or anti-chain \emph{in} $P$. If $X$ is a chain (anti-chain), we call its cardinality $|X|$ the \emph{length} of the chain (anti-chain).

 
A broader class of posets, containing both anti-chain and chain posets, is the class of hierarchical posets. We say that $P = ([n], \leqslant_P )$ is \emph{hierarchical} if elements at different levels are always comparable, i.e., $a \leqslant_P b$ for every $a\in\Gamma_P^i$ and $b\in \Gamma_P^j$ where $1 \leq i < j \leq h(P)$. This is an interesting class of posets that will play a central role in the applications to coding theory, as we shall see in Section \ref{sec:applications}.

%\subsection{Poset Metrics and Codes}
\medskip
We now show how a poset determines a metric over a finite-dimensional vector space. Due to the primary concern to applications in coding theory, we will restrict ourselves to the case of finite fields, so we let $\mathbb{F}_q$ be the finite field with $q$ elements and $\mathbb{F}_q^n$ be the vector space of all $n$-tuples over $\mathbb{F}_q$. A $k$-dimensional subspace  $\mathcal{C}\subset \mathbb{F}_q^n$ is called an $[n,k]$-\textit{linear code} or, simply a \textit{code} when the parameters are either clear from the context or not relevant.

\medskip

 Given a vector $v=(v_1,\ldots,v_n)\in\mathbb{F}_q^n$, its \emph{support} is the set of all non-null coordinates: $supp(v)=\{i\in [n]:v_i\neq 0\}$.  Given a poset $P$ over $[n]$, the \emph{poset weight} (or $P$\emph{-weight}) of an element $v\in\mathbb{F}_q^n$ is the cardinality of the ideal generated by its support, i.e., $$w_{P}(v)= |\langle supp(v)\rangle_P|.$$
The \emph{poset distance} (or $P$\emph{-distance}) $d_P$ is the distance function over $\mathbb{F}_q^n$ induced by the $P$-weight, in other words, if $u,v\in\mathbb{F}_q^n$, then $$d_P(u,v)=w_P(u-v).$$ The poset distance was introduced by Brualdi et.al. \cite{brualdi1995codes} and it is immediate to prove that $(\mathbb{F}_q^n,d_P)$ is a metric space. The space $(\mathbb{F}_q^n,d_P)$ is called $P$\emph{-space} and the metric $d_P$ is called $P$\emph{-metric}.





A linear \emph{$P$-isometry} is a linear map $T:\mathbb{F}_q^n\rightarrow \mathbb{F}_q^n$ preserving the $P$-weight, and hence the $P$-distance. Two codes $\mathcal{C}_1$ and $\mathcal{C}_2$ over $\mathbb{F}_q^n$ are said to be \emph{$P$-equivalent} if there is a linear isometry $T$ such that $T(\mathcal{C}_1)=\mathcal{C}_2$. 
This is clearly an equivalence relation on the set of all codes and to determine the equivalence classes we need to know what are the linear $P$-isometries of the space.
The group of all linear $P$-isometries over $\mathbb{F}_q^n$ is denoted by $GL_P(\mathbb{F}_q^n)$, and it  is described by the next proposition.



\begin{proposition}[\cite{panek2008groups}]\label{propos1}
	Let $P$ be a poset over $[n]$. Given $T\in GL_P(\mathbb{F}_q^n)$, the map $\phi_T(i)=\mathcal{M}(supp(T(e_i)))$ is a $P$-automorphism. Furthermore, $T\in GL_P(\mathbb{F}_q^n)$ if, and only if,  
	\[
	T(e_i)=\sum_{i\leqslant_P j} x_{ij}e_{\phi_T(i)},
	\]
	where $x_{ij}$ are scalars satisfying $x_{jj}\neq 0$ for every $j\in [n]$.
\end{proposition}

Let $\mathcal{G}_P$ be the subgroup of all linear isometries $T$ such that $\phi_T=id$. Considering the subgroup of linear isometries induced by the automorphisms of $P$ (the permutation part), witch is commonly denoted by $\mathcal{A}ut(P)$, in \cite{panek2008groups}, it was proved that 
\[
GL_P(\mathbb{F}_q^n)=\mathcal{G}_P\rtimes \mathcal{A}ut(P).
\]% \section{Canonical Form for Hierarchical Metrics}

%By using this characterization we aim to construct the canonical form for general posets in a way that it extend the ones encountered in the literature for particular classes of posets.


 


% In \cite{felix2012canonical}, it was proposed a canonical-systematic form for codes over spaces endowed with a hierarchical poset metric. In this section, we will present an alternative way to obtain the canonical-systematic form emphasizing the role of the basis of the code instead of the generating matrix. When using the generator matrix, the focus is on the form of the matrix, here, an particular form may be obtained in some cases by the choice of an appropriate basis which is determined by a decomposition. Consequently, a particular form for the matrix is not the main goal, the goal is to obtain a generator matrix as simple as possible. 

% Let $P$ be a hierarchical poset over $[n]$. Given $w\in\mathbb{F}_q^n$, the $P$\textit{-clean} of $w$ is the vector $\widetilde{w}$ with the same value of $w$ in the coordinates that are maximal in the support of $w$ and zero in the remaining coordinates, namely: $\widetilde{w}_i=w_i$ if $i\in Max(w)$ and $\widetilde{w}_i=0$ otherwise. Note that the $P$-clean of $w$ has the same $P$-weight of $w$. The $j$-th projection of $w$ is the vector $w^{(j)}\in\mathbb{F}_q^n$ obtained by the projection of $w$ into the coordinates corresponding to the $j$-th level of $P$, i.e., ${w^{(j)}}_i=w_i$ if $i\in\Gamma_P^j$ and ${w^{(j)}}_i=0$, otherwise. In the following lemma and theorem, if $w\in\mathbb{F}_q^n$, $\langle w \rangle$ denotes the one-dimensional space generated by $w$ (not to be confused with the ideal generated by the support of $w$). 

% \begin{lemma}\label{lem01}
% Let $P$ be a hierarchical poset with $s$ levels over $[n]$ and $\mathcal{C}$ be a $l$-dimensional code satisfying $supp(\mathcal{C})\subset \Gamma_P^{i_0}$ for some $i_0\in\{1,\ldots,s\}$. Given $w\in\mathbb{F}_q^n$ such that $Max(w)\subset \Gamma_P^{i_0}$ and $\widetilde{w}\not\in \mathcal{C}$, there exists a linear code $\mathcal{C}^{\prime}$ such that $\mathcal{C}^{\prime}\sim_P\mathcal{C}\oplus\langle w \rangle$ and $supp(\mathcal{C}^{\prime})\subset \Gamma_P^{i_0}$.
% \end{lemma}


% \begin{IEEEproof}
% Let $\{v^1,\ldots,v^l\}$ be a basis of $\mathcal{C}$. Given $w$ as in the statements of the lemma, since $\widetilde{w}\not\in \mathcal{C}$, the set $\beta=\{\widetilde{w},v^1,\ldots,v^l\}$ is linearly independent. So, $\beta$ is a basis for the linear code $\mathcal{C}\oplus \langle \widetilde{w} \rangle$. Let 
% $$\beta_1 =\{\widetilde{w},v^1,\ldots,v^l,e_{j_1},\ldots, e_{j_{n-l-1}}\}$$ 
% be a basis of $\mathbb{F}_q^n$ obtained by extending the basis $\beta$ using vectors of the canonical basis. 

% Because $w=\widetilde{w}+\sum_{i=1}^{n-l-1} \alpha_i e_{j_{i}}$ for suitable scalars $\alpha_i$, the set 
%  $$\beta_2=\{w,v^1,\ldots,v^l,e_{j_1},\ldots, e_{j_{n-l-1}}\}$$ 
% generates $\mathbb{F}_q^n$. Furthermore, note that $\beta_2$ contains a basis of $\mathcal{C}\oplus\langle w \rangle$. Define the linear map $T$ by setting $T(w)=\widetilde{w}$, $T(v^i)=v^i$ for all $i\in\{1,\ldots,l\}$ and $T(e_{j_r})=e_{j_r}$ for all $r\in\{1,\ldots,n-l-1\}$. Denoting by $\mathcal{C}^\prime$ the code generated by $\beta$, we have that $supp(\mathcal{C}^\prime)\subset \Gamma_P^{i_0}$ and $T(\mathcal{C}\oplus \langle w \rangle)=\mathcal{C}^\prime$. To conclude, we just need to prove that $T$ is an isometry. Writing a canonical vector $e_j\in\mathbb{F}_q^n$ according to $\beta_2$ where $j\not\in \{j_1,\ldots,j_{n-l-1}\}$, we get that 
% $$e_j=\alpha w + \sum_{i=1}^l \gamma_i v^i + \sum_{i=1}^{n-l-1} \theta_i e_{j_i},$$
% where $\alpha,\gamma_i,\theta_i \in\mathbb{F}_q$. Since $w=\widetilde{w}+\sum_{i=1}^{n-l-1} \alpha_i e_{j_{i}}$ and $\alpha_i=0$ if $j_i\in\Gamma_P^r$ with $r\geq i_0$ ($\widetilde{w}$ is the $P$-clean of $w$), then
% 	\begin{align*}
% 		T(e_j) &=\alpha \widetilde{w} + \sum_{i=1}^l \gamma_i v^i + \sum_{i=1}^{n-l-1} \theta_i e_{j_i}\\
% 			&=\alpha \left(w- \sum_{i=1}^{n-l-1} \alpha_ie_{j_i}\right)+ \sum_{i=1}^l \gamma_i v^i + \sum_{i=1}^{n-l-1} \theta_i e_{j_i}=e_j-\sum_{i=1}^{n-l-1} \alpha\alpha_i e_{j_i}.
% 	\end{align*}
% Due to the fact that $P$ is hierarchical and $\alpha_i= 0$ for every $i$ such that $j_i\in\Gamma_P^r$ with $r\geq i_0$, the characterization given in Lemma \ref{lem04} ensures that $T$ is a linear isometry.
% \end{IEEEproof}

% \begin{observation}\label{obs01}
% The linear isometry $T$ constructed in the previous lemma coincides with the identity map when restricted to elements whose support does not intercept the level $i_0$, i.e., $T(x)=x$ if $supp(x)\subset [n]\setminus \Gamma_P^{i_0}$.	
% \end{observation}

% \begin{theorem}\label{th01}
% Let $P$ be an $(n:n_1,\ldots,n_s)$ hierarchical poset. If $\mathcal{C}$ is a linear $P$-code, there exists $\widetilde{\mathcal{C}}$ such that $\widetilde{\mathcal{C}}\sim_P \mathcal{C}$,  
% $$\widetilde{\mathcal{C}}=\mathcal{C}_1\oplus \mathcal{C}_2 \oplus \cdots \oplus \mathcal{C}_s$$
% and $supp(\mathcal{C}_i)\subset \Gamma_P^i$ for every $i\in [s]$.
% \end{theorem}
% \begin{IEEEproof}
%  If $\mathcal{C}$ is an one-dimensional code,  then $\mathcal{C}=\langle v \rangle$ for a suitable $v\in\mathbb{F}_q^n$. Considering $\mathcal{C}^\prime=\{\mathbf{0}\}$ to be the null vector space, since $v\notin \mathcal{C}^\prime$, Lemma \ref{lem01} ensures that $\mathcal{C}$ is equivalent to the code generated by the $P$-clean of $v$. Suppose $\mathcal{C}$ is a $k$-dimensional code and $k>1$. Then $ \mathcal{C}=\langle w \rangle\oplus\mathcal{C}^\prime$ for some $w\in\mathcal{C}$ and a $(k-1)$-dimensional code $\mathcal{C}^\prime\subset \mathcal{C}$. By induction, there is a linear isometry $T^\prime$ such that $T^\prime( \mathcal{C}^\prime)=\oplus_{i=1}^s B_i$ and $supp(B_i)\subset \Gamma_P^i$. Since $T^\prime$ is injective, we get that $T^\prime(w)\not\in T^\prime( \mathcal{C}^\prime)$. Consider the code $T^\prime( \mathcal{C})=\langle T^\prime(w)\rangle\oplus T^\prime( \mathcal{C}^\prime)$. Therefore, there exists a level $i$ of $P$ such that the projection of $T^\prime(w)$ in this level does not belong to $B_i$, i.e, $T^\prime(w)^{(j)}\not\in B_i$. Let $i_0$ be the maximal level with this property. Define the vector $v\in\mathbb{F}_q^n$ as follows: $v^{(i)}=T^\prime(w)^{(i)}$ if $i\leq i_0$ and $v^{(i)}=\mathbf{0}$ if $i>i_0$. Since $v=T^\prime(w)-c$ for some $c\in T^\prime(\mathcal{C}^\prime)$ we get that $T^\prime( \mathcal{C})=\langle v \rangle \oplus T^\prime( \mathcal{C}^\prime)$. By Lemma \ref{lem01}, there is a linear isometry $T$ such that $T(B_i)=B_i$ if $i\neq i_0$ (ensured by the Observation \ref{obs01}) and $supp(T(B_{i_0}\oplus \langle v \rangle))=supp(T(B_{i_0})\oplus \langle \widetilde{v} \rangle)\subset \Gamma_P^{i_0}$ where $T(v)=\widetilde{v}$. Therefore, denoting $\mathcal{C}_i=B_i$ for every $i\neq i_0$ and $\mathcal{C}_{i_0}=T(B_{i_0})\oplus \langle \widetilde{v} \rangle$, we have that $\widetilde{\mathcal{C}}=TT^\prime(\mathcal{C})=\oplus_{i=1}^s \mathcal{C}_i$ and $supp(\mathcal{C}_i)\subset \Gamma_P^i$ for every $i\in\{1,\ldots,s\}$.
% \end{IEEEproof}

% Given a linear code $\mathcal{C}$, Theorem \ref{th01} states that there exists a code $\widetilde{\mathcal{C}}$, equivalent to $\mathcal{C}$, such that $\widetilde{\mathcal{C}}=\mathcal{C}_1\oplus\ldots\oplus\mathcal{C}_s$ and $supp(\mathcal{C}_i)\subset \Gamma_P^i$ for every $i\in\{1,\ldots,s\}$. Assuming $P$ to be naturally labeled, the direct sum can be seen as a product of codes, namely, 
% \[
% 	\widetilde{\mathcal{C}}=\mathcal{C}_1\oplus\ldots\oplus\mathcal{C}_s= (\widehat{\mathcal{C}_1},\ldots,\widehat{\mathcal{C}_s}),
% \]
% where the codes $\widehat{\mathcal{C}_i}$ were obtained from $\mathcal{C}_i$ just by deleting the coordinates that do not belong to the level $i$ of the poset (this is known as the punctured code construction, see \cite{huffman2003fundamentals}). Therefore, while $\mathcal{C}_i$ is a sub-code of $\mathbb{F}_q^n$, $\widehat{\mathcal{C}_i}$ is a sub-code of $\mathbb{F}_q^{n_i}$ where $n_i=|\Gamma_P^i|$.


% \begin{corollary}\label{col5}
%  	If $\mathcal{C}$ is a $P$-code where $P$ is a naturally labeled $(n:n_1,\ldots,n_s)$ hierarchical poset, there is a code $\mathcal{C}^\prime$, equivalent to $\mathcal{C}$, with generator matrix $G$ in the form
%  		$$G=\left[
% 	\begin{array}{ccccc}
% 		\mathbf{0} &\mathbf{0}& \mathbf{0} & \cdots& G_s\\
% 		\mathbf{0} & \mathbf{0} &  & \text{\reflectbox{$\ddots$}} & \mathbf{0} \\
% 		\vdots & \vdots &  &  & \vdots \\
% 		\mathbf{0} & G_2 & \mathbf{0} & \cdots & \mathbf{0} \\
% 		G_1 & \mathbf{0} & \mathbf{0} & \cdots & \mathbf{0}
% 	\end{array}\right],
% 	$$
% 	where $G_i$ is the generator matrix of $\widehat{\mathcal{C}_i}$.
%  \end{corollary} 


% The representation given by Corollary \ref{col5} can be standardized even more. Indeed, by operating in the rows of $G$ we can assume that $G_i$ is in reduced row echelon form, note that this operations only perform changing of basis in the code. If $T\in\mathcal{A}ut(P)$, according to Example \ref{exampleh}, $T$ is a composition of permutations according to each level of the poset. 

% In terms of matrices, assuming that the generator matrix $G$ of a code $\mathcal{C}$ is in the form given by Corollary \ref{col5} and that each $G_i$ is in reduced row echelon form, the description of $\mathcal{A}ut(P)$ ensures that any two rows of $G$ can be permuted if, and only if, the coordinates corresponding to these rows belong to the same level of the poset. Therefore, if $P_i$ are $n_i\times n_i$ permutation matrices, the code generated by
% $$G^\prime=\left[
% 	\begin{array}{ccccc}
% 			\mathbf{0} &\mathbf{0}& \mathbf{0} & \cdots& G_sP_s\\
% 		\mathbf{0} & \mathbf{0} &  & \text{\reflectbox{$\ddots$}} & \mathbf{0} \\
% 		\vdots & \vdots &  & & \vdots \\
% 		\mathbf{0} & G_2P_2 & \mathbf{0} & \cdots & \mathbf{0} \\
% 		G_1 P_1 & \mathbf{0} & \mathbf{0} & \cdots & \mathbf{0} 
% 	\end{array}\right]
% 	$$
% 	is equivalent to $\mathcal{C}$. With the previous arguments, the following representation holds.
% \begin{corollary}\label{col6}
%  	If $\mathcal{C}$ is a $P$-code where $P$ is a naturally labeled $(n:n_1,\ldots,n_s)$ hierarchical poset, there is a code $\mathcal{C}^\prime$, equivalent to $\mathcal{C}$ with generator matrix $G$ given by 
%  		$$G=\left[
% 	\begin{array}{ccccc}
% 		\mathbf{0} &\mathbf{0} & \mathbf{0} & \cdots & [I_{k_s}|A_s]\\
% 		\mathbf{0} & \mathbf{0} &  & \text{\reflectbox{$\ddots$}} & \mathbf{0} \\
% 		\vdots & \vdots &  & & \vdots \\
% 		\mathbf{0} & [I_{k_2}|A_2] & \mathbf{0} & \cdots & \mathbf{0} \\
% 		\left[I_{k_1}|A_1\right] & \mathbf{0} & \mathbf{0} & \cdots & \mathbf{0}
% 	\end{array}\right]
% 	$$
% 	where $k_i$ is the dimension of $\widehat{\mathcal{C}_i}$ and $A_i$ are $k_i\times (n_i-k_i)$ matrices. This representation is called the \index{canonical-systematic form}\textit{canonical-systematic form}. 
%  \end{corollary} 

% As may be seen in \cite{felix2012canonical}, the constants $k_1,\ldots,k_s$ are determined by the weight enumerator of the code and, in this sense, the decomposition is canonical.




\subsection{Partitions and Decompositions}\label{sub:parti}

A \index{partition}\textit{partition} of a subset $J\subseteq\left[  n\right]$ is a family of non-empty subsets $\{J_1,\ldots,J_r\}$ such that  
$$J=\bigcup_{i=1}^{r}J_{i} \text{ and } J_i\cap J_j =\emptyset \text{ for every } i\neq j.$$
We will denote such partition by $\mathcal{J}=(J_{i})_{i=1}^r$. The triple $\mathcal{J}^{\ast}=\left(J;J_0;J_{i}\right)_{i=1}^r$ where 
$J_{0}=\left[  n\right]  \backslash J=\left\{  i\in\left[  n\right]  \ : \ i\notin
J\right\} $ is called \emph{pointed partition}. Since $J$ is the union of the subsets $J_i$, the pointed partition $\mathcal{J}^{\ast}$ is completely determined once the pair $\left(J_0;J_{i}\right)_{i=1}^r$ is given, so we may also write $\mathcal{J}^{\ast}=\left(J_0;J_{i}\right)_{i=1}^r$. Note that $J_{0}=\emptyset$ if, and only if, $J=\left[  n\right]$. We stress that the \emph{pointer} $J_{0}$ has a
special role, since it is the only part we allow to be empty. From now on, we consider only pointed partitions, hence we will omit the symbol $^{\ast}$ and the adjective ``pointed''. 

A partition $\mathcal{J}$  can be
refined in two ways: either by increasing the number of parts or by enlarging
the distinguished part $J_{0}$. Except for the pointer
$J_{0}$, the order of the other parts is irrelevant, for example,
\[
\left(  J_{0};\left\{  1,2\right\}  ,\left\{  3,4,5\right\}  \right)  =\left(
J_{0};\left\{  5,4,3\right\}  ,\left\{  1,2\right\}  \right)  \text{.}%
\]


\begin{definition}
Given a partition $\mathcal{J}=\left(J_{0};J_{i}\right)_{i=1}^{r}$, a \emph{split of} $\mathcal{J}$ is a partition $\mathcal{J}^{\prime
}=(  J_{0};J_{i}^{\prime})_{i=1}^{r+1}$ where $J_{l}=J_{l}^{\prime}\cup J_{r+1}^{\prime}$ for some $l\in[r]$ and $J_{i}=J_{i}^{\prime}$ for each $i\neq l$.
This means that $J_l$ is split into two components and the others are unchanged. 
An \emph{aggregate} of $\mathcal{J}$ is a partition $\mathcal{J}^{\prime}=(  J_{0}^{\prime}%
;J_{i}^{\prime})  _{i=1}^{r}$ where for some $l\in[r]$, $J_{i}^{\prime}=J_{i}$ if $i\not\in\{l,0\}$, $J_{l}=J_{l}^{\prime}\cup J_{l}^{\ast}$ and $J_{0}^{\prime}=J_{0}\cup
J_{l}^{\ast}$ for some $\emptyset\neq J_{l}^{\ast}\varsubsetneq J_{l}$, i.e., some elements of $J_{l}$ were aggregated into the distinguished part $J_{0}$.
\end{definition}

\begin{definition}\label{defdes}
We say that a partition $\mathcal{J}^{\prime}$ is a $1$\emph{-step refinement} of $\mathcal{J}$ if $\mathcal{J}^{\prime}$ is obtained from $\mathcal{J}$
either by a splitting or by aggregating only one element. The partition $\mathcal{J}^{\prime}$ is a \emph{refinement of} $\mathcal{J}$ if $\mathcal{J}^{\prime}$ can be obtained
from $\mathcal{J}$ by a successive number of $1$-step refinements and, if that is the case, we use the
notation $\mathcal{J} \geq \mathcal{J}^{\prime}$.
%and $ \mathcal{J} \geq_{l} \mathcal{J}^{\prime}$ to denote that $\mathcal{J}^{\prime }$ is a $1$-step refinement of $\mathcal{J}$ performed by an $l$-split or $l$-aggregate. When the kind of operation (splitting or aggregation) is relevant, we will use the notation $\mathcal{J} \geq_{l}^{s} \mathcal{J}^{\prime}$ and $\mathcal{J} \geq_{l}^{a}\mathcal{J}% ^{\prime}$ for an $l$-split or an $l$-aggregate, respectively.
\end{definition}

\begin{example}\label{exdec}
The partition $([4];\emptyset ; \{1,2,3,4\})$ can be refined in order to get the partition $([4];\{1,3\};\{2\},\{4\})$ by using the following $1$-step refinements:
%\begin{align*}
$$\left(  \emptyset;\left\{  1,2,3,4\right\}  \right)   \geq\left( 
\left\{  3\right\}  ;\left\{  1,2,4\right\}  \right)  \geq\left(
\left\{  1,3\right\}  ;\left\{  2,4\right\}  \right)  \geq\left(
\left\{  1,3\right\}  ;\left\{  2\right\}  ,\left\{  4\right\}  \right).
$$%\end{align*}
\end{example}


Set partitions and refinement operations allow us to define decompositions of codes.

\begin{definition}
\label{code_decomposition}We say that $\mathscr{C}=\left(  \mathcal{C};\mathcal{C}_{0};\mathcal{C}_{i}\right)  _{i=1}^{r}$ is a \index{code!decomposition}\emph{decomposition of} an $[n,k,\delta]_q$ code $\mathcal{C}$ if each
$\mathcal{C}_{i}$ is a subspace of $\mathbb{F}_{q}^{n}$ and

\begin{itemize}
\item[(a)] $\mathcal{C}=\oplus_{i=1}^{r}\mathcal{C}_{i}$ with $dim(\mathcal{C}_{i})  >0$ for every $i\in [r]$;
\item[(b)] $\mathcal{C}_{0}=\left\{  \left(  x\,_{1},x_{2},\ldots,x_{n}\right) \ : \ x_{i}=0\text{ if }  i\in supp\left(  \mathcal{C}\right)  \right\}$;
\item[(c)] $\left(supp\left(  \mathcal{C}_{0}\right)  ;supp\left(
\mathcal{C}_{i}\right)  \right)  _{i=1}^{r}$ is a partition over $[n]$.
\end{itemize}
\end{definition}

\begin{definition}
A split, aggregate, $1$-step refinement and a refinement $\mathscr{C}%
^{\prime}=(  \mathcal{C};\mathcal{C}_{0}^{\prime};\mathcal{C}_{i}^{\prime})  _{i=1}^{r\prime}$ of
a decomposition $\mathscr{C}=\left(  \mathcal{C};\mathcal{C}_{0};\mathcal{C}_{i}\right)  _{i=1}^{r}$ are
defined according to
$
(  supp (  \mathcal{C}_{0}^{\prime} )  ;supp(
\mathcal{C}_{i}^{\prime})  )  _{i=1}^{r\prime}%
$
being a split, aggregate, $1$-step refinement or a refinement of
$\left(  supp\left( \mathcal{C}_{0}\right)  ;supp\left(
\mathcal{C}_{i}\right)  \right)  _{i=1}^{r}$ respectively. We will also use the notation $\mathscr{C}\geq \mathscr{C}^\prime$ to denote a refinement.
\end{definition}


\begin{example}
	Let $P$ be a poset over $[4]$. Consider the $[4,2,\delta_P]_2$ code $\mathcal{C}$ given by
	\[
	 	\mathcal{C}=\{0000,1100,0010,1110\}.
	  \] 
	  Then,
	  \[
	  	(\mathcal{C}; \langle e_4 \rangle; \mathcal{C})\geq (\mathcal{C}; \langle e_4 \rangle; \mathcal{C}_i)_{i=1}^2  
	  \]
	  where
	  \[
	  	\mathcal{C}_1=\{0000,1100\} \text{ and } \mathcal{C}_2=\{0000,0010\}.
 	  \]
\end{example}

\begin{definition}
	A decomposition $\mathscr{C}=(\mathcal{C};\mathcal{C}_0;\mathcal{C}_i)_{i=1}^r$ is said to be \index{maximal decomposition}\textit{maximal} if it does not admit a refinement.
\end{definition}

Until now, only the algebraic aspects of the codes were used, the metric $d_{P}$ has not played any role in the decomposition of a code. We introduce now a decomposition that depends of the metric and consequently of the poset $P$.  

\begin{definition}
\label{P_decomposition} A \index{code!$P$-decomposition}$P$-\emph{decomposition of} $\mathcal{C}$ is a decomposition 
$\mathscr{C}=(  \mathcal{C}^{\prime};\mathcal{C}_{0}^{\prime};\mathcal{C}_{i}^{\prime
})  _{i=1}^{r}$ of
$\mathcal{C}^{\prime}$ (as in Definition \ref{code_decomposition}) where $\mathcal{C}^{\prime}\sim_{P}\mathcal{C}$. Each $\mathcal{C}_{i}^{\prime}$ is called a \emph{component }of the decomposition. A 
\emph{ trivial }$P$\emph{-decomposition} of $\mathcal{C}$ is either the decomposition
$\left(  \mathcal{C};\mathcal{C}_{0};\mathcal{C}\right)  $ or any $P$-decomposition with a unique factor
$(  \mathcal{C}^{\prime};\mathcal{C}_{0}^{\prime};\mathcal{C}^{\prime})  $ where $\vert
supp(  \mathcal{C}^{\prime})  \vert =\left\vert supp%
\left(  \mathcal{C}\right)  \right\vert $ and $\vert supp(
\mathcal{C}_{0}^{\prime})  \vert =\left\vert supp\left(
\mathcal{C}_{0}\right)  \right\vert $.
\end{definition}


\begin{definition}
A code $\mathcal{C}$ is said to be $P$\emph{-irreducible} if it does not admit a non-trivial $P$-decomposition.
\end{definition}

% \begin{example}\label{ex3poset}
% 	Consider the $[4,2,\delta_P]_q$ code $\mathcal{C}$ given by
% 	\[
% 		\mathcal{C}=\{0000,1110,0111,1001\}.
% 	\]
% 	Let $P_1$ be the $(4:2,2)$ hierarchical poset, $P_2$ be the anti-chain poset and $P_3$ be the poset determined by $2\leq_{P_3}3$ and $2\leq_{P_3}4$. Their Hasse diagrams are as follows:
		
% 		\begin{figure}[h]
% 	\centering
% 		\includegraphics[width=.6\textwidth]{figuras/ex.pdf}
% 	\end{figure}
% \noindent It is straightforward that $\mathcal{C}$ does not admit a non-trivial $P_2$-decomposition, then $\mathcal{C}$ is $P_2$-irreducible. If we consider the $d_{P_3}$-isometry given by
% \[
% 	(x_1,x_2,x_3,x_4)\mapsto (x_1,x_2+x_3,x_3,x_4),
% \]
% then
% \[
% 	\mathscr{C}^\prime = (\{0000,1010,0011,1001\};\langle e_2\rangle;\{0000,1010,0011,1001\}).
% \]
% is a $P_3$-decomposition of $\mathcal{C}$. Note that the previous isometry is also a $d_{P_1}$-isometry, hence $\mathscr{C}^\prime$ is also a $P_1$-decomposition of $\mathcal{C}$. Considering the $d_{P_1}$-isometry given by
% \[
% 	(x_1,x_2,x_3,x_4)\mapsto (x_1+x_3+x_4,x_2,x_3,x_4),
% \]
% we get that
% $$
% \mathscr{C}^{\prime\prime} =(\{0000,0010,0011,0001\};\langle e_1,e_2\rangle;\{0000,0010\}\oplus\{0000,0001\})
% $$
% is also a $P_1$-decomposition for $\mathcal{C}$. 
% \end{example}

\begin{example}\label{exemplo3}
	Let $P$ be the hierarchical poset with order relations $1,2,3\leqslant 4$. The codes 
\[
	\mathcal{C}=\{0000,1001\} \ \text{ and }\ \mathcal{C}^\prime= \{0000,0111\}
\]
are equivalent since
\[
	T(e_1)=e_1, \ T(e_2)=e_2, \ T(e_3)=e_3, \ T(e_4)=e_1+e_2+e_3+e_4
\]
is an isometry satisfying $T(\mathcal{C})=\mathcal{C}^\prime$. Then, $\mathscr{C}^\prime=(\mathcal{C}^\prime; \langle e_1 \rangle; \mathcal{C}^\prime)$ is a $P$-decomposition of $\mathcal{C}$ while $\mathscr{C}=(\mathcal{C};\langle e_2, e_3 \rangle; \mathcal{C})$ is a decomposition of $\mathcal{C}$. 
% \[
% 	S(e_1)=e_1, \ S(e_2)=e_2, \ S(e_3)=e_3, \ S(e_4)=e_1+e_3+e_4+e_2
% \]
% are isometries satisfying $T(\mathcal{C})=\mathcal{C}^\prime=S(\mathcal{C})$. 
\end{example}

We note that if we consider the partitions $([4];\{2,3\};\{1,4\})$ and $([4];\{1\};\{2,3,4\})$ induced by the $P$-decompositions $\mathscr{C}$ and $\mathscr{C}^\prime$ constructed in the previous example, these partitions can not be obtained from each other by a sequence of aggregations and splittings. Hence, we must use the order automorphism induced by the isometries in order to compare them. We now do it explicitly.




% Let $\beta=\left\{  e_{1},\ldots,e_{n}\right\}  $ be the canonical basis of $\mathbb{F}_q^n$. Given $I\subset\left[
% n\right]$, the $I$-\emph{coordinate subspace} $V_I$ is defined by    
% \[
% V_I=\langle\left\{e_i \ : \ i\in I\right\}\rangle =\left\{  \sum_{i\in I}x_{i}e_{i} \ : \ x_i\in \mathbb{F}_q\right\} .
% \]
% Given a decomposition $\mathscr{C}=(\mathcal{C};\mathcal{C}_0;\mathcal{C}_i)_{i=1}^r$ of a linear code $\mathcal{C}$, we say that 
% \begin{center}
% $
% V_{i}:= V_{supp(\mathcal{C}_i)}=\langle \left\{e_i \ : \ i\in supp\left(
% \mathcal{C}_{i}\right)\right\} \rangle $
% \end{center}
% is the \emph{support-space of (the component) }$\mathcal{C}_{i}$. We consider
% $\left[  n\right]  _{\mathcal{C}}=supp\left(  \mathcal{C}\right)  $ and $\left[
% n\right]  ^{\mathcal{C}}=\left[  n\right]  \backslash\left[  n\right]  _{\mathcal{C}}$. In the case where $\left[  n\right]  ^{\mathcal{C}}\neq\emptyset$, we  write 
% $V_{0}=V_{[n]^{\mathcal{C}}}$ and denote $\mathcal{C}_{0}=V_{0}$. We
% say that the decomposition $(\mathcal{C};\mathcal{C}_0;\mathcal{C}_i)_{i=1}^r$ is supported by the
% \emph{environment decomposition }$(V_0;V_i)_{i=1}^r$. In the case where $\left[
% n\right]  ^{\mathcal{C}}=\emptyset$, we have $V_{0}=\mathcal{C}_{0}=\left\{  \mathbf{0}\right\}  $.

% Given a $P$-decomposition $\mathscr{C}=(  \mathcal{C}^\prime;\mathcal{C}_{0}^{\prime};\mathcal{C}_{i}^{\prime})
% _{i=1}^{r}$  of $\mathcal{C}$, we have that $\left[  n\right]  =\cup_{i=0}^{r}supp\left(  V_{i}\right)  $. Also, if $\mathcal{C}_{i}^\prime=\left\{  \mathbf{0}\right\}$, then $ i=0$. If each $\mathcal{C}^\prime_i$ is $P$-irreducible, denoting $n_{i}=dim (V_{i})$
% and $k_{i}=dim (\mathcal{C}_{i}^{\prime})$, then 
% \begin{equation*}
% \sum_{i=0}^{r}n_{i}   =n=dim (\mathbb{F}_q^n )\ \text{ and } \ 
% \sum_{i=1}^{r}k_{i}=k=dim (\mathcal{C}).
% \end{equation*}

Let $\mathscr{C}=(
\mathcal{C}^{\prime\prime};\mathcal{C}_{0}^{\prime\prime};\mathcal{C}_{i}^{\prime\prime})  _{i=1}^{r}$ and
$\mathscr{C}^{\prime}=(  \mathcal{C}^{\prime};\mathcal{C}_{0}^{\prime
};\mathcal{C}_{i}^{\prime})  _{i=1}^{r^{\prime}}$ be two $P$-decompositions of a code $\mathcal{C}$. Associated to those
$P$-decompositions there are two  partitions of $\left[  n\right]  $,
namely: $(  supp(  \mathcal{C}_{0}^{\prime\prime})  ;supp%
(  \mathcal{C}_{i}^{\prime\prime}))  _{i=1}^{r}$ and $(supp(  \mathcal{C}_{0}^{\prime})  ;supp(\mathcal{C}_{i}^{\prime}))  _{i=1}^{r^{\prime}}$.
By the definition of a $P$-decomposition, there are isometries $T_1,T_2\in GL_{P}(\mathbb{F}_q^n)$ such that $T_1\left(  \mathcal{C}\right)  =
\mathcal{C}^{\prime\prime}$ and $T_2\left(  \mathcal{C}\right)  =\mathcal{C}^{\prime}$. Denote $T=T_2\circ\left(  T_1\right)  ^{-1}$. Then $T$ is a linear isometry and $T(\mathcal{C}^{\prime\prime})=\mathcal{C}^{\prime}$. Considering the automorphism $\phi_T$ of Proposition \ref{propos1} (the order automorphism induced by $T$), %$T$ induces an automorphism of order $\phi_{T}:\left[  n\right]  \rightarrow\left[  n\right] $. The automorphism 
$\phi_{T}$ induces a map on the  partition of $\left[  n\right]  $ determined by the $P$-decomposition $\mathscr{C}$, namely,
$$\phi_{T}[  (  supp(  \mathcal{C}_{0}^{\prime\prime})
;supp (  \mathcal{C}_{i}^{\prime\prime}))  _{i=1}^{r}]
=  \left(  \phi_{T}\left(  supp\left(  \mathcal{C}_{0}\right)
\right)  ;\phi_{T}\left(  supp\left(  \mathcal{C}_{i}\right)
\right)  \right)  _{i=1}^{r}.$$


Considering the map $T$ defined in Example \ref{exemplo3}, we may define $T_1=\text{identity}$ and $T_2=T$. Then,
$$\phi_{T} \left[([4];\{2,3\};\{1,4\})\right]=([4];\phi_{T}(\{2,3\});\phi_{T}(\{1,4\}))=([4];\{2,3\};\{1,4\})$$
is a partition which also can not be obtained by $([4];\{1\};\{2,3,4\})$ using an aggregation. Considering the isometry 
\[
	S(e_1)=e_3, \ S(e_2)=e_2, \ S(e_3)=e_1, \ S(e_4)=e_2+e_4
\]
we still have that $S(\mathcal{C}^{\prime\prime})=\mathcal{C}^\prime$ but now
$$\phi_{S} \left[([4];\{2,3\};\{1,4\})\right]=([4];\phi_{S}(\{2,3\});\phi_{S}(\{1,4\}))=([4];\{1,3\};\{2,4\})$$
is an aggregation of $([4];\{1\};\{2,3,4\})$. Hence, it may happen that $\mathscr{C}^{\prime}$ and $\mathscr{C}^{\prime\prime}$ may not be comparable for some $U\in GL_P(\mathbb{F}_q^n)$ but comparable for some $T\in GL_P(\mathbb{F}_q^n)$. Therefore, we can define the analogous of the operations on decompositions by  demanding the existence of such an isometry. 

\begin{definition}
Let $\mathscr{C}^{\prime}=(  \mathcal{C}^{\prime};\mathcal{C}_{0}^{\prime}%
;\mathcal{C}_{i}^{\prime})  _{i=1}^{r\prime}$ and $\mathscr{C}^{\prime\prime
}=(  \mathcal{C}^{\prime\prime};\mathcal{C}_{0}^{\prime\prime};\mathcal{C}_{i}^{\prime\prime})
_{i=1}^{r\prime\prime}$ be two $P$-decompositions of $\mathcal{C}$. We say that
$\mathscr{C}^{\prime}$ is \emph{a }$P$\emph{-refinement} of $\mathscr{C}^{\prime\prime}$ (and write $\mathscr{C} \geq \mathscr{C}^\prime$) if there is  $T\in GL_P(\mathbb{F}_q^n)$ such that $\phi_{T}[
(  supp(  \mathcal{C}_{0}^{\prime})  ;supp(
\mathcal{C}_{i}^{\prime}))  _{i=1}^{r\prime}]  $ is a refinement
of the partition $ (  supp(
\mathcal{C}_{0}^{\prime\prime})  ;supp(  \mathcal{C}_{i}^{\prime\prime
})  )  _{i=1}^{r^{\prime\prime}}$. 
\end{definition}


Since, for every $T\in GL_P(\mathbb{F}_q^n)$, the induced map $\phi_T$ is an automorphism, if $\mathscr{C}$ and $\mathscr{C}^\prime$ are comparable by $S$ and $T$ respectively, the number of aggregations and splittings used to obtain $\mathscr{C}^{\prime}$ from $\mathscr{C}^{\prime\prime}$ coincides when $S$ or $T$ are used to compare them. Hence, splittings and aggregations are well determined once two $P$-decompositions are given.

%Similar to what was done with set partitions in Definition \ref{defdes}, the symbols $\overset{P}{\geq_l^s}$ and $\overset{P}{\geq_l^a}$ specify when the refinement was obtained by an $l$-split or an $l$-aggregation, respectively. 


% \begin{example}
% Let $\mathcal{C}=\left\{  0000,1100,0011,1111\right\}$ be a $2$-dimensional code over $\mathbb{F}_2^4$ and $P$ be the chain poset determined by $1\leqslant 2 \leqslant 3 \leqslant 4$. Then, starting with the trivial $P$-decomposition, we have the following refinements:
% \begin{align*}
% &  \left(  \mathcal{C};\emptyset;\mathcal{C}\right)  \overset{P}{\geq_1^a}\left(  \left\{
% 0000,1100,0001,1101\right\}  ;\left\{  0000,0010\right\}
% ;\left\{  0000,1100,0001,1101\right\}  \right) \\
% &  \overset{P}{\geq_1^a}\left(  \left\{  0000,0100,0001,0101\right\}
% ;\left\{  0000,0010,1000,1010\right\}  ;\left\{  0000%
% ,0100,0001,0101\right\}  \right) \\
% &  \overset{P}{\geq_1^s}\left(  \left\{  0000,0100,0001,0101\right\}
% ;\left\{  0000,0010,1000,1010\right\}  ;\left\{  0000%
% ,0100\right\}  ,\left\{  0000,0001\right\}  \right)
% \end{align*}
% where the first two refinements were obtained by considering the linear $P$-isometries
% $$\left(  x_{1},x_{2},x_{3},x_{4}\right)   \mapsto\left(  x_{1},x_{2}%
% ,x_{3}-x_{4},x_{4}\right) $$
% and
% $$\left(  x_{1},x_{2},x_{3},x_{4}\right)  \mapsto\left(  x_{1}-x_{2}%
% ,x_{2},x_{3},x_{4}\right),$$
% respectively. The third refinement is just a splitting
% \[
% \left\{  0000,0100,0001,0101\right\}  =\left\{  0000,0100\right\}
% \oplus\left\{  0000,0001\right\}  \text{.}%
% \]
	
% \end{example}



\begin{definition}\label{com}
A $P$-decomposition $\mathscr{C}=\left(  \mathcal{C};\mathcal{C}_0;\mathcal{C}_{i}\right)_{i=1}^r$ is said to be \index{$P$-decomposition!maximal}\emph{maximal} if it can not be refined or, equivalently, if each $\mathcal{C}_{i}$ is $P$-irreducible for every $i\in[r]$.
\end{definition}

Let us consider the Hamming metric $d_{H}$ over $\mathbb{F}_2^n$. It is well-known that the group of linear isometries of this metric space is isomorphic to the permutation group $\mathcal{S}_{n}$. Given a code $\mathcal{C}$, let
$\mathscr{C}=(\mathcal{C};\mathcal{C}_0;\mathcal{C}_i)_{i=1}^r$ be a maximal decomposition of $\mathcal{C}$. If a code $\mathcal{C}^{\prime}$
is $d_H$-equivalent to $\mathcal{C}$, then there is $T\in GL_{d_H}(\mathbb{F}_q^n)\sim \mathcal{S}_n$ such that $T\left(
\mathcal{C}\right)  =\mathcal{C}^{\prime}$. Note that the decomposition $\mathscr{C}^\prime=(\mathcal{C}^\prime;T(\mathcal{C}_0);T(\mathcal{C}_i))_{i=1}^r$ is a maximal decomposition of
$\mathcal{C}^{\prime}$, otherwise, $\mathscr{C}$ would not be a maximal decomposition of $\mathcal{C}$. Therefore, when considering the Hamming metric, a maximal decomposition is also a maximal $H$-decomposition ($H$ is the anti-chain poset over $[n]$). This is not true in general, as we can see in Example \ref{exemplo3}.

% \begin{example}
% Consider $\mathcal{C}$ to be the $1$-dimensional binary code of length $n$ generated by $\left(
% 1,1,\ldots,1\right)\in\mathbb{F}_2^n$. Let $P$ be a poset defined by the chain
% order: $1\leqslant 2\leqslant \cdots\leqslant n$; and $H$ be the anti-chain order poset. It follows
% that $\mathcal{C}$ is $H$-irreducible but not $P$-irreducible. Indeed, by Lemma \ref{lem04}, the map
% \[
% T\left(  x_{1},\ldots,x_{n-1},x_{n}\right)  =\left(  x_{1}+x_{n},\ldots,x_{n-1}%
% +x_{n},x_{n}\right)
% \]
% is a $P$-isometry because $T(e_i)=e_i$ for every $i\neq n$ and $T(e_n)=\sum_{i=1}^n e_i$. Also, $T\left(  \mathcal{C}\right)=\langle e_n \rangle  $ is the code generated by the vector $e_{n}$, hence
% \[
% \mathscr{C}^{\prime}=(\langle e_n\rangle; \langle\{e_1,\ldots,e_{n-1}\}\rangle;\langle e_n\rangle)
% \]
% is a maximal $P$-decomposition of $\mathcal{C}$. Therefore, $\mathcal{C}$ is not $P$-irreducible. Since $\mathcal{C}$ is a one-dimensional code, we only can perform aggregations, but since $supp(11\ldots 1)=[n]$, aggregations change the Hamming weight, so that $\mathcal{C}$ is $H$-irreducible.
% \end{example}

\begin{definition}
Let $\mathscr{C}=\left(
\mathcal{C}^{\prime};\mathcal{C}_{0};\mathcal{C}_{i}\right)  _{i=1}^{r}$ be a
$P$-decomposition of an $\left[  n,k,\delta\right]  _{q}$ code $\mathcal{C}$. The
\index{$P$-decomposition!profile}\emph{profile} of
$\mathscr{C}$ is the array 
\[ \mathrm{profile}\left(  \mathscr{C}\right) :=\left[  \left(  n_{0}%
,k_{0}\right)  ,\left(  n_{1},k_{1}\right)
,\ldots,\left(  n_{r},k_{r}\right)  \right],  
\]
where
\[
n_{i}=\left\vert supp\left(  \mathcal{C}_{i}\right)
\right\vert \text{ and }k_{i}=dim\left(  \mathcal{C}_{i}\right)
\text{.}%
\]
\end{definition}



Let $\beta=\left\{  e_{1},\ldots,e_{n}\right\}  $ be the canonical basis of $\mathbb{F}_q^n$. Given $I\subset\left[
n\right]$, the $I$-\emph{coordinate subspace} $V_I$ is defined by    
\[
V_I=span \left\{e_i \ : \ i\in I\right\} =\left\{  \sum_{i\in I}x_{i}e_{i} \ : \ x_i\in \mathbb{F}_q\right\} .
\]
Given a decomposition $\mathscr{C}=(\mathcal{C};\mathcal{C}_0;\mathcal{C}_i)_{i=1}^r$ of a linear code $\mathcal{C}$, we say that 
\begin{center}
$
V_{i}:= V_{supp(\mathcal{C}_i)}=span \left\{e_i \ : \ i\in supp\left(
\mathcal{C}_{i}\right)\right\}  $
\end{center}
is the \emph{support-space of (the component) }$\mathcal{C}_{i}$. We consider
$\left[  n\right]  _{\mathcal{C}}=supp\left(  \mathcal{C}\right)  $ and $\left[
n\right]  ^{\mathcal{C}}=\left[  n\right]  \backslash\left[  n\right]  _{\mathcal{C}}$. In the case where $\left[  n\right]  ^{\mathcal{C}}\neq\emptyset$, we  write 
$V_{0}=V_{[n]^{\mathcal{C}}}$ and denote $\mathcal{C}_{0}=V_{0}$. We
say that the decomposition $(\mathcal{C};\mathcal{C}_0;\mathcal{C}_i)_{i=1}^r$ is supported by the
\emph{environment decomposition }$(V_0;V_i)_{i=1}^r$. In the case where $\left[
n\right]  ^{\mathcal{C}}=\emptyset$, we have $V_{0}=\mathcal{C}_{0}=\left\{  \mathbf{0}\right\}  $.

Given a $P$-decomposition $\mathscr{C}=(  \mathcal{C}^\prime;\mathcal{C}_{0}^{\prime};\mathcal{C}_{i}^{\prime})
_{i=1}^{r}$  of $\mathcal{C}$, the environment decomposition determine a partition of $[n]$, i.e., $\left[  n\right]  =\cup_{i=0}^{r}supp\left(  V_{i}\right)  $. Also, if $\mathcal{C}_{i}^\prime=\left\{  \mathbf{0}\right\}$, then $ i=0$. If each $\mathcal{C}^\prime_i$ is $P$-irreducible, denoting $n_{i}=dim (V_{i})=|supp(\mathcal{C}_i)|$
and $k_{i}=dim (\mathcal{C}_{i}^{\prime})$, then 
\begin{equation*}
\sum_{i=0}^{r}n_{i}   =n=dim (\mathbb{F}_q^n )\ \text{ and } \ 
\sum_{i=1}^{r}k_{i}=k=dim (\mathcal{C}).
\end{equation*}

The following theorem states that the profile of a maximal $P$-decomposition
$\mathscr{C}$ of a code $\mathcal{C}$ depends (essentially) exclusively on
$\mathcal{C}$, not on $\mathscr{C}$.

\begin{theorem}\label{teo:profile}
\label{teo1}Let $\mathcal{C}$ be an $\left[  n,k,\delta\right]  _{q}$ code and let $P$
be a poset over $\left[  n\right]  $. If $\mathscr{C}^{\prime}$ and
$\mathscr{C}^{\prime\prime}$ are two maximal $P$-decompositions of $\mathcal{C}$ with%
$$
\mathrm{profile}(  \mathscr{C}^{\prime})    =\left[  (
n_{0}^{\prime},k\,_{0}^{\prime})  ,(  n_{1}^{\prime},k_{1}^{\prime
})  ,\ldots,(  n_{r}^{\prime},k_{r}^{\prime})  \right] 
$$
and
$$
\mathrm{profile}(  \mathscr{C}^{\prime\prime})   =\left[
(  n_{0}^{\prime\prime},k_{0}^{\prime\prime})  ,(
n_{1}^{\prime\prime},k_{1}^{\prime\prime})  ,\ldots,(  n_{s}%
^{\prime\prime},k_{s}^{\prime\prime})  \right]  \text{.}%
$$
Then, $r=s$ and, up to a permutation, $\mathrm{profile}\left(  \mathscr{C}%
^{\prime}\right)  =\mathrm{profile}\left(  \mathscr{C}^{\prime\prime}\right)
$, i.e., there is $\sigma\in \mathcal{S}_{r}$ such that $(  n_{i}^{\prime}%
,k_{i}^{\prime})  =(  n_{\sigma(  i)  }^{\prime\prime
},k_{\sigma(  i)  }^{\prime\prime})  $ and $(
n_{0}^{\prime},k_{0}^{\prime})  =(  n_{0}^{\prime\prime}%
,k_{0}^{\prime\prime})  $.
\end{theorem}

\begin{IEEEproof}
	Let $\mathscr{C}^{\prime}=(  \mathcal{C}^{\prime};\mathcal{C}_{0}^{\prime
	};\mathcal{C}_{i}^{\prime})  _{i=1}^{r}$ and $\mathscr{C}^{\prime\prime}=(
	\mathcal{C}^{\prime\prime};\mathcal{C}_{0}^{\prime\prime};\mathcal{C}_{i}^{\prime\prime})  _{i=1}^{s}$
	be two maximal $P$-decompositions of $\mathcal{C}$. Suppose, without loss of generality, $r<s$. If $T\in GL_{P}(\mathbb{F}_q^n)$
	is an isometry satisfying $T\left(  \mathcal{C}^{\prime}\right)  =\mathcal{C}^{\prime\prime}$, there is a
	component $\mathcal{C}_{i}^{\prime}$ of $\mathscr{C}^{\prime}$ such that $T(  \mathcal{C}_{i}^{\prime
	})  $ is not contained in any component $\mathcal{C}_{j}^{\prime\prime}$ of
	$\mathscr{C}^{\prime\prime}$, otherwise $r\geq s$. Hence, there are components $\mathcal{C}_{i_{0}}^{\prime}$ of $\mathscr{C}^\prime$ and $\mathcal{C}_{j_{0}}%
	^{\prime\prime},\mathcal{C}_{j_{1}}^{\prime\prime},\ldots,\mathcal{C}_{j_{t}}^{\prime\prime}$ of $\mathscr{C}^{\prime\prime}$ such that 
	\[
	T(  \mathcal{C}_{i_{0}}^{\prime})  \subset \mathcal{C}_{j_{0}}^{\prime\prime}\oplus
	\mathcal{C}_{j_{1}}^{\prime\prime}\oplus\cdots\oplus \mathcal{C}_{j_{t}}^{\prime\prime}%
	\]
	and $T(  \mathcal{C}_{i_{0}}^{\prime}) \cap \mathcal{C}_{j_{l}}^{\prime\prime} \neq \emptyset$
	for any $l\in\{1,\ldots,t\}$. Therefore, 
	\[
	T(  \mathcal{C}_{i_{0}}^{\prime})  =\bigoplus_{m=0}^t T(  \mathcal{C}_{i_{0}}^{\prime
	})  \cap \mathcal{C}_{j_{m}}^{\prime\prime}
	\]
	is a non-trivial $P$-decomposition for $\mathcal{C}_{i_0}^\prime$, contradicting the fact that each component of a maximal $P$-decomposition is $P$-irreducible. It follows that $r=s$. Moreover, 
	for every $i\in\{1,\ldots,r\}$ there is $j_{i}$ such that $T(
	\mathcal{C}_{i}^{\prime})  \subseteq \mathcal{C}_{j_{i}}^{\prime\prime}$. Hence, 
	$n_{i}^{\prime}\leq$ $n_{j_{i}}^{\prime\prime}$ and $k_{i}^{\prime}\leq
	k_{j_{i}}^{\prime\prime}$. Applying the same reasoning to $T^{-1}\in
	GL_{P}(\mathbb{F}_q^n)$, we get that $n_{i}^{\prime\prime}\leq$ $n_{j_{i}%
	}^{\prime}$ and $k_{i}^{\prime\prime}\leq k_{j_{i}}^{\prime}$, hence
	$n_{i}^{\prime}=$ $n_{j_{i}}^{\prime\prime}$ and $k_{i}^{\prime}=k_{j_{i}%
	}^{\prime\prime}$, so that, up to a permutation, $\mathrm{profile}(  \mathscr{C}^{\prime
})  =\mathrm{profile}(  \mathscr{C}^{\prime\prime})  $.
\end{IEEEproof}
The next Corollary follows straight from Theorem \ref{teo1}.
\begin{corollary}\label{cor:permut}
	Let $\mathscr{C}^{\prime}=(  \mathcal{C}^{\prime};\mathcal{C}_{0}^{\prime};\mathcal{C}_{i}^{\prime
	})  _{i=1}^{r}$ and $\mathscr{C}^{\prime\prime}=(  \mathcal{C}^{\prime\prime
	};\mathcal{C}_{0}^{\prime\prime};\mathcal{C}_{i}^{\prime\prime})_{i=1}^{r}$ be two maximal
	$P$-decompositions of $\mathcal{C}$ and let $T\in GL_{P}(\mathbb{F}_q^n)$ be a linear
	isometry such that $T\left(  \mathcal{C}^{\prime}\right)  =\mathcal{C}^{\prime\prime}$. Then,
	there is a permutation $\sigma\in \mathcal{S}_{r}$ such that $T(  \mathcal{C}_i^{\prime})  =\mathcal{C}_{\sigma\left(  i\right)  }^{\prime\prime}$.
\end{corollary}

To express the number of operations (splitting and aggregations) performed in a decomposition from a trivial decomposition, we first need to show that every non-trivial $P$-decomposition is a refinement of a trivial $P$-decomposition.


\begin{lemma}\label{le11}
	If $T\in GL_P(\mathbb{F}_q^n)$ then the ideals $\langle supp(\mathcal{C})\rangle$ and $\langle supp(T(\mathcal{C}))\rangle$ are isomorphic.%, i.e.,
%\[
%\langle supp(\mathcal{C})\rangle \sim \langle supp(T(\mathcal{C}))\rangle.
%\]
\end{lemma}
\begin{IEEEproof}
	Given $T\in GL_P(\mathbb{F}_q^n)$, follows immediate from the definition of $\phi_T$ (Proposition \ref{propos1}) that 
\[
	\phi_T(\mathcal{M}(supp(\mathcal{C})))=\mathcal{M}(supp(T(\mathcal{C}))).
\]
Hence, 
\[
	\langle supp(T(\mathcal{C}))\rangle=\langle \mathcal{M}(supp(T(\mathcal{C})))\rangle=\langle \phi_T(\mathcal{M}(supp(\mathcal{C}))) \rangle.
\]
On the other hand, since $\phi_T$ is an isomorphism,
\[
	\langle supp(\mathcal{C})\rangle=\langle \mathcal{M} (supp(\mathcal{C}))\rangle \sim \phi_T (\langle \mathcal{M} (supp(\mathcal{C}))\rangle ) = \langle \phi_T (\mathcal{M}(supp(\mathcal{C})))\rangle.
\]
Therefore,
\[
 	\langle supp(\mathcal{C})\rangle \sim \langle supp(T(\mathcal{C}))\rangle.
 \] 
\end{IEEEproof}

\begin{proposition}
	If $\mathscr{C}=(\mathcal{C}^\prime;\mathcal{C}_0^\prime;\mathcal{C}_i^\prime)_{i=1}^r$ is a non-trivial $P$-decomposition of $\mathcal{C}$ with $|supp(\mathcal{C}_0^\prime)|>|supp(\mathcal{C}_0)|$, 
% with $|supp(\mathcal{C}_0^\prime)|\geq|supp(\mathcal{C}_0)|$, 
then $\mathscr{C}$ is a refinement of a trivial $P$-decomposition of $\mathcal{C}$.
\end{proposition}

\begin{IEEEproof}
	  It is straightforward that $\mathscr{C}$ is a refinement of the one-component $P$-decomposition $(\mathcal{C}^\prime;\mathcal{C}_0^\prime;\mathcal{C}^\prime)$. To conclude, we need to prove that $(\mathcal{C}^\prime;\mathcal{C}_0^\prime;\mathcal{C}^\prime)$ is obtained by aggregations from a trivial $P$-decomposition. Since $|supp(\mathcal{C}^\prime)|<|supp(\mathcal{C})|$ and $|\mathcal{M}(supp(\mathcal{C}^\prime))|=|\mathcal{M}(supp(\mathcal{C}))|$, there exist $i_0\in \langle supp(\mathcal{C}^\prime)\rangle\setminus supp(\mathcal{C}^\prime)$, otherwise $\langle supp(\mathcal{C})\rangle\not\sim \langle supp(\mathcal{C}^\prime)\rangle$ contradicting Lemma \ref{le11}. Take $j_0\in \mathcal{M}(supp(\mathcal{C}^\prime))$ such that $j_0>_P i_0$ and define $S\in GL_P(\mathbb{F}_q^n)$ by
\[
	S(e_i)=e_i \ \forall \ i\neq j_0 \ \ \ \text{ and} \ \ \ S(e_{j_0})=e_{j_0}+e_{i_0}.
\]
Therefore, $\phi_S=id$. Denoting $S(\mathcal{C}^\prime)=\mathcal{C}^{\prime\prime}$, since $supp(\mathcal{C}^\prime)=supp(\mathcal{C}^{\prime\prime})\cup \{i_0\}$ we get that $(\mathcal{C}^\prime;\mathcal{C}_0^\prime;\mathcal{C}^\prime)$ is a 1-step refinement of $(\mathcal{C}^{\prime\prime};\mathcal{C}_0^{\prime\prime};\mathcal{C}^{\prime\prime})$. Proceeding in this form (performing aggregations), at some point we get a trivial $P$-decomposition having $\mathscr{C}$ as its refinement.
\end{IEEEproof}

\begin{definition}
	Given a $P$-decomposition $\mathscr{C}=(\mathcal{C}^\prime; \mathcal{C}_0^\prime; \mathcal{C}_i^\prime)_{i=1}^r$ of $\mathcal{C}$, its \textit{degree} according to $\mathcal{C}$ is defined by 
	\[
		\mathcal{D}_P(\mathscr{C},\mathcal{C})=(r-1)+ |supp(\mathcal{C}_0^\prime)|-|supp(\mathcal{C}_0)|.
	\]	
	A $P$-decomposition with maximum degree is called \textit{primary $P$-decomposition}. 
\end{definition}

The degree of a decomposition is basically the number of $1$-step refinements necessary to obtain the given decomposition from a trivial decomposition, clearly, if $\mathscr{C}$ is a trivial decomposition, $\mathcal{D}_P(\mathscr{C},\mathcal{C})=0$ and if $\mathscr{C}^\prime$ is a $P$-refinement of $\mathscr{C}$, then $\mathcal{D}_P(\mathscr{C}^\prime,\mathcal{C})>\mathcal{D}_P(\mathscr{C},\mathcal{C})$. Furthermore, the degree of a decomposition is completely determined by its profile. Hence, by Theorem \ref{teo1}, maximal $P$-decompositions have the same degree. Thus, the maximum degree of a decomposition of a code $\mathcal{C}$ will be denoted by $\mathcal{D}_P(\mathcal{C})$ instead of $\mathcal{D}_P(\mathscr{C},\mathcal{C})$.

The following proposition follows straight from the previous comments.

% \begin{definition}
% 	Given a $P$-decomposition $\mathscr{C}=(\mathcal{C}^\prime; \mathcal{C}_0; \mathcal{C}_i)_{i=1}^r$ of $\mathcal{C}$, its \index{complexity of $P$-decomposition}\textit{complexity} is defined by 
% 	\[
% 		\mathcal{D}_P(\mathscr{C})=\frac{1}{r}+\sum_{i=1}^r n_i-k_i,
% 	\]
% 	where $n_i=dim (V_i)$ (the dimension of the support-space of $\mathcal{C}_i$) and $k_i=dim (\mathcal{C}_i)$ for every $1\leq i \leq r$. A $P$-decomposition with minimum complexity is called \index{primary $P$-decomposition}\textit{primary $P$-decomposition}. 
% \end{definition}


% Note that the complexity of a $P$-decomposition is completely determined by its profile. Each aggregation decreases the complexity since some of the parcels $n_i-k_i$ in the summation decrease. A splitting also decreases the complexity since it increases the number of components (the number $r$). By Theorem \ref{teo1}, maximal $P$-decompositions have the same complexity. Thus, the minimum complexity of a decomposition of a code $\mathcal{C}$ will be denoted by $\mathcal{D}(\mathcal{C})$ instead of $\mathcal{D}(\mathscr{C})$. It is straightforward that aggregations and splittings decrease the complexity of a $P$-decomposition; Therefore, we have the following proposition.

\begin{proposition}\label{prop:maximal_primary}
	A $P$-decomposition of a code $\mathcal{C}$ is maximal if, and only if, it is a primary $P$-decomposition.
\end{proposition}

We recall that the group of linear $P$-isometries is the semi-direct product $GL_P(\mathbb{F}_q^n)=\mathcal{G}_P\rtimes \mathcal{A}ut(P)$. It is worth remarking that the permutation part $\mathcal{A}ut(P)$ is irrelevant regarding maximality of $P$-decompositions:

%, remark that this decomposition will provide a canonical form for the generator matrix of codes. The permutation part is just relevant to obtain a standard form for the generator matrix since, in some cases, as we can see in the canonical form for hierarchical codes (Corollary \ref{col6}) and in the canonical decomposition for NRT metrics given in \cite{alves2011standard}, we can standardized them by using block matrices.

\begin{proposition}
	\label{lema1}Let $\mathscr{C}=\left(  \mathcal{C}^{\prime}%
	;\mathcal{C}_{0};\mathcal{C}_{i}\right)_{i=1}^r$ be a maximal
	$P$-decomposition of $\mathcal{C}$. Let $\phi\in Aut\left(  P\right)  $ and $T_{\phi}\in
	\mathcal{A}ut(P)$ be the isometry induced by $\phi$. Then,
	\[
	\mathscr{C}^{\prime}  =\left(  T_{\phi}\left(
	\mathcal{C}^{\prime}\right)  ;T_{\phi}\left(  \mathcal{C}_{0}\right)  ;T_{\phi}\left(  \mathcal{C}_{i}\right)  \right)_{i=1}^r
	\]
	is also a maximal $P$-decomposition of $\mathcal{C}$.
\end{proposition}

\begin{IEEEproof}
	Because $\phi$ is a permutation, for every $i\in\{0,1,\ldots,r\}$, 
	$$j\in supp(\mathcal{C}_i) \iff \phi(j) \in supp(T_\phi (\mathcal{C}_i)).$$
	Hence, $\mathscr{C}^{\prime}$ is a $P$-decomposition of $\mathcal{C}$. Since its profile coincides with the profile of $\mathscr{C}$, $\mathscr{C}^\prime$ is also a maximal $P$-decomposition of $\mathcal{C}$.
\end{IEEEproof}


%We will see that the permutation part  is irrelevant to the $P$-decomposition of a code. 


\subsection{Construction of Maximal P-Decompositions}

%Starting with an arbitrary generator matrix of a code $\mathcal{C}$, we will describe how to obtain a maximal $P$-decomposition for this code. This will be performed by operating in the generator matrix of $\mathcal{C}$, each operation being equivalent to apply a linear isometry over $\mathcal{C}$. First of all, as we shall see in the next proposition, given a linear isometry $T\in\mathbb{F}_q^n$, the maximal decomposition $$\mathscr{C}=(T(\mathcal{C});\mathcal{C}_0^\prime;\mathcal{C}_i^\prime)_{i=1}^r$$ of $T(\mathcal{C})$, which is also a (not necessarily maximal) $P$-decomposition of $\mathcal{C}$, is completely determined once $T$ is chosen.

% \begin{proposition}\label{propo001}
% 	Given a $[n,k,\delta]_q$ linear code $\mathcal{C}$, its maximal decomposition is fully determined by $\mathcal{C}$.
% \end{proposition}

% \begin{proof}
% 	The proof follows by construction. Define $J_0=\{i\in[n]  \ :  \ x_i=0 \ \forall \ x=(x_1,\ldots,x_n)\in\mathcal{C}\}$ and 
% 	\[
% 		\mathcal{C}_0=\{(x_1,\ldots,x_n)\in\mathbb{F}_q^n \ : \ x_i=0 \ \forall \ i\in [n]\setminus J_0\}.
% 	\]
% 	Remark that $J_0=[n]\setminus supp(\mathcal{C})$, hence $[n]\setminus J_0=supp(\mathcal{C})$. If $supp(\mathcal{C})=\emptyset$, there is nothing to be done because the trivial decomposition $(\mathcal{C};\mathcal{C}_0;\mathcal{C})$ is the only possible decomposition. Suppose $supp(\mathcal{C})\neq \emptyset$, choose $i_1\in [n]\setminus J_0$ and define
% 	\begin{equation}\label{eqq03}
% 			J_1 = \min \left\{J\subset [n] \ : \ i_1\in J \text{ and } \dim \pi_J(\mathcal{C})+\dim \pi_{[n]\setminus (J_0\cup J)} (\mathcal{C})= \dim \mathcal{C}\right\}.
% 	\end{equation}
% 	The minimum in \ref{eqq03} is according to the inclusion order and $\pi_{J}$ is the projection into the coordinate space $V_{\left[  n\right]
% \backslash J}:=\left\{  \sum_{_{i\in\left[  n\right]  \backslash J}}
% x_{i}e_{i} \ : \ x_{i}\in\mathbb{F}_{q}\right\}  $, that is, $\pi_{J}\left(
% x_{1},\ldots,x_{n}\right)  =\left(  y_{1},\ldots,y_{n}\right)  $ is defined by%
% \[
% y_{i}=\left\{
% \begin{array}
% [c]{c}%
% 0\text{ if }i\notin J\\
% x_{i}\text{ if }i\in J
% \end{array}
% \right.  \text{.}%
% \]
% We remark that, for any $J\subset [n]$, $\dim\pi_{J}(  \mathcal{C})  +\dim
% \pi_{\left[  n\right]  \backslash(  J_{0}\cup J)  }(
% \mathcal{C}^{\prime})  \geq\dim\left(  \mathcal{C}\right)  $ and equality holds if, and only if, $\mathcal{C}=\pi_{J}\left(  \mathcal{C}\right)  \oplus\pi_{\left[
% n\right]  \backslash\left(  J_{0}\cup J\right)  }(  \mathcal{C})  $.
% If $L_1$ and $L_2$ are subsets of $[n]$ such that $i_1\in L_1 \cap L_2$, 
% $$\dim \pi_{L_1}(\mathcal{C})+\dim \pi_{[n]\setminus (J_0\cup L_1)} (\mathcal{C})=\dim \mathcal{C}$$
% and 
% $$\dim \pi_{L_2}(\mathcal{C})+\dim \pi_{[n]\setminus (J_0\cup L_2)} (\mathcal{C})=\dim \mathcal{C},$$
% then, because  $\pi_I(\mathcal{C})\cap \pi_J(\mathcal{C})=\pi_{I\cap J}(\mathcal{C})$, their intersection $L_1\cap L_2$ satisfies
% \begin{align*}
% 	\mathcal{C}&=\left(\pi_{L_1}(\mathcal{C})\oplus\pi_{[n]\backslash(J_{0}\cup L_1)}(\mathcal{C})\right)  \cap \left(\pi_{L_2}(\mathcal{C})\oplus\pi_{[n]\backslash(J_{0}\cup L_2)}(\mathcal{C})\right)\\
% 	&= \pi_{L_1\cap L_2}(\mathcal{C})\oplus \pi_{[n]\setminus (J_0 \cup (L_1\cap L_2))}(\mathcal{C}).
% \end{align*}
% Therefore, the minimum of \ref{eqq03} is well defined.
% We define $\mathcal{C}_{1}=\pi_{J_{1}}\left(  \mathcal{C}\right)  $ and
% $\widetilde{\mathcal{C}}_{2}=\pi_{\left[  n\right]  \backslash\left(  J_{0}\cup
% J_{1}\right)  }\left(  \mathcal{C}\right)  $. If $\mathcal{C}_{1}=\mathcal{C}$, it
% means that the code $\mathcal{C}$ is irreducible, and we are done. Otherwise, $\left[  n\right]  \backslash\left(
% J_{0}\cup J_{1}\right)  \neq\emptyset$. So, we choose $i_{2}\in$ $\left[
% n\right]  \backslash\left(  J_{0}\cup J_{1}\right)$ and define 
% \[
% J_{2}=\min\left\{ J\subseteq\left[  n\right]  \backslash\left(
% J_{0}\cup J_{1}\right) \ : \ i_2\in J \ \text{ and } \dim\pi_{J}(  \widetilde{\mathcal{C}}_{2})  +\dim
% \pi_{\left[  n\right]  \backslash\left(  J_{0}\cup J_{1}\cup J\right)
% }(  \widetilde{\mathcal{C}}_{2})  =\dim(  \widetilde{\mathcal{C}}_{2})  \right\}.
% \]
% By the same argument as before, the minimum is well defined. Define $\mathcal{C}_{2}=\pi_{J_{2}}(  \widetilde{\mathcal{C}}_{2})$. If $\left[  n\right]  \backslash\left(  J_{0}\cup J_{1}\cup J_{2}\right)
% =\emptyset$ we stop the process, otherwise, we choose $i_{3}\in$ $\left[
% n\right]  \backslash\left(  J_{0}\cup J_{1}\cup J_{2}\right)  $ and continue on. Since the dimension of $\mathcal{C}$ is finite, for some $r>0$, $[n]\setminus (J_0\cup J_1 \cup \ldots \cup J_r)=\emptyset$. Therefore, we have constructed a maximal decomposition $\mathscr{C}=(\mathcal{C};\mathcal{C}_0;\mathcal{C}_i)_{i=1}^r$.
% \end{proof}


%Since the maximal decomposition of a code $\mathcal{C}$ is fully determined by $\mathcal{C}$, 
In order to find maximal $P$-decompositions of a code $\mathcal{C}$, we need to obtain the maximal decompositions of its equivalent codes. 
%find codes that are equivalent to $\mathcal{C}$ and verify if one of theirs maximal decompositions is a refinement of the given maximal decomposition of $\mathcal{C}$. 
In this section, we will describe the construction of a generator matrix which provides a code equivalent to $\mathcal{C}$ and determines a maximal $P$-decomposition of $\mathcal{C}$. 
%Since our main object will be generator matrix, we need to define what we mean by decomposition obtained by a generator matrix and translate the notation of maximal decompositions to matrices.

Let $P$ be a poset over $[n]$ and $G=(g_{ij})$ be a $k\times n$ generator matrix of an $[n,k,\delta]_{q}$ code $\mathcal{C}$. We lose no generality by assuming that $G$ is in a reduced row echelon form, obtained by elementary operations on rows.
% (these operations just perform change of basis). 
In order to obtain a maximal $P$-decomposition, we need to use a slight different definition for the classical reduced row echelon form. For each $i\in [k]$, let
$$j\left(  i\right)  :=\max\left\{  j \ : \ g_{ij}\neq0\right\} $$
be the right-most non-zero column of the $i$-th row of $G$. Performing elementary row operations on $G$, we may assume that
\begin{equation}\label{eqelemen}
j(1)>j(2)>\cdots > j(k) \ \text{ and } \ g_{ij(l)}=0 \ \text{ if } \ i\neq l.	
\end{equation}
We say that $G$ is in \textit{inverse reduced row echelon form} if the entries of $G$ satisfy Property (\ref{eqelemen}). From now on, we assumed that generator matrices have this form. In order to make more clear the difference of the proposed reduced row echelon form and the classical one, we present the next example.

%, the only difference is that our reduced row echelon form is obtained taking the columns from right to left, instead of the classical direction: left to right, that is, by permuting the rows of $G$, if $j\left(  i\right)  =\max\left\{  j \ : \ g_{ij}\neq0\right\}  $, we can assume that $j\left(  1\right)  >j\left(  2\right)  >\cdots>j\left(  k\right)  $ and
%$g_{ij(l)}=0$ if $i\neq l$. Such a matrix is obtained by elementary
%operations with rows, so that we are choosing another basis for $\mathcal{C}$, so that the $P$-distance is not yet playing any real role. 

\begin{example}\label{exxx01}
	Let 
	$$G=\left[
	\begin{array}{ccccc}
	1 & 0 & 1 & 1 & 0\\
	1 & 1 & 0 & 1 & 1\\
	0 & 1 & 0 & 1 & 1 
	\end{array}\right]
	$$
	be a generator matrix of a $[5,3]_2$ code $\mathcal{C}$ (the metric here is irrelevant). Then,
	$$G_1=\left[
	\begin{array}{ccccc}
	1 & 0 & 0 & 0 & 0\\
	0 & 1 & 0 & 1 & 1\\
	0 & 0 & 1 & 1 & 0 
	\end{array}\right] \text{ and }
	G_{2}=\left[
	\begin{array}{ccccc}
	0 & 1 & 1 & 0 & 1\\
	0 & 0 & 1 & 1 & 0\\
	1 & 0 & 0 & 0 & 0 
	\end{array}\right]
	$$
	are also generator matrices of $\mathcal{C}$. Note that $G_1$ is in the classical reduced row echelon form while $G_2$ is in the proposed one. 
	% Furthermore, if $j^\prime(i)=min\{j \ : \ g_{ij}\neq 0\}$, 
	% \begin{itemize}
	% 	\item[(a)] considering $G_1$ we get that 
	% 	$$j^\prime(1)=1\text{, } j^\prime(2)=2 \text{ and } j^\prime(3)=3\text{, hence } j^\prime(1)<j^\prime(2)<j^\prime(3);$$
	% 	\item[(b)] on the other hand, considering $G_2$, 
	% 	$$j(1)=5\text{, } j(2)=4 \text{ and } j(3)=1\text{, hence } j(1)>j(2)>j(3).$$
	% \end{itemize}
	
\end{example} 

%To find a maximal $P$-decomposition, we will use the generator matrix of a code by characterizing the ones determining maximal $P$-decompositions, to do so, we first need to characterize generator matrices determining maximal decompositions (without using isometries). 

%\begin{proposition}\label{propmat}
%Given an $[n,k,\delta]_q$ linear code $\mathcal{C}$. Each generator matrix determines a decomposition for $\mathcal{C}$.
%\end{proposition}

A generator matrix $G$ of $\mathcal{C}$ determines a unique decomposition $\mathscr{C}$ in the following sense:

\vspace{0.4cm}
\noindent\textbf{Construction of $\mathscr{C}$:}
\vspace{0.4cm}
\hrule
\vspace{0.3cm}
%\begin{proof}
Suppose $\beta_1=\{v_1,\ldots,v_k\}$ is the set of all rows of $G$ and $I\subset [n]$ is the index set of the null columns of $G$. Then, define 
\[
\mathcal{C}_0=\left\{v\in \mathbb{F}_q^n \ : \ v=\sum_{i\in I} x_i e_i\right\}.
\]
Take $w_1\in \beta_1$ and let $\gamma_1=\{v_{i_1},\ldots,v_{i_r}\}\subset \beta_1$ be the set of all rows of $G$ such that if $v\in\gamma_1$, then $supp(w_1)\cap supp(v)\neq \emptyset$. Denote 
$$\mathcal{C}_1=\left\{c\in \mathcal{C} \ : \ c=\sum_{j=1}^r x_i v_{i_j}\right\}.$$
Take $\beta_2=\beta_1\setminus \gamma_1$, if it is empty, the decomposition $(\mathcal{C};\mathcal{C}_0;\mathcal{C}_1)$ is the one determined by $G$. If $\beta_2\neq \emptyset$, take $w_2\in \beta_2$ and $\gamma_2=\{v_{i_1},\ldots,v_{i_s}\}\subset \beta_2$ where $v\in \gamma_2$ if, and only if, $supp(w_2)\cap supp(v)\neq \emptyset$. Define
\[
\mathcal{C}_2=\left\{c\in \mathcal{C} \ : \ c=\sum_{j=1}^s x_i v_{i_j}\right\}.	
\] 
Proceeding in this way, $\beta_{r+1}=\emptyset$ and $\beta_r\neq \emptyset$ for some $r$. In this case, $\mathscr{C}=(\mathcal{C};\mathcal{C}_0;\mathcal{C}_i)_{i=1}^r$ is the decomposition determined by $G$. It is clear that the choice of $w_i$ does not change the degree of the decomposition, therefore, the decomposition constructed is unique, up to a permutation of its components. As we shall see in the next proposition, this decomposition is maximal.
%\end{proof}
\vspace{0.3cm}
\hrule
\vspace{0.6cm}

\begin{example}
	Consider the generator matrices of Example \ref{exxx01}. The decomposition determined by $G$ is trivial since every two rows of $G$ have intersection in their supports. On the other hand, the decomposition obtained by the matrix $G_2$ is not trivial, indeed, the third row has disjoint support from the first and second rows. Therefore, if 
	\[
	\mathcal{C}_1^\prime=\{00000,01011,00110,01101\}, \ \ 
	\mathcal{C}_2^\prime=\{00000,10000\},
	\]
	and
	\[
	\mathcal{C}_1=\{00000,01101,00110,01011\}, \ \ 
	\mathcal{C}_2=\mathcal{C}_2^\prime,
	\]
	then $(\mathcal{C};\emptyset;\mathcal{C}_i^\prime)_{i=1}^2$ and $(\mathcal{C};\emptyset;\mathcal{C}_i)_{i=1}^2$ are the decomposition obtained from $G_1$ and $G_2$ respectively. 
\end{example}


A generator matrix $G$ is said to be in \index{generalized reduced row echelon form}\textit{generalized reduced row echelon form} if there is a permutation $\sigma \in \mathcal{S}_k$ such that
\[
j(\sigma(1))>\ldots>j(\sigma(k)) \text{ and } g_{ij(l)}=0 \text{ if } i\neq l,
\]
i.e., if a matrix in inverse reduced row echelon form may be obtained by permuting the rows of $G$.

\begin{proposition}\label{maxrow}
	Let $\mathcal{C}$ be an $[n,k,\delta]_q$ code. If $G$ is a generator matrix of $\mathcal{C}$ in a generalized reduced row echelon form, then $G$ determines a maximal decomposition for $\mathcal{C}$.
\end{proposition}

\begin{IEEEproof}
	Let $G$ be a generator matrix of $\mathcal{C}$ in a generalized reduced row echelon form. Without loss of generality, we will assume that the decomposition determined by $G$ has only one component, i.e., $\mathscr{C}=(\mathcal{C}; \mathcal{C}_0; \mathcal{C})$. By the construction of $\mathscr{C}$ it is straightforward that $\mathscr{C}$ can not be refined by aggregations. 
	% Suppose, by contradiction, there is a refinement for $\mathscr{C}$. 
	% \newline Claim 1: Aggregations are not allowed: if $i_0\in supp(\mathcal{C})$, every basis of $\mathcal{C}$ would have an element $v$ such that $i_0\in supp(v)$ but $supp(\mathcal{C}_0)$ is the set of null columns of $G$. 
	% \newline Claim 2: Splittings are not allowed: 
	%Denote by $v_1,\ldots,v_k$ the rows of $G$. 
	Suppose $\mathscr{C}^\prime=(\mathcal{C};\mathcal{C}_0;\mathcal{C}_i)_{i=1}^2$ is a splitting of $\mathscr{C}$. Thus, $\mathcal{C}=\mathcal{C}_1 \oplus \mathcal{C}_2$ and $supp(\mathcal{C}_1)\cap supp(\mathcal{C}_2)=\emptyset $. Let $\{w_1,\ldots,w_{k_1}\}$ and $\{w_{k_1+1},\ldots,w_k\}$ be a basis of $\mathcal{C}_1$ and $\mathcal{C}_2$ respectively. The $k\times n$ matrix $G_1$ having $\{w_1,\ldots,w_k\}$ as its rows is the generator matrix of $\mathcal{C}$ whose decomposition induced is $\mathscr{C}^\prime$. Then, 
	%$AG=G_1$ for some $k\times k$ matrix $A$, i.e., 
	each row of $G_1$ is a linear combination of the rows of $G$. Let $\beta_1$ be the minimum set of rows of $G$ generating $\{w_1,\ldots,w_{k_1}\}$, i.e., for every $i\in\{1,\ldots,k_1\}$,	
	\[
	w_i=\sum_{v\in\beta_1} x_v^i v
	\] 
	where $x_v^i\in\mathbb{F}_q$. Similarly, let $\beta_2$ be the minimum set of rows of $G$ generating $\{w_{k_1+1},\ldots,w_{k}\}$. %, i.e., 
	% 	\[
	% 	w_i=\sum_{v\in\beta_2} x_v^i v
	% \] 
	%for every $k_1+1\leq i\leq k$. 
	Since $G$ and $G_1$ generates the same code, $\beta_1\cap \beta_2=\emptyset$. 
	%Since $G$ is in a generalized reduced row echelon form, there is a coordinate $i_0$ of $v_0$ such that it is the only non-null entry of the $i_0$-th column of $G$. Then, there exist $1\leq j_1\leq k_1$ and $k_1+1\leq j_2\leq k$ such that the coordinate $i_0$ of both $w_{j_1}$ and $w_{j_2}$ are non-null, which is a contradiction, therefore $\beta_1\cap \beta_2=\emptyset$. 
	%Furthermore, since the rows of $G$ are linearly independent, $\beta_1 \cup \beta_2$ generates $\mathcal{C}$. 
	Since the decomposition induced by $G$ is trivial, $supp(\beta_1)\cap supp(\beta_2)\neq \emptyset$. Take $i_0\in supp(\beta_1)\cap supp(\beta_2)$, since $span\{\beta_1\}=\mathcal{C}_1$ and $span\{\beta_2\}=\mathcal{C}_2$, it follows that  $i_0\in supp(\mathcal{C}_1)\cap supp(\mathcal{C}_2)$, a contradiction.
	% because we are not using isometry and no aggregations are allowed when considering the trivial decompositions given by the codes generated by $\beta_1$ and $\beta_2$ (the decompositions obtained by the matrices in the generalized reduced row echelon form having $\beta_1$ and $\beta_2$ as its rows).
	% then $i_0\not\in supp(\mathcal{C}_0)$ and, supposing $i_0\in supp(\mathcal{C}_2)$, it follows that $i_0\not\in supp(\mathcal{C}_1)$. Since $i_0\in supp(\beta_1)$, there exists a row $w_i$ of $G_1$ such that $1\leq i \leq k_1$ and its $i_0$-th coordinate is non-null. Therefore, $i_0\in supp(\mathcal{C}_1)$, which is a contradiction. Hence, the decomposition determined by $G$ does not admits refinements, therefore, it is maximal.
\end{IEEEproof}



%Note that in order to find a 
%$P$-decomposition of an $[n,k,\delta]_q$ linear $P$-code $\mathcal{C}$ such that $\mathcal{C}\sim_P \mathcal{C}^{\prime}=\mathcal{C}_{1}^{\prime}\oplus \mathcal{C}_{2}^{\prime}$ with
%$supp \left(  \mathcal{C}_{1}^{\prime}\right)  \cap supp \left(
%\mathcal{C}_{2}^{\prime}\right)  =\emptyset$, we need to split the rows of the generator matrix $G$ of $\mathcal{C}^\prime$ generating two sub-matrices  with $k_1$ and $k_2$ rows ($k_1+k_2=k$) such that the index sets of non-null columns of each matrix are disjoint, 
The previous proposition ensures that each maximal decomposition is obtained by taking a generator matrix in a generalized reduced row echelon form. 
%Then, to find a maximal $P$-decomposition we need to use an proper isometry and take the maximal decomposition of the code obtained by this isometry. 
Till now, we have not used the group of linear isometries to construct maximal $P$-decompositions. In the following, we will consider the subgroup of isometries $\mathcal{G}_P$ (as we saw, the automorphism part is not relevant when searching for maximal $P$-decompositions since it does not change the degree of a decomposition). 
%Remark that if $A\in \mathcal{G}_P\subseteq GL_{P}(  \mathbb{F}_q^n )$ ($A$ is a linear isometry), then the matrix of $A$ according to the canonical basis is an element of $G_P$ (see \ref{eqq04}), which we will also denote by $A$. Therefore, applying the isometry $A$ to the generator matrix $G$ will provide a generator matrix $G_1$ such that 
%\[
%	AG^T=G_1^T.
%\]
%The matrix $G_1$ generates a code $P$-equivalent to the one generated by $G$. 
%Suppose $\{g_1,\ldots,g_k\}$ are the rows of the generator matrix $G$. 
By definition of $\mathcal{G}_P$, the following two operations over a generator matrix $G$ will provide matrices generating equivalent codes to the one generated by $G=(g_{ij})$:
\begin{enumerate}
	
	\item[(OP 1)] If $g_{i_0 j_0}\neq0$, $g_{ij_0}=0$ for every $i\neq i_0$ ($g_{i_0 j_0}$ is
	the only non-zero entry on the $j_0$-th column) and $r\leqslant_P j_0$ ($r\neq j_0$), we may assume $g_{i_0 r}=0$;
	
	This is equivalent to choosing the isometry $T\in \mathcal{G}_P$ such that $T(e_j)=e_j$ for every $j \neq j_0$ and 
	\[
	T(e_{j_0})=e_{j_0}-g_{i_0 r}g_{i_0 j_0}^{-1} e_r.	
	\]
	\item[(OP 2)] More generally, if there is $s\in[n]$ such that $r\leqslant_P j_i$ and $r\neq j_i$ for every $i\in\{1,\ldots,s\}$, furthermore, there are two rows of $G$, namely, $i_1,i_2\in [k]$, such that $g_{i_1r}=\sum_{l=1}^{s}x_l g_{i_1 j_l}$ and $g_{i_2r}=\sum_{l=1}^{s}x_l g_{i_2 j_l}$ for some choice of $x_1,\ldots,x_l\in\mathbb{F}_q$, and $g_{ij_l}=0$ for every $i\neq i_1,i_2$, 
	%($g_{i_1 j_k}$ and $g_{i_2 j_k}$ are the only non-zero entry on the $j_k$-th column for every $k\in\{1,\ldots,s\}$), 
	we may assume $g_{i_1r}=g_{i_2r}=0$. The procedure
	can be performed simultaneously to many lines and all those entries may be considered to be $0$. Furthermore, if the column $r$ is a linear combination of columns $j_{1},\ldots,j_{s}$, then one may exchange the column $r$ by the null column. Let $\{g_1,\ldots,g_n\}$ be the set of columns of $G$ and suppose
	\[
	g_{r}=\sum_{i=1}^s x_i g_{j_i}.
	\]
	In order to exchange the $r$-th column of $G$ by a null column we  consider the isometry $T\in\mathcal{G}_P$ defined by $T(e_i)=e_i$ for every $i\not\in\{j_1,\ldots,j_s\}$ and 
	\[
	T(e_{j_i})=e_{j_i}-x_i e_{r}
	\]
	for every $i\in\{1,\ldots,s\}$.
\end{enumerate}

\begin{definition}\label{main}
	Let $G$ be a generator matrix of an $[n,k,\delta]_q$ code $\mathcal{C}$. If $G$ is in generalized reduced row echelon form  and none non-null entry of $G$ may be exchanged by zero using Operations (OP 1) or (OP 2), we say that $G$ is in $P$-\textit{canonical form}.
\end{definition}

\begin{example}
	Let $\mathcal{C}$ be the $[6,3]_2$ code with generator matrix given by  
	$$G=\left[
	\begin{array}{cccccc}
	0 & 0 & 1 & 1 & 0 & 1\\
	1 & 0 & 1 & 1 & 1 & 0\\
	1 & 1 &0 & 0 & 0 & 0 
	\end{array}\right].
	$$
	Consider the poset $P_1$ with order relations $1\leqslant_{P_1} 2$ and $3\leqslant_{P_1} 4$. Applying operations (OP  1) and (OP  2) we get the following matrix in $P_1$-canonical form:
	$$G^\prime=\left[
	\begin{array}{cccccc}
	0 & 0 & 0 & 1 & 0 & 1\\
	1 & 0 & 0 & 1 & 1 & 0\\
	0 & 1 &0 & 0 & 0 & 0 
	\end{array}\right].
	$$
	Furthermore, if we consider $P_2$ a poset such that $P_1\subset P_2$ and $4\leqslant_{P_2} 5$, then performing operation (OP 1) we get
	$$G^{\prime\prime}=\left[
	\begin{array}{cccccc}
	0 & 0 & 0 & 1 & 0 & 1\\
	1 & 0 & 0 & 0 & 1 & 0\\
	0 & 1 &0 & 0 & 0 & 0 
	\end{array}\right].
	$$
	It is clear that $G^{\prime\prime}$ is in $P_2$-canonical form. It is also clear that it determines a maximum $P_2$-decomposition for $\mathcal{C}$.
\end{example}

%In the following, given $T\in\mathcal{G}_P$, denote by $A_T=(a_{ij})\in G_P$ its matrix according to the canonical basis. 

\begin{theorem}
	Let $G$ be a generator matrix of a code $\mathcal{C}$. If $G$ is in a $P$-canonical form then the decomposition determined by $G$ is a maximal $P$-decomposition of $\mathcal{C}$.
\end{theorem}

\begin{IEEEproof}
	Assume, without loss of generality, $\mathscr{C}=(\mathcal{C};\mathcal{C}_0; \mathcal{C})$. We will first show that $\mathscr{C}$ does not admit aggregations. Suppose there is a $P$-decomposition $\mathscr{C}^\prime=(T(\mathcal{C});\mathcal{C}_0^\prime; T(\mathcal{C}))$ where $T\in \mathcal{G}_P$ and 
	%such that this decomposition is obtained by an aggregation from $\mathscr{C}$, i.e., $\mathscr{C}^\prime=(T(\mathcal{C});\mathcal{C}_0^\prime; \mathcal{C}_i^\prime)_{i=1}^r$ and 
	$\phi_T(supp(\mathcal{C}_0))\subset supp(\mathcal{C}_0^\prime)$. Since $T\in\mathcal{G}_P$, the map $\phi_T$ coincides with the identity map, hence $supp(\mathcal{C}_0)\subset supp(\mathcal{C}_0^\prime)$. 
	%, i.e., $\mathscr{C}^\prime$ is an aggregation of $\mathscr{C}$. 
	Let $G_2=T(G)$ be the matrix whose $i$-th row is obtained by the action of $T$ in the $i$-th row of $G=(g_{ij})$. Thus, $G_2$ is a generator matrix of $T(\mathcal{C})$. 
	%Remark that if $G$ is the generator matrix of $\mathcal{C}$, then $(TG^T)^T$ is a generator matrix for $\mathcal{C}^\prime=T(\mathcal{C})$, denote $(TG^T)^T=G_1=(g_{ij}^1)$. 
	%We remark that $A_T=(a_{ij})\in G_P$ is the matrix obtained by $T$. 
	If $i_0 \in supp(\mathcal{C}_0^\prime)$, then $i_0$ is a null column of $G_2$. The characterization of $\mathcal{G}_P$ ensures that for every row $g_i=(g_{i1},\ldots,g_{in})$ of $G$, the $i_0$-th coordinate of $T(g_i)$, which is null and denoted by $T(g_i)_{i_0}$, is given by
	\begin{equation}\label{tg}
	0= T(g_i)_{i_0} = \sum_{\genfrac{}{}{0pt}{}{j}{i_0\leqslant_P j}} x_{ji_0}g_{ij} =g_{ii_0}x_{i_0i_0}+\sum_{\genfrac{}{}{0pt}{}{j}{j\neq i_0,\ i_0\leqslant_P j}} x_{ji_0}g_{ij}
	\end{equation}  
	%\[
	%		0=g_{li_0}^1=\sum_{\genfrac{}{}{0pt}{}{j}{i_0\leqslant j}} x_{i_0j}g_{lj}
	%	\]
	for every $i\in\{1,\ldots,k\}$. Since $x_{i_0i_0}\neq 0$, it follows that  
	\begin{equation}\label{eeq01}
	g_{ii_0}=\sum_{\genfrac{}{}{0pt}{}{j}{j\neq i_0,\ i_0\leqslant_P j}} \left(-\frac{x_{ji_0}}{x_{i_0i_0}}\right)g_{ij}
	\end{equation}
	for every $i\in\{1,\ldots,k\}$. Since $G$ is in $P$-canonical form, Equation \ref{eeq01} together with Operation (OP 2) ensures that the $i_0$-th column of $G$ is null, so $i_0\in supp(\mathcal{C}_0)$. Therefore, $supp(\mathcal{C}_0^\prime)= supp(\mathcal{C}_0)$.%, hence $\mathscr{C}^\prime$ is not an aggregation of $\mathscr{C}$. 
	
	The decomposition $\mathscr{C}$ also does not admit a splitting, indeed, suppose otherwise and let $\mathscr{C}^\prime= (T(\mathcal{C});\mathcal{C}_0;\mathcal{C}_i)_{i=1}^2$ be its refinement. 
	%To do so, we will assume, without loss of generality, $\mathscr{C}=(\mathcal{C};\mathcal{C}_0;\mathcal{C})$ is the decomposition determined by $G$. 
	Let $G_1$ be as in Proposition \ref{maxrow}, then $G_1$ is a generator matrix of $T(\mathcal{C})$ and, by construction, the decomposition determined by $G_1$ is $\mathscr{C}^\prime$. Let $\beta_1$ be the minimal set of rows of $G$ such that for every $i\in\{1,\ldots,k_1\}$,
	\begin{equation}\label{01eq}
	w_i=\sum_{g\in\beta_1} x_g^i T(g)
	\end{equation}
	where $x_v^i\in\mathbb{F}_q$. Let $\beta_2$ be the minimal set of rows of $G$ such that% generating $w_{k_1+1},\ldots,w_{k}$, i.e., 
	\begin{equation}\label{02eq}
	w_i=\sum_{g\in\beta_2} x_g^i T(g)
	\end{equation}
	for every $i\in \{k_1+1,\ldots,k\}$. We stress that the only difference between this equalities and the ones in Proposition \ref{maxrow} is the presence of the linear isometry $T$. As before, we also have that $\beta_1\cap \beta_2 = \emptyset$. By construction, $supp(\beta_1)\cap supp(\beta_2)\neq \emptyset$. Let $i_0$ be the rightmost column of $G$ such that $i_0\in supp(\beta_1)\cap supp(\beta_2)$, if $i_0\not\in supp(T(\beta_1))$ then for every $g_i=(g_{i1},\ldots,g_{in})\in\beta_1$ (which is also a row of $G$), the $i_0$-th coordinate of $T(g_i)$ is given by Equation \ref{tg}.
	%, then 
	%\[
	%	0=T(g_i)_{i_0}=\sum_{i_0\leqslant_P i} g_i x_{ii_0}.
	%\]
	Since $i_0$ is the rightmost column of $G$ such that $i_0\in supp(\beta_1)\cap supp(\beta_2)$. Equation \ref{eeq01} ensures that the $i_0$-th column of $G$ is null, a contradiction. 
	%Since $i_0$ is the rightmost column of $G$ such that $i_0\in supp(\beta_1)\cap supp(\beta_2)$, if $g_{ij}\neq 0$ for some $j\neq i_0$ and $g_i\in\beta_1$ then $g_{lj}=0$ for every $g_l\in\beta_2$. Thus, by (OP 2), the column $i_0$ of $G$ is null, a contradiction since $i_0\in supp(\beta_1)$. 
	The same argument shows that $i_0\in supp(T(\beta_2))$. Therefore, $i_0\in supp(T(\beta_1))\cap supp(T(\beta_2))$. By identities \ref{01eq} and \ref{02eq}, there exist $j\in \{1,\ldots,k_1\}$ and $l\in\{k_1+1,\ldots,k\}$ such that $i_0\in supp(w_j)\cap supp(w_l)$, a contradiction. 
	% Let $T\in\mathcal{G}_P$ be the isometry determining the splitting for $\mathscr{C}$ and consider $G_1$ as in the first part of the proof. Hence, the rows of $G_1$ can be split into two sets with disjoint support, i.e., there exist two disjoint sets $I_1$ and $I_2$ formed by rows of $G_1$ such that $|I_1|=k_1$, $|I_2|=k_2$ and $k_1+k_2=k$. Therefore, $I_1$ and $I_2$ generate $\mathcal{C}_1$ and $\mathcal{C}_2$ respectively, and $\mathscr{C}^\prime=(T(\mathcal{C});\mathcal{C}_0;\mathcal{C}_i)_{i=1}^2$ is the maximum decomposition determined by $G_1$. Since the rows of $G$ cannot be split in this form, let $i_0$ be the right-most column of $G$ such that $i_0$ belongs to the support of the 
	% 	first $k_1$ and also of the last $k_2$ rows of $G$. Since the support of the subspaces generated by the first $k_1$ and the last $k_2$ rows of $G_1$ respectively are disjoint and $i_0\not\in supp(\mathcal{C}_0^\prime)$ since $i_0\not\in supp(\mathcal{C}_0)$, then $i_0$ or belongs to the support of the first $k_1$ or of the last $k_2$ rows of $G_1$. Without loss of generality, suppose $i_0$ belongs to the support of the last $k_2$ rows of $G_1$. Therefore, if $l$ is an integer such that $0\leq l\leq k_1$, then 
	% 	\[
	% 		0=g_{li_0}^1=\sum_{\genfrac{}{}{0pt}{}{j}{i_0\leqslant j}} a_{i_0j}g_{lj}.
	% 	\]
	% 	Thus,
	% 	\begin{equation}\label{eeq02}
	% 		g_{li_0}=\sum_{\genfrac{}{}{0pt}{}{j}{i_0\leqslant j, i_0\neq j}} \left(-\frac{a_{i_0j}}{a_{i_0i_0}}\right)g_{lj}
	% 	\end{equation}
	% 	for every $l\in\{1,\ldots,k_1\}$. 
	% 	%Remark that $i_0$ is biggest column of $G$ belonging to the support of both first $k_1$ and last $k_2$ rows of $G$, and that we are assuming $G$ satisfying $j(1)>\ldots>j(k)$ and the columns $j(i)$ have only one non-null entry. 
	% 	Therefore, $i_0$ is not the last column of $G$ such that $g_{li_0}\neq 0$ for every $l\in\{1,\ldots,k_1\}$.
	% 	%, hence the summation \ref{eeq02} make sense. 
	% 	Each column contributing to the summation \ref{eeq02} has support either in the first $k_1$ or in the last $k_2$ rows of $G$, therefore, Operation (OP 2) ensures that every vector in the first $k_1$ rows of $G$ has zero in the coordinate $i_0$. Hence, $i_0$ is not in the support of the first $k_1$ rows of $G$. Therefore, $\mathcal{C}=\mathcal{C}_1\oplus \mathcal{C}_2$ where $\mathcal{C}_1$ and $\mathcal{C}_2$ are generated by the first $k_1$ and the last $k_2$ rows of $G$ respectively. We conclude that $\mathscr{C}$ and $\mathscr{C}^\prime$ have the same profile, since $G_1$ is also in a reduced row form and by Proposition \ref{maxrow}, $\mathscr{C}^\prime$ is a maximal decomposition of $\mathcal{C}^\prime$, therefore, $\mathscr{C}$ is a maximal $P$-decomposition.
\end{IEEEproof}


%\begin{corollary}
%	Let $\mathcal{C}$ be a linear code with generator matrix $G$. If $G^\prime$ is in a canonical form and if it was obtained by $G$ only by changing the basis of $\mathcal{C}$ and by operations as defined in $(1)$ and $(2)$, the decomposition determined by $G^\prime$ is a maximal $P$-decomposition for $\mathcal{C}$. 
%\end{corollary}

Each time we exchange a non-null column by a null column, we exchange a code $\mathcal{C}$
with $P$-decomposition $\mathscr{C}=\left(\mathcal{C};\mathcal{C}_{0};\mathcal{C}_{i}\right)_{i=1}^{r}  $ by a $P$-equivalent code with $P$-decomposition $\mathscr{C}%
^{\prime}=(  \mathcal{C}^{\prime};\mathcal{C}_{0}^{\prime};%
\mathcal{C}_{i}^{\prime})_{i=1}^{r}  $ where $dim (\mathcal{C}_{0}^{\prime})=dim (\mathcal{C}_{0})+1$. If the Operation (OP 2) is performed in a proper subset of $k$-lines of $G$, we do not increase
$dim (\mathcal{C}_{0})$ but, we may split some of the $\mathcal{C}_{i}$ into $\mathcal{C}_{i}=\mathcal{C}_{i_{1}%
}^{\prime}\oplus \mathcal{C}_{i_{2}}^{\prime}$ with $supp(\mathcal{C}_{i_{1}%
}^{\prime})  \cap supp(  \mathcal{C}_{i_{2}}^{\prime})
=\emptyset$.

Note that the role of $P$ in such operations rests solely on the
condition  $j\leqslant_P j_{1},j_{2},\ldots,j_s$. For the two extremal posets,
namely, the anti-chain and the chain poset, the picture is absolutely clear: If
$P$ is an anti-chain (hence we are considering the Hamming metric), no such
operation may be performed (since $i\leqslant_P j\iff i=j$). Hence, maximal $P$-decompositions coincide with maximal decompositions (see the paragraph after Definition \ref{com}) and the $P$-canonical form is a permutation of the classical systematic form; if $P$ is a chain
with $1\leqslant_P 2\leqslant_P \cdots\leqslant_P n$, then (OP 1) may be
performed to every $j\left(  i\right)  $ in the reduced row echelon matrix
$G$, hence, $\mathcal{C}$ is equivalent to a code that has a generator
matrix $G=(  g_{ij})  $ where $g_{ij (  i )  }=1$ and
$g_{ij}=0$ if $j\neq j (  i)  $ (see 
\cite{panek2010classification}). More general, for $NRT$ metrics, the $P$-canonical form is also a permutation of the $NRT$-triangular form presented in \cite{alves2011standard}. We stress that, fixing the natural labeling in the posets, the permutations necessary to obtain one form from other are the ones induced by $\mathcal{A}ut(P)$. 

The other case that can be easily described is the case of hierarchical posets. The algorithm to find $P$-decompositions according to the levels of the poset was first proposed in \cite{felix2012canonical}. 
%In that work, the basis of the code providing such decomposition was also constructed. We explicit the matrix of this basis in Corollary \ref{col6}. 
The matrix obtained by this form is called canonical-systematic and it is also a permutation of the $P$-canonical form. Furthermore, in this case, the canonical-systematic form is a standard representation in the sense that every code has such decomposition. In \cite{MachadoPinheiroFirer}, it was proved that for every non-hierarchical poset, it is not possible to give a standard representation like this one (whose support of each component is entirely contained in a specific level of the poset). %Actually, this was the main motivation to define a canonical form as we did in Definition \ref{main}.








% The second algorithm shows that hierarchical relations allow a quasi-independent syndrome decoding which is better than the independent, it is easy to see that this step-decoding process is better than search in a table with $q^{n_{i_0-k_0}}+\prod_{i\neq i_0, i=1}^r q^{n_i-k_i}$ elements, which would be the size of the look-up table if the decoding could be performed independently. Since we are concerned in quantify the complexity of syndrome decoding, we will assume the worst case scenario (which is tractable), i.e., the quasi-independent case will be considered as independent (we are actually constructing an upper bound for the quasi-independent case).


% If $\mathcal{C}^\prime=(C^\prime,C_0^\prime,C_i^\prime)_{i=1}^r$ is a maximal $P$-decomposition, the components $C_i$ can be grouped into codes $D_i$ $(D_i=\oplus_j C_{i_j})$ such that syndrome decoding can be performed independently (or quasi-independently) in each $D_i$. By construction $\mathcal{C}^{\prime\prime}=(C^\prime,C_0^\prime,D_i^\prime)_{i=1}^s$ is also a $P$-decomposition of $C$ (actually, $\mathcal{C}^\prime$ is a refinement of $\mathcal{C}^{\prime\prime}$ obtained by split operations), we will call this decomposition \textit{independent}.

% \begin{definition}
% 	We call
% 	$$\mathcal{D}(\mathcal{C}^{\prime\prime})=\sum_{j=1}^s q^{n_i-k_i}$$
% 	the complexity of the decomposition, where $[(n_0,k_0),\ldots,(n_s,k_s)]$ is the profile of the independent $P$-decomposition $\mathcal{C}^{\prime\prime}=(C^\prime,C_0^\prime,D_i^\prime)_{i=1}^s$.
% \end{definition}

%  If for all $i$, $D_i$ can not be decomposed into components where decoding can be done independently, we will call such decomposition \textit{optimal}. Since optimal decompositions for the same code has the same profile (up to a permutation), we have the following theorem.  

%  \begin{theorem}
%  	Optimal decompositions minimize the search space for syndrome decoding algorithm.
%  \end{theorem}





%Let us consider the posets $P,Q\in\mathcal{P}_{4}$ defined by $1\preceq
%_{P}2\preceq_{P}3\preceq_{P}4$ and $1\preceq_{Q}3,2\preceq_{Q}3,2\preceq_{Q}%
%4$. First of all we note that $Q<P$. If we consider the code $C$ generated by
%$\left\{  1110,0101\right\}  $, then, by matrix
%\[
%A=\left(
%\begin{array}
%[c]{cccc}%
%1 & 0 & 0 & 0\\
%0 & 1 & 0 & 0\\
%0 & 1 & 1 & 0\\
%0 & 1 & 0 & 1
%\end{array}
%\right)
%\]
%we get a code $C^{\prime}$ generated by%
%\[
%0010=\left(  1,1,1,0\right)  A\text{ and }0001=\left(  0,1,0,1\right)
%A\text{.}%
%\]
%Since the linear map $T_{A}\in GL_{P}\left(  4\right)  \cap GL_{Q}\left(
%4\right)  $ we have that
%\[
%\mathcal{C}^{\prime}=\left(  C^{\prime};C_{0}^{\prime}=\mathrm{span}\left\{
%e_{1},e_{2}\right\}  ;\mathrm{span}\left\{  e_{3}\right\}  \oplus
%\mathrm{span}\left\{  e_{3}\right\}  \right)
%\]
%is both the $P$-primary and the $Q$-primary decompositions of $C$.
%
%If we consider now the code $D=\mathrm{span}\left\{  1110,1001\right\}  $, we
%have that
%\[
%\mathcal{D}^{\prime}=\left(  D^{\prime};D_{0}^{\prime}=\mathrm{span}\left\{
%e_{1},e_{2}\right\}  ;\mathrm{span}\left\{  e_{3}\right\}  \oplus
%\mathrm{span}\left\{  e_{4}\right\}  \right)
%\]
%is the $P$-primary decomposition of $D$ and%
%\[
%\mathcal{D}^{\prime\prime}=\left(  D^{\prime\prime};D_{0}^{\prime\prime
%}=\mathrm{span}\left\{  e_{2}\right\}  ;\mathrm{span}\left\{  e_{3}\right\}
%\oplus\mathrm{span}\left\{  e_{1},e_{4}\right\}  \right)
%\]
%is the $Q$-primary decomposition of $D$, where $D^{\prime}$ and $D^{\prime
%\prime}$ are obtained from $D$ through the matrices%
%\[
%A^{\prime}=\left(
%\begin{array}
%[c]{cccc}%
%1 & 0 & 0 & 0\\
%0 & 1 & 0 & 0\\
%1 & 1 & 1 & 0\\
%\mathbf{1} & 0 & 0 & 1
%\end{array}
%\right)  \text{ and }A^{\prime\prime}=\left(
%\begin{array}
%[c]{cccc}%
%1 & 0 & 0 & 0\\
%0 & 1 & 0 & 0\\
%1 & 1 & 1 & 0\\
%\mathbf{0} & 0 & 0 & 1
%\end{array}
%\right)
%\]
%respectively. We note that $T_{A^{\prime}}\notin\Delta_{Q}$ since
%$a_{4,1}^{\prime}=1$ but $1\npreceq_{Q}4$. 
%
% The situation above is quite general: in what concern maximal decompositions,
% there are no futile posets, in the sense there is always a code that can be refined when passing from $P$ to $Q$.  This is what is stated in the next proposition, its proof is omitted since it is a long and technical construction, considering many different situations.

% \begin{proposition}
% \label{conj3}Let $P,Q\in\mathcal{P}_n  $
% with $P<Q$. Then there is a code $C$ such that the maximal $Q$-decomposition
% of $C$ is strictly finer than the maximal $P$-decomposition.
% \end{proposition}

%\begin{proof}
%Let us suppose $P=P_{0}<P_{1}<\cdots<P_{t}=Q$ where each $P_{i+1}$covers
%$P_{i}$. By Proposition \ref{conj2}, it is enough to consider the case where
%$Q$ covers $P$ and hence we assume it. \ It follows there is $i\in\left[
%r-1\right]  $ such that there are $a,b\in H_{i},c\in H_{i+1}$ such that
%\begin{align*}
%a &  \preceq_{P}c,a\preceq_{Q}c\\
%b &  \npreceq_{P}c,b\preceq_{Q}c
%\end{align*}
%Let $C$ be the one dimensional code generated by $e_{c}+e_{b}$ and let
%$C^{\prime}$ be the code generated by $e_{c}$. We have that $\left[  n\right]
%^{C}=\left[  n\right]  \backslash\left\{  b,c\right\}  $ and $\left[
%n\right]  ^{C^{\prime}}=\left[  n\right]  \backslash\left[  c\right]  $ and
%define
%\begin{align*}
%C_{0} &  =C_{0}^{^{\prime}}=\left\{  0\right\}  \\
%V_{0} &  =\left\{  \sum_{j\in\left[  n\right]  \backslash\left\{  b,c\right\}
%}\lambda_{j}e_{j}|\lambda_{j}\in\mathbb{F}_{q}\right\}  ,V_{1}=\left\{
%\lambda_{b}e_{b}+\lambda_{c}e_{c}|\lambda_{b},\lambda_{c}\in\mathbb{F}%
%_{q}\right\}  \\
%V_{0}^{^{\prime}} &  =\left\{  \sum_{j\in\left[  n\right]  \backslash\left\{
%c\right\}  }\lambda_{j}e_{j}|\lambda_{j}\in\mathbb{F}_{q}\right\}
%,V_{1}^{^{\prime}}=\left\{  \lambda_{c}e_{c}|\lambda_{c}\in\mathbb{F}%
%_{q}\right\}  \text{.}%
%\end{align*}
%The linear $\phi:\left\{  e_{1},\ldots,e_{n}\right\}  \rightarrow\left\{
%e_{1},\ldots,e_{n}\right\}  $ defined by
%\begin{align*}
%\phi\left(  e_{j}\right)   &  =e_{j}\text{ if }j\in\left[  n\right]
%\backslash\left\{  b,c\right\}  \\
%\phi\left(  e_{c}\right)   &  =e_{c}-e_{b}\\
%\phi\left(  e_{b}\right)   &  =e_{b}%
%\end{align*}
%extends to a linear $Q$-isometry $T_{\phi}:\mathbb{F}_{q}^{n}\rightarrow
%\mathbb{F}_{q}^{n}$ and it follows that $\mathcal{C}^{\prime}=\left(
%C;C_{0}^{^{\prime}},C^{\prime}\right)  $ is a $Q$-primary decomposition of $C$.
%
%On the other hand, we claim that $\mathcal{C=}\left(  C;C_{0},C\right)  $ is a
%$P$-primary decomposition of $C$. Indeed, if $\mathcal{C=}\left(
%C;C_{0},C\right)  $ was not a $P$-primary decomposition, the only way to
%refine it would be  to have a code $D\subset\mathbb{F}_{q}^{n}$ such that $D$
%is $1$-dimensional with $\left\vert supp\left(  D\right)  \right\vert
%=1$ and to have an isometry $T\in\Delta_{P}\left(  n\right)  $ such that
%$T\left(  C\right)  =D$. Assuming $dim\left(  D\right)  =1$ we have that $D$
%is generated by a single vector $v$ and assuming $\left\vert supp%
%\left(  D\right)  \right\vert =1$ this implies that we may assume $v=e_{d}$
%for some $d\in\left[  n\right]  $. However, an element $T\in GL_{P}\left(
%n\right)  $ determines an order automorphism $\sigma_{T}\in Aut\left(
%P\right)  $ that is defined by looking at ideals generated by single elements,
%that is: given $S\in GL_{P}\left(  n\right)  $ and $i\in\left[  n\right]  $,
%$\left\langle supp\left(  S\left(  e_{i}\right)  \right)
%\right\rangle =\left\langle j_{i}\right\rangle $ and the map $\sigma\left(
%i\right)  =j_{i}$ is an order automorphism. In particular, $\left\langle
%supp\left(  S\left(  e_{i}\right)  \right)  \right\rangle $ has a
%unique maximal element. In our case, putting $S=T^{-1}$, we get a
%contradiction, since $\left\langle supp\left(  S\left(  e_{c}\right)
%\right)  \right\rangle =\left\langle supp\left(  T^{-1}\left(
%e_{c}\right)  \right)  \right\rangle =\left\langle \left\{  b,c\right\}
%\right\rangle $. It follows that $\mathcal{C=}\left(  C;C_{0},C\right)  $ is a
%$P$-primary decomposition of $C$ and since $dim\left(  C_{0}\right)
%<dim\left(  C_{0}^{\prime}\right)  $ we have $\mathcal{C}^{\prime}$ is
%strictly finer then $\mathcal{C}$.
%\end{proof}

% \subsection{Hierarchical Bounds for Complexity of Syndrome Decoding}

% Hierarchical poset metrics are well understood. In particular, if $P$ is a hierarchical poset, the profile of a primary $P$-decomposition of a code $C$ is uniquely (and easily) determined by the weight hierarchy of the code (see \cite{felix} for details). Moreover, it is possible to prove that this property is exclusive of hierarchical posets. For this reason, when considering a general poset $P$, we aim to establish bounds for $\mathcal{D}_P(C)$ considering the easy-to-compute minimal complexity of $C$ relatively to hierarchical posets.



% Let $P=\left(  \left[  n\right]  ,\preceq\right)$ be a poset with level
% hierarchy $\left[  n\right]  =H_{1}\cup H_{2}\cup\ldots\cup H_{r}$ with
% $n_{i}=\left\vert H_{i}\right\vert $ and $n=\sum_{i=1}^r n_{i}$. We say that $P$ is
% \emph{hierarchical at level }$i$ if levels $H_{i}$ and $H_{i-1}$ relate
% hierarchically, that is, if $a\in H_{i}$ and $b\in H_{i-1}$ then $b\preceq a$. Since $H_0$ is empty, by vacuity every poset is hierarchical at level $1$.
% Let $\mathcal{H}\left(  P\right)  =\left\{  i\in\left[  r\right]  |P\text{ is
% hierarchical at }i\right\}  $. Of course, $P$ is hierarchical \emph{iff}
% $\mathcal{H}\left(  P\right)  =\left[  r\right]  $. We can label the elements
% of $\mathcal{H}\left(  P\right)  $ as $1=j_{1}<j_{2}<\cdots<j_{h}$ where
% $h=\left\vert \mathcal{H}\left(  P\right)  \right\vert $. 
% %We denote
% %$N_{i}=n_{1}+n_{2}+\cdots+n_{j_{i}}$, for $j_{i}\in\mathcal{H}\left(
% %P\right)$.

% Out of $P$ we define two hierarchical posets:

% \textbf{Upper neighbour:} Let $P^{+}$ be the poset on $\left[n\right]  $
% with the same level decomposition of $P$ and for every $a\in H_{i},b\in H_{j}$ with $a\neq b$ define $a\preceq_{P^+}b$ if, and only if, $i<j$.

% \textbf{Lower neighbour: }Let $P^{-}$ be the poset on $\left[  n\right]  $ with level  hierarchy $\left[  n\right]  =J_{1}\cup
% J_{2}\cup\cdots\cup J_{h}$ where
% %J_{1}  =\left[  N_{2}\right]  =\left[  N_{1}\right]  \text{ and }
% %\left[  N_{i-1}+1,N_{i}\right]:=[N_i]\setminus [N_{i-1}]
% \begin{equation*}
% J_{i}   = \bigcup_{s=j_i}^{j_{i+1}-1} H_s  \ \text{ and } \ j_{h+1}=r+1
% \end{equation*}
% and for $a\in H_{i},b\in H_{j}$ with $a\neq b$ we have $a\preceq_{P^-}b$ if, and only if, $ i<j$.
% It is easy to see that:

% \begin{itemize}
% \item $P^{+}$ and $P^{-}$ are hierarchical posets and $P$ is hierarchical if, and only if,  $P=P^{+}=P^{-}$;

% \item Considering the natural order $\leq$ on $\mathcal{P}_{n}$ we have that
% $P^{-}\leq P\leq P^{+}$, moreover 
% \begin{align*}
% P^{-}  &  =\max\left\{  Q\in\mathcal{P}_{n}|Q\leq P,Q\text{ hierarchical}%
% \right\}  ,\\
% P^{+}  &  =\min\left\{  Q\in\mathcal{P}_{n}|P\leq Q,Q\text{ hierarchical}%
% \right\}.
% \end{align*}
% \end{itemize}
% The proposition below follows directly from the definitions.

% \begin{proposition}\label{bound} For any linear code $C$ we have%
% \[
%  \mathcal{D}_{P^+}\left(  C\right)  \leq \mathcal{D}_{P}\left(  C\right) \leq  \mathcal{D}_{P^-}\left(  C\right).
% \]
% \end{proposition}

% We remark that due to the Canonical-systematic form, introduced in \cite{felix}, the minimal complexity of syndrome decoding is easy to compute for hierarchical metrics.

%  If $P$ is not hierarchical, both inequalities are strict, for some code
% $C$. Moreover, the bounds are tight, in the sense that, given $P$, there are codes $C^{+}$ and $C^{-}$ such that $\mathcal{D}_{P^{+}}\left(
% C^{+}\right)  =\mathcal{D}_{P}\left(  C^{+}\right)  $ and  $\mathcal{D}_{P^{-}%
% }\left(  C^{-}\right)  =\mathcal{D}_{P}\left(  C^{-}\right)  $.



\section{Comparison of Posets and Decompositions}\label{sec:refinement}



%A maximal $P$-decomposition, as determined in Section  \ref{sub:parti}, is essentially unique when $P$ is a hierarchical poset, the permutation $\sigma\in \mathcal{S}_{r}$ defined in Corollary \ref{cor:permut} is the identity.
%To be more clear, } 

As proved in \cite[Corollary 1]{felix2012canonical}, if $P$ is a hierarchical poset, a linear code may be canonically decomposed as $T(\mathcal{C})=\mathcal{C}_1\oplus \cdots\oplus \mathcal{C}_r$ where $supp\left(\mathcal{C}_{i}\right)\subset \Gamma_P^i$. As we shall explain in Section \ref{sec:applications}, this canonical decomposition permits to give explicit formulae and constructions for metric invariants. Since this decomposition (according to the levels of the poset) is a characteristic of hierarchical posets, see \cite[Theorem 3]{MachadoPinheiroFirer}, we aim to use the knowledge about hierarchical poset metrics to establish bounds in the general case. To do that, we need to show that the  $P$-primary decomposition is \textquotedblleft  well behaved\textquotedblright, in the sense that the decomposition are comparable when the posets are comparable. The meaning of the expression ``well behaved'' will be explained in Theorem \ref{well}. 


\subsection{Decompositions and refinements}\label{sub:decomp_refine}


The set of all posets over $[n]$ is denoted by $\mathcal{P}_n$. It is, on itself, a partially ordered set with the order relation given by $P\leq Q$ if for every $a,b\in[n]$ with $a\leqslant_P b$ implies $a\leqslant_Q b$.

The set $\mathcal{P}_n$ has $n!$ (isomorphic) \emph{chain} posets and one \emph{anti-chain} poset, these $n!+1$ elements may be considered as extremal posets, indeed, it is easy to verify that adding a relation to a chain will give rise to a cycle $a\leqslant b\leqslant a$ since a total order on $[n] $ is defined once we state that $\sigma (1)\leq \sigma (2)\leq\ldots\leq\sigma (n)$ for some permutation $\sigma\in \mathcal{S}_n$, contradicting the anti-symmetry property of a partial order. On the other hand, it is also immediate to realize that no relation can be removed from an anti-chain since $a\leqslant a$ for all $a\in [n]$ are the unique relations on an anti-chain. 




%We recall that the set $\mathcal{P}_{n}$ of all posets over $\left[  n\right]  $ isitself a partially ordered set. Maximal $P$-decompositions ``behaves well'' according to this order in the following way: 

\begin{theorem}\label{well}
	\label{conj2}Let $P,Q\in\mathcal{P}_n$ with
	$P\leq Q$. Given a code $\mathcal{C}$, there is a maximal $P$-decomposition of $\mathcal{C}$ which is a $Q$-decomposition of $\mathcal{C}$.
\end{theorem}

\begin{IEEEproof}
	Assume $P,Q\in\mathcal{P}_n  $ and $P<Q$. Let
	$\mathscr{C}^{\prime}=\left(  \mathcal{C}^{\prime};\mathcal{C}_{0};\mathcal{C}_{i}\right)_{i=1}^r  $ be a maximal $P$-decomposition
	of $\mathcal{C}$ and $T\in GL_{P}(\mathbb{F}_q^n)$ such that $T\left(
	\mathcal{C}\right)  =\mathcal{C}^{\prime}$. By the characterization of $GL_P(\mathbb{F}_q^n)$, $T=A\circ T_\phi$ where $A\in\mathcal{G}_P$ and $T_\phi\in\mathcal{A}ut(P)$. From Proposition \ref{lema1}, we have that
	$$
	\mathscr{C}^{\prime\prime} = \left(  T_{\phi^{-1}}\left(  \mathcal{C}^{\prime}\right)  ;T_{\phi^{-1}}\left(
	\mathcal{C}_{0}\right)  ;T_{\phi^{-1}}\left(  \mathcal{C}_{i}\right)  \right)_{i=1}^r  
	$$
	is also a maximal $P$-decomposition of $\mathcal{C}$. However $T_{\phi^{-1}}\left(  \mathcal{C}^{\prime}\right)=T_{\phi^{-1}}\circ T (\mathcal{C})$, hence 
	$$
	T_{\phi^{-1}}\left(  \mathcal{C}^{\prime}\right)   =T_{\phi^{-1}}\circ A \circ T_\phi ( \mathcal{C}).
	$$
	We stress that $\mathcal{G}_P\subset \mathcal{G}_Q$ always that $P\leq Q$. Because $\mathcal{G}_P$ is a normal subgroup of $GL_P(\mathbb{F}_q^n)$, it follows that $T_{\phi^{-1}}\circ A \circ T_\phi \in \mathcal{G}_P$, hence $T_{\phi^{-1}}\circ A \circ T_\phi \in \mathcal{G}_Q$. Therefore, $\mathscr{C}^{\prime\prime}$ is a $Q$-decomposition of $\mathcal{C}$.
\end{IEEEproof}
 As a direct consequence of the previous theorem, we obtain a relation among primary decompositions of posets and the natural order over $\mathcal{P}_n$. 
 \begin{corollary}\label{col10}
	 If $P,Q\in\mathcal{P}_n  $ with
	 $P\leq Q$. Then, 
	 $\mathcal{D}_P(\mathcal{C})\leq \mathcal{D}_Q(\mathcal{C})$
	 for every linear code $\mathcal{C}$.
 \end{corollary}

Concerning primary $P$-decompositions, there is always a code that it is differently decomposed depending on the poset, that is, the preceding inequality is strict:

\begin{proposition}
	\label{conj3}If $P,Q\in\mathcal{P}_n$
	with $P<Q$. Then, there is a code $\mathcal{C}$ such that 
	$$\mathcal{D}_P(\mathcal{C})<\mathcal{D}_Q(\mathcal{C}).$$	
\end{proposition}

\begin{IEEEproof}
Suppose $P< Q$. Hence, there are $i_0,j_0 \in [n]$ such that 
	$$
	i_0   \nleqslant_{P} j_0 \text{ and }\ i_0 \leqslant_{Q} j_0.
	$$
	Let $\mathcal{C}=span\{e_{i_0}+e_{j_0}\}$ and $\mathcal{C}^{\prime}=span\{e_{j_0}\}$ be two codes over $\mathbb{F}_q^n$. 
	The linear map $T$ defined by $T(e_j)=e_j$ for every $j \in [n]\setminus \{i_0,j_0\}$, $T(e_{i_0})=e_{i_0}$ and $T(e_{j_0})=e_{j_0}-e_{i_0}$, is a $Q$-linear isometry, by the characterization of $GL_Q(\mathbb{F}_q^n)$ given in Proposition \ref{propos1}. Therefore, the $Q$-decomposition 
$		\mathscr{C}^\prime=(\mathcal{C}^\prime; \mathcal{C}_0^\prime; \mathcal{C}^\prime)$
	of $\mathcal{C}$, where $\mathcal{C}_0^\prime=\{v\in\mathbb{F}_q^n \ : \ v_{j_0}=0\}$, is a primary $Q$-decomposition and it follows that $\mathcal{D}_{Q}(\mathcal{C})=1$.

	On the other hand, when considering the $P$-metric, the decomposition $\mathscr{C}=\left(  \mathcal{C};\mathcal{C}_{0};\mathcal{C} \right)$, where $\mathcal{C}_0=\{v\in\mathbb{F}_q^n \ : \ v_{i_0}\neq 0 \text{ and } v_{j_0}\neq 0\}$, can not be refined since $\mathcal{C}$ is a one-dimensional code (hence, splittings are not allowed) whose support is composed by two maximal elements of $P$ (hence, aggregations are not allowed). Therefore, $\mathscr{C}^\prime$ is a primary $P$-decomposition for $\mathcal{C}$ and $\mathcal{D}_P(\mathcal{C})=0$. 



% 	{\color{red}Let us suppose $P<P_{1}\leq Q$ and that $P_1$ covers $P$. Then, there are $i_0,j_0 \in [n]$ such that 
% 	$$
% 	i_0   \nleqslant_{P} j_0 \text{ and }\ i_0 \leqslant_{P_1} j_0.
% 	$$
% 	Let $\mathcal{C}$ be the one-dimensional code generated by $e_{i_0}+e_{j_0}$ and let
% 	$\mathcal{C}^{\prime}$ be the one-dimensional code generated by $e_{j_0}$. 
% 	The linear map $T$ defined by $T(e_j)=e_j$ for every $j \in [n]\setminus \{i_0,j_0\}$, $T(e_{i_0})=e_{i_0}$ and $T(e_{j_0})=e_{j_0}-e_{i_0}$, is a $P_1$-linear isometry by the characterization of $GL_P(\mathbb{F}_q^n)$ given in Proposition \ref{propos1}. Therefore, the $P_1$-decomposition 
% $		\mathscr{C}=(\mathcal{C}^\prime; \mathcal{C}_0^\prime; span \{e_{j_0}\})$
% 	of $\mathcal{C}$ is a primary $P_1$-decomposition. We note that $\mathcal{C}_0^\prime=\mathbb{F}_q^n \setminus span \{e_{j_0}\}$ and therefore, $\mathcal{D}_{P_1}(\mathcal{C})=1$.

% 	On the other hand, we claim that $\mathscr{C}^\prime=\left(  \mathcal{C};\mathcal{C}_{0};\mathcal{C} \right)$, where $\mathcal{C}_0=\oplus_{i\neq i_0,j_0} V_i$, is a $P$-primary decomposition of $\mathcal{C}$. Indeed, suppose, for a contradiction that $\mathscr{C}^\prime$ is not a $P$-primary decomposition, the only way to refine it would be by constructing a $1$-dimensional code $\mathcal{C}^{\prime\prime}$ with $\left\vert supp \left(  \mathcal{C}^{\prime\prime}\right)  \right\vert
% 	=1$ and $\mathcal{C}^{\prime\prime}\sim_P \mathcal{C}$. Hence, $\mathcal{C}^{\prime\prime}$ would be generated by a canonical vector $e_{d}$
% 	for some $d\in\left[  n\right]$. Suppose $T\in GL_P(\mathbb{F}_q^n)$ and $T(\mathcal{C})=\mathcal{C}^{\prime\prime}$, therefore $T(e_{i_0}+e_{j_0})=e_d$ for some $d\in[n]$. Considering $S=T^{-1}$, it follows that $\mathcal{M}(supp (S(e_d)))=\{i_0,j_0\}$. But $S$ can not be an isometry since $\phi_S$ is not well defined. Therefore, $\mathscr{C}^\prime$ is a primary $P$-decomposition for $\mathcal{C}$ and 
% 	\begin{equation}
% 		0= \mathcal{D}_P(\mathcal{C})<\mathcal{D}_{P_1}(\mathcal{C}) =1.\label{eqq01}
% 	\end{equation}
% 	Since $P_1\leq Q$, Corollary \ref{col10} ensures that 
% 	\begin{equation}
% 		\mathcal{D}_{P_1}(\mathcal{C}) \leq \mathcal{D}_{Q}(\mathcal{C}) .\label{eqq02}
% 	\end{equation}
% 	From inequalities \ref{eqq01} and \ref{eqq02} we get that $\mathcal{D}_{P}(\mathcal{C}) <\mathcal{D}_{Q}(\mathcal{C}) $.}
\end{IEEEproof}


We remark that Corollary \ref{col10} together with Proposition \ref{conj3} implies that primary decomposition is a characterization of posets, in the sense that a given poset $P$ may be reconstructed from the profile of codes according to $P$. Moreover, looking at the proof of Proposition \ref{conj3}, one may notice that the reconstruction can be done by considering only the $n(n-1)/2$ pairs of vectors $(e_i,e_j)$.   


%{\textcolor{red}{Arrumar a partir daqui}}
\subsection{Hierarchical Bounds}\label{sub:hierar_bouds}

As we have mentioned, metrics induced by hierarchical posets are well understood. This knowledge was mainly obtained from the existence of the decomposition derived from the canonical-systematic form. Since the degree of a decomposition express the amount of $1$-step refinements performed from the trivial decomposition, we aim to use the knowledge of hierarchical posets and establish bounds for the degree considering the easy-to-compute degree of primary $P$-decompositions relatively to hierarchical posets. 


As we have mentioned, hierarchical poset metrics are well understood and, in particular, if $P$ is a hierarchical poset, the profile (and consequently the degree) of a primary $P$-decomposition of a code $\mathcal{C}$ 
%is unique and, as we can see in \cite{machado2015characterization}, this property is exclusive of hierarchical posets.} Moreover, in this case, the maximal degree $\mathcal{D}_P(\mathcal{C})$ 
can be easily computed once we know the canonical-systematic form. %if we know the cardinality of each $\Lambda_i(\mathcal{C}):= \{ c\in\mathcal{C}: w_P(c)=i  \} $. 
For this reason, when considering a general poset $P$, we aim to establish bounds for $\mathcal{D}_P(\mathcal{C})$ considering the easy-to-compute primary $P$-decompositions relatively to hierarchical posets.

%In the next section, we will characterize the generator matrices that determine maximal $P$-decompositions providing an algorithm to obtain these matrices. But the complexity to determine these matrices will not be discussed.

% We say that a poset $P$ is
% \emph{hierarchical at level }$i$ if levels $\Gamma_P^i$ and $\Gamma_P^{j}$ relate
% hierarchically for every $j\in \{1,\ldots,i-1\}$, i.e., if $a\in \Gamma_P^{j}$ for some $j\in\{1,\ldots,i-1\}$ and $b\in \Gamma_P^{i}$ then $a\leqslant b$.
% Let 
% $$\mathcal{H}\left(  P\right)  =\left\{  i\in\left[  r\right]  \ : \ P\text{ is
% hierarchical at }i\right\}  .$$
% It is clear that $P$ is hierarchical if, and only if, 
% $\mathcal{H}\left(  P\right)  =\left[  r\right]  $. 


% We stress that for every integers $a$ and $b$ with $a<b$, the notation $[a,b]$ denotes the set $\{a,a+1,\ldots,b\}$. Given a poset $P$ with height $r$, then:

% \noindent\textbf{(1)} Consider 
% $$s_1=\min\{i\in[r] \ : \ P \text{ is not hierarchical at level } i+1 \}$$
% and
% \[
% 	s_2=\min\{i\in[r] \ : \ i>s_1 \text{ and } P \text{ is hierarchical at level } i+1\}. 
% \]
% Denote 
% $$J_i=[n_1+\cdots+n_{i-1}+1,n_1+\cdots+n_i]$$
% for every $1 \leq i < s_1$ and
% \[
% 	J_{s_1}=[n_1+\cdots+n_{s_1-1}+1,n_1+\cdots+n_{s_2}].
% \]

% \noindent\textbf{(2)} Consider
% \[
% 	s_3=\min\{i\in[r] \ : \ i>s_2 \text{ and } P \text{ is not hierarchical at level } i+1\} 
% \]
% and
% \[
% 		s_4=\min\{i\in[r] \ : \ i>s_3 \text{ and } P \text{ is hierarchical at level } i+1\}. 
% \]
% Thus, denote
% $$J_{s_1+i}=[n_1+\cdots +n_{s_2+i-1}+1,n_1+\cdots+n_{s_2+i}]$$
% for every $i\geq 1$ satisfying $s_2+i<s_3$ and 
% \[
% 	J_{s_1+(s_3-s_2)}=[n_1+\cdots+n_{s_3-1}+1,n_1+\cdots+n_{s_4}].
% \]


% \noindent\textbf{(3)} Consider
% \[
% 	s_5=\min\{i\in[r] \ : \ i>s_4 \text{ and } P \text{ is not hierarchical at level } i+1\} 
% \]
% and
% \[
% 	s_6=\min\{i\in[r] \ : \ i>s_5 \text{ and } P \text{ is hierarchical at level } i+1\}. 
% \]
% Therefore,
% \[
% 	J_{s_1+(s_3-s_2)+i}=[n_1+\cdots+n_{s_4+i-1}+1,n_1+\cdots+n_{s_4+i}]
% \]
% for every $i\geq 1$ satisfying $s_4+i<s_5$ and
% \[
% 	J_{s_1+(s_3-s_2)+(s_5-s_4)}=[n_1+\cdots+n_{s_5-1}+1,n_1+\cdots+n_{s_6}].
% \]
% Proceeding in this way, we construct a partition of $[n]$ given by $J_1\cup \ldots \cup J_h$ for some $h$. An arbitrary iteration of the process can be described as follows.
% \noindent\textbf{(General Case)} Consider $t$ to be an odd integer, then
% \[
% 	s_t=\min\{i\in[r] \ : \ i>s_{t-1} \text{ and } P \text{ is not hierarchical at level } i+1\}	
% \]
% and,
% \[
% 	s_{t+1}=\min\{i\in[r] \ : \ i>s_{t} \text{ and } P \text{ is hierarchical at level } i+1\}.	
% \]
% Furthermore,  
% \[
% 	J_{s_1+(s_3-s_2)+\cdots+(s_{2t-1}-s_{2t-2})}=[n_1+\cdots+n_{s_{2t-1}-1}+1,n_1+\cdots+n_{2t}]
% \]
% and
% \[
% 	J_{s_1+(s_3-s_2)+\cdots+(s_{2t-1}-s_{2t-2})+i}=[n_1+\cdots+n_{s_{2t}+i-1}+1,n_1+\cdots+n_{2t+i}].	
% \]
% Therefore, out of $P$ we can define two hierarchical posets:

% \textbf{Upper neighbor:} Let $P^{+}$ be the poset over $\left[n\right]  $
% with the same level decomposition of $P$ and for every $a\in \Gamma_P^i$ and $b\in \Gamma_P^j$ with $a\neq b$, define $a\leqslant_{P^+}b$ if, and only if, $i<j$.

% \textbf{Lower neighbor: }Let $P^{-}$ be the poset over $\left[  n\right]  $ with level  hierarchy $\left[  n\right]  =J_{1}\cup
% J_{2}\cup\ldots\cup J_{h}$ 
% and for $a\in \Gamma_P^i$ and $b\in \Gamma_P^j$ with $a\neq b$, we have $a\leqslant_{P^-}b$ if, and only if, $ i<j$.

% In order to clarify the definitions of the upper and lower neighbors, we shall present an illustrative example. 
% \begin{example}
% Let $P$ be a poset with $4$ levels.	Suppose $\mathcal{H}(P)=\{1,2,4\}$. Consider the simplified Hasse diagram representing whether the poset is hierarchical at a particular level or not: if two consecutive levels are joined by a dotted line, then the poset is not hierarchical at the level above the other; if two consecutive levels are joined by a line, then the poset is hierarchical at the level above. Therefore, the diagrams of $P^-$, $P$ and $P^+$ are as follows:
	
% 		\begin{figure}[h]
% 	\centering
% 		\includegraphics[scale=0.7]{hierel.pdf}
% 	\end{figure}
% 	\noindent We stress that $\Gamma_{P^-}^2=\Gamma_P^2\cup \Gamma_P^3 \cup \Gamma_P^4$ since the smallest level where $P$ is hierarchical at this level is the third one. Hence, in order to construct $P^-$, all levels of $P$ above the level $2$ are gathered in the second level of $P^-$.
% \end{example}

% It is easy to see that:

% \begin{itemize}
% \item[(a)] $P^{+}$ and $P^{-}$ are hierarchical posets and $P$ is hierarchical if, and only if,  $P=P^{+}=P^{-}$;

% \item[(b)] Considering the natural order $\leq$ on $\mathcal{P}_{n}$, we have that
% $P^{-}\leq P\leq P^{+}$. Moreover, 
% $$
% P^{-} =\max\left\{  Q\in\mathcal{P}_{n} \ : \ Q\leq P \text{ and } Q\text{ is hierarchical}\right\}$$%
% and
% $$P^{+}  =\min\left\{  Q\in\mathcal{P}_{n} \ : \ P\leq Q \text{ and } Q\text{ is hierarchical}%
% \right\}.$$

Considering the natural order $\leq$ on $\mathcal{P}_{n}$, out of $P$ we can define two hierarchical posets:

 \textbf{1 - Upper neighbor:} 
$$P^{+}  =\min\left\{  Q\in\mathcal{P}_{n} \ : \ P\leq Q \text{ and } Q\text{ is hierarchical}%
 \right\}.$$

 \textbf{2 - Lower neighbor: }
$$P^{-} =\max\left\{  Q\in\mathcal{P}_{n} \ : \ Q\leq P \text{ and } Q\text{ is hierarchical}\right\}.$$

The next proposition follows directly from Corollary \ref{col10}.

\begin{proposition}\label{bound} For any linear code $\mathcal{C}$, 
\[
\mathcal{D}_{P^{+}}\left(
\mathcal{C}\right)  \leq \mathcal{D}_{P}\left(  \mathcal{C}\right) \leq  \mathcal{D}_{P^{-}}\left(  \mathcal{C}\right).
\]

\end{proposition}

% \begin{example}
% 	Consider the posets of Example \ref{ex3poset} and denote $P=P_3$, then $P^+=P_1$ and $P^-=P_2$. Furthermore, using the decompositions in that example (which are maximal), we conclude that 
% 	\[
% 		\mathcal{D}_{P^+}(\mathcal{C})=1/2 \text{, } \mathcal{D}_{P}(\mathcal{C})=2 \text{ and } \mathcal{D}_{P^-}(\mathcal{C})=3.
% 	\]
% \end{example}
If $P$ is not hierarchical, both inequalities are strict for some code
$\mathcal{C}$. Moreover, the bounds are tight, in the sense that, given a poset $P$, there are codes $\mathcal{C}_1$ and $\mathcal{C}_2$ such that $\mathcal{D}_{P^{+}}\left(
\mathcal{C}_1\right)  =\mathcal{D}_{P}\left(  \mathcal{C}_1\right)  $ and  $\mathcal{D}_{P^{-}%
}\left(  \mathcal{C}_2\right)  =\mathcal{D}_{P}\left(  \mathcal{C}_2\right)  $ (just consider any code $\mathcal{C}$ with $supp(\mathcal{C})\subset \Gamma_P^1$).

\medskip 

\section{Applications to Coding Theory}\label{sec:applications}

The poset-metrics, as much as the decomposition problem, arose in the context of coding theory, what justified the use of the terminology and the notation from the area: code and codeword for vector subspace and vector, respectively. Now comes the time to justify it with some content, i.e., with applications to coding theory. 


 We combine the knowledge available for hierarchical posets with the degree's bound found in Section \ref{sub:hierar_bouds}  to produce bounds for the most important invariant in coding theory (the packing radius) and to optimize the traditional full lookup table searching algorithm in the syndrome decoding process.
 


\subsection{Packing Radius Bounds}\label{sub:pack}
	
	
	If $\mathbb{F}_q^n$ is endowed with a $P$-metric, an $[n,k,\delta_P]$ $P$-code is an $[n,k]$-linear code $\mathcal{C}$ with \emph{minimum distance}
	\[
	\delta_P=\min \{w_P(c) : c\in\mathcal{C}\} = \min \{ d_P(c,c'): c,c'\in\mathcal{C},c\neq c'  \}.
	\]  
	In the context of coding theory, the minimum distance is considered the most important metric parameter of a code. Its importance comes from the fact that it may ensures the correction of a certain amount of errors. If $P$  is an anti-chain, the $P$-weight and metric are known as Hamming weight and metric, denoted by $w_H$ and $\delta_H$, respectively. This is the most important setting in the context of coding theory. In this situation, let us say that a message $c\in \mathcal{C}$ is transmitted  and it is received with errors as a message $v=c+e$, where $e\in\mathbb{F}_q^n$ is the error vector. If $\delta_H$ is the minimum distance of $\mathcal{C}$ and $w_H(e)\leq \lfloor (\delta_H-1)/2 \rfloor$ (where $ \lfloor \cdot \rfloor  $ is the floor function), then we can ensure that the original message $c$ can be recovered. The quantity $\lfloor (\delta_H-1)/2 \rfloor$ happens to be what is known as the \emph{packing radius} of the code, defined, in general, as 
	\[
	\mathcal{R}_P(\mathcal{C})=\max\{r\geq 0: B_P(c,r)\cap B_P(c',r)=\emptyset \ \forall c,c'\in\mathcal{C},c\neq c'  \},
	\] 
	where $B_P(u,r)=\{v\in\mathbb{F}_q^n:d_P(u,v)\leq r   \}$ is the \emph{$P$-ball} with center $u$ and radius $r$.
	
	When considering a general poset metric, the packing radius maintains the same property of evaluating the correction capability. However, in general, the minimum distance does not determine the packing radius, only bounds for it (see \cite{d2015packing}). Indeed, hierarchical posets are the unique posets for which the packing radius of a code is a function of its minimum distance, as can be seen in \cite{MachadoPinheiroFirer}. Determining the packing radius, in general settings, is a very difficult task, it may be an NP-hard problem even considering the case of a code with only two elements (see \cite{d2015packing}). For this reason, working with a general poset, the best we can do is to find bounds and we do it considering maximal $P$-decompositions of the code. We start with two simple propositions.

%Maximal $P$-decompositions may be useful to determine bounds for the packing radius of a code. We remark that the packing radius of codes according to hierarchical metrics is completely characterized and depends essentially on the minimum distance of the code, see \cite{machado2015characterization}. We also remark that for non-hierarchical metrics, the complexity to determine the packing radius of a single vector is NP-hard (see \cite{d2015packing}) and the packing vector is not necessarily a vector with minimum distance.

\begin{proposition}\label{prop15}
	Let $\mathscr{C}=(\mathcal{C}^\prime;\mathcal{C}_0;\mathcal{C}_i)_{i=1}^r$ be a $P$-decomposition for $\mathcal{C}$. Then,
	\[
		\mathcal{R}_P(\mathcal{C}) \leq \min_{i\in\{1,\ldots,r\}} \mathcal{R}_P(\mathcal{C}_i).
	\]
\end{proposition}

\begin{IEEEproof}
	Note that $\mathcal{R}_P(\mathcal{C})=\mathcal{R}_P(\mathcal{C}^\prime)$. Furthermore, since each $\mathcal{C}_i$ is a subcode of $\mathcal{C}^\prime$, it follows that $\mathcal{R}_P(\mathcal{C})\leq \mathcal{R}_P(\mathcal{C}_i)$ for every $i\in \{1,\ldots,r\}$.
\end{IEEEproof}
% \begin{proof}
% 	Every $c\in\mathcal{C}$ can be expressed as $c=c_1+\cdots+c_r$ with $c_i\in\mathcal{C}_i$, so it is sufficient to prove that 
% 	\[
% 	 	\mathcal{R}_P(c_i)\leq \mathcal{R}_P(c)
% 	 \] 
% 	 for some $i\in\{1,\ldots,r\}$. Suppose $x\in B(r,c)\cap B(r,\mathbf{0})$, where $r=\mathcal{R}_P(c_i)$, then $d_P(x,c)\leq r$, so
% 	 \[
% 	 	d_P(x-c+c_i,c_i)\leq r.
% 	 \]
% 	 But $d_P(x-c+c_i,\mathbf{0})\leq r$ because $supp(x-c+c_i)\subset supp(x-c)$ and this leads to a contradiction since $x-c+c_i\in B(r,c_i)\cap B(r,\mathbf{0})=\emptyset$. Therefore, $B(r,c)\cap B(r,\mathbf{0})=\emptyset$, i.e., $ \mathcal{R}_P(c) \geq \mathcal{R}_P(c_i)$.
% \end{proof}

%In general, we have the following result

\begin{proposition}\label{bound01}
	If $P\leq Q$, then $ \mathcal{R}_P(\mathcal{C})\leq  \mathcal{R}_Q(\mathcal{C})$ for every linear code $\mathcal{C}$.
\end{proposition}

\begin{IEEEproof}
	If follows directly from the fact that 
	$$B_Q(r,c)\cap B_Q(r,\mathbf{0})\subset B_P(r,c)\cap B_P(r,\mathbf{0})$$ for every $c\in\mathcal{C}$ and any integer $r\geq 0$. 
\end{IEEEproof}

% {\color{blue} Consider the projections  
% $\pi_i:\mathbb{F}_q^n \longrightarrow \mathbb{F}_q^{n_i}$ (note that $n_i=|supp(\mathcal{C}_i)|$) defined by
% \[
% 	\pi_i(x_1,\ldots,x_n) = (x_{i_1},\ldots,x_{i_s})
% \]
% where $i_1<\cdots<i_s$ and $\{i_1,\ldots,i_s\}=supp(\mathcal{C}_i)$. Consider on $\mathbb{F}_q^{n_i}$ the metric $d_{\pi_i}$ induced by $\pi_i$ in the sense that $\pi_i:V_i \rightarrow \mathbb{F}_q^{n_i}$ is an isometry. Then, by the definition of $d_{\pi_i}$, 
% \begin{equation}\label{eq10}
% 	\mathcal{R}_P(\mathcal{C}_i)=\mathcal{R}_{d_{\pi_i}}(\pi_i(\mathcal{C}_i)).
% \end{equation}
% }
Using Proposition \ref{bound01} and the upper and lower neighbours $P^+$ and $P^-$ defined in the previous section, bounds for the packing radius of codes according to hierarchical posets may be obtained. The proof of the next proposition follows straight from the previous proposition.
\begin{proposition}\label{prop16}
	Given a maximal $P$-decomposition $\mathscr{C}=(\mathcal{C}^\prime;\mathcal{C}_0;\mathcal{C}_i)_{i=1}^r$ for $\mathcal{C}$, 
	\[
		\mathcal{R}_{P^-}(\mathcal{C}_i)\leq \mathcal{R}_P(\mathcal{C}_i) \leq \mathcal{R}_{P^+}(\mathcal{C}_i)
	\]
	for every $i\in\{1,\ldots,r\}$.
\end{proposition}

Propositions \ref{prop15} and \ref{prop16} yield the following upper and lower bounds for the packing radius:
\begin{equation}\label{eq11}
	\mathcal{R}_{P^-}(\mathcal{C}) \leq \mathcal{R}_P(\mathcal{C})\leq \min_{i\in\{1,\ldots,r\}}\mathcal{R}_{P^+}(\mathcal{C}_i)
\end{equation}
for every $i\in\{1,\ldots,r\}$.
% and 
%\begin{equation}\label{eq12}
%		\min_{i\in \{1,\ldots,r\}} \mathcal{R}_{P^-}(\mathcal{C}_i) \leq \mathcal{R}_P(\mathcal{C}).
%\end{equation}

Since $P^+$ and $P^-$ are hierarchical, these bounds are obtained just by finding the minimum distance of $\mathcal{C}$ and each code $\mathcal{C}_i$ according to $P^-$ and $P^+$, respectively. Furthermore, each of these codes may be decomposed according to the lower and upper neighbors in order to simplify and optimize the search for the minimum distance. If $P$ is hierarchical, we obtain equalities in the bounds obtained in Proposition \ref{prop16} and in Inequality (\ref{eq11}), hence, these bounds are tight.

\subsection{Optimizing the Full Lookup Table Searching in Syndrome Decoding}\label{sub:syndrome}
%{\color{blue}Complexity of Syndrome Decoding Algorithm}

%In the Section \ref{scesyn} of the first chapter it was characterized the metrics where syndrome decoding coincides with the metric decoder, since poset metrics are invariant by translations, syndrome decoding can be done for poset metrics in the same way as in the Hamming case, just exchanging syndrome leaders to be vectors with minimal poset weight, instead of the Hamming weight. 

The core of coding theory is the existence of errors: the messages to be sent are elements of a code $ \mathcal{C}\subset\mathbb{F}_q^n $, but, in the occurrence of errors, any element of $\mathbb{F}_q^n $ may be received. Once $y\in \mathbb{F}_q^n $ arrives, the receiver needs to decide what was the original message. There are essentially to types of decision criteria: probabilistic and deterministic. We are interested in the deterministic criteria determined by metrics, the well-known \textit{minimum distance decoding}.

Minimum distance decoding works as follows: once $y\in \mathbb{F}_q^n $ is received, we look for one of the codewords that minimizes the distance to $y$. We are in a good situation if the minimum is unique and this is the case if the weight of the error was not greater than the packing radius. 
Despite the fact that the minimum distance decoding is very simple to describe as a criterion, its implementation as an algorithm is very difficult, since codes (for practical purposes) are very large and searching on very large sets is infeasible. 

Syndrome decoding is an algorithm to perform minimum distance decoding that works for every linear code and every metric that is determined by a weight or, equivalently,  a metric that is invariant by translations. %, in the sense that $d(u,v)=d(u+w,v+W)$, for all $u,v,w\in \mathbb{F}_q^n $. 
Given a code $ \mathcal{C}\subset\mathbb{F}_q^n $, for each coset $u+ \mathcal{C}$, consider an element with minimal weight, called coset leader. In syndrome decoding, once a message $y$ is received, instead looking for $c\in\mathcal{C}$ that minimizes $d_P(y,c)$, one looks for a coset leader $u$ such that $T(u-y)=0$, where $T:\mathbb{F}_q^n\rightarrow \mathbb{F}_q^{n-k}$ is a linear map that has $\mathcal{C}$ as its kernel (determined by the parity check matrix, in coding jargon). The advantage of using syndrome decoding is the exchange of a lookup table of size $q^k$ by one of size $q^{n-k}$, what is smaller, in general, since coding theory looks for $[n,k]$-codes with $k/n$ close to $1$. This quantity, $q^{n-k}$, is an algebraic invariant that does not depend on the metric.

We do not explain here the details of syndrome decoding (it can be found in any book on coding theory, for example \cite[Section 1.11]{huffman2003fundamentals}), but it is a very established process and all we need is to state that when we use the poset metric $d_P$, we mean that the minimality of the coset leader refers to the $P$-weight $w_P$. 

In this section we show how we can reduce the searching process in the lookup table of syndrome decoding, by  considering $P$-decompositions of a code. Roughly speaking, the finest the decomposition, the smaller the search table. Let us do it in details.


%Considering metrics determined by weights, hence invariant by translations, a syndrome algorithm, which depends on the choice of the coset leaders, is an implementation of an MD-decoder. This is the case for poset metrics.
%Given an $[n,k,\delta]_q$ code $\mathcal{C}$, a look-up table for syndrome decoding of $\mathcal{C}$ (the table composed by the coset leaders) has $q^{n-k}$ elements. This is an algebraic invariant and does not depend on the metric.

% Nevertheless, we can use refinements of decompositions in order to minimize the search space (number of cosets) by isometrically immersing the code into a smaller dimension space or by performing syndrome in each component of the decomposition. In this section we describe the cases for which such improvements are possible.


Let $\mathscr{C}=\left(  \mathcal{C};\mathcal{C}_{0};\mathcal{C}_{i}\right)_{i=1}^r$ be a maximal $P$-decomposition of an $[n,k,\delta]_q$ code $\mathcal{C}$. 
Initially, note that in order to perform decoding, we can ignore the component $V_{0}$ (recall that $V_i$ is the support-space of $\mathcal{C}_i$) since we know that any codeword $c=(c_1,\ldots,c_n)\in \mathcal{C}$ should have $c_{j}=0$ for every $j\in\left[n\right]  ^{\mathcal{C}}$. Consider the projection 
$\pi:\mathbb{F}_q^n \longrightarrow \mathbb{F}_q^{n_1+\cdots+n_r}$ (recall that $n_i=|supp(\mathcal{C}_i)|$) defined by
\[
\pi(x_1,\ldots,x_n) = (x_{i_1},\ldots,x_{i_s})
\]
where  $\{i_1,\ldots,i_s\}=supp(\mathcal{C})$ and we assume $i_1<\cdots<i_s$ . The map $\pi_{1,\ldots,r}=\pi|_{\oplus_{i=1}^r V_i}$, the restriction of $\pi$ to the space $\oplus_{i=1}^r V_i$, is a bijection.  Therefore, by pushing forward the metric in the restriction, we obtain the metric $d_P^\pi$ in $\mathbb{F}_q^{n_1+\cdots+n_r}$ defined by
\[
d_P^\pi(x,y):=d_P(\pi_{i,\ldots,r}^{-1}(x),\pi_{i,\ldots,r}^{-1}(y))
\]
for every $x,y\in\mathbb{F}_q^{n_1+\cdots+n_r}$. The metric $d_P^\pi$ turns the restriction map $\pi_{1\ldots r}$ into a linear isometry. Because $\mathcal{C}$ is a subspace of $V_1\oplus \ldots\oplus V_r$, the proof of the proposition below follows straight from these observations. 
\begin{proposition}\label{propo}
	The metric-decoding criteria of $\mathbb{F}_q^n$ for $\mathcal{C}$ is equivalent to the metric-decoding criteria of $\mathbb{F}_q^{n_1+\cdots+n_r}$ for $\pi(\mathcal{C})$, i.e.,
	\[
	d_P(c^\prime,y)=\min_{c\in \mathcal{C}} d_P(c,y) 
	\iff 
	d_P^\pi(\pi(c^\prime),\pi(y))=\min_{c\in \pi(\mathcal{C})} d_P^\pi(c,\pi(y)).
	\]
\end{proposition}

By Proposition \ref{propo}, to perform syndrome decoding, instead of using a lookup table with $|\mathbb{F}_q^n/\mathcal{C}|=q^{n-k}$ elements, we can reduce the number of cosets to $|\mathbb{F}_q^{n_1+\cdots+n_r}/\pi(\mathcal{C})|=\prod_{i=1}^r q^{n_i-k_i}$ elements. Note that 
$$q^{n_0} \times \prod_{i=1}^r q^{n_i-k_i} = q^{n-k}.$$
Therefore, $P$-decompositions having the maximum possible number of elements in the support of $\mathcal{C}_0$ are the best ones in order to perform syndrome decoding. 

%Until now we have just immersed a code in a smaller dimension space preserving the metric decoding characteristics. This is achieved by increasing the dimension of $\mathcal{C}_0$, that is, by decomposing the code using aggregations. Splitting was first used in \cite{felix2012canonical} to improve the performance of syndrome decoding for hierarchical posets. In the hierarchical case, we have a sort of ``maximal reduction'' since decode can be done ``independently'' in each level (due to the decomposition obtained in Corollary \ref{col6}). Considering split operations, we will now describe how to improve the syndrome decoding ``complexity'', i.e., how to decrease the cardinality of the look-up table for general posets.


Besides this possible (and a-posteriori irrelevant) gain in the cardinality of the syndrome lookup table obtained considering aggregations, there is a more significant gain that can be obtained through the splitting operation.


\begin{proposition}\label{prop001}
	If 
	$$\langle supp(\mathcal{C}_i)\rangle_P \cap \langle supp(\mathcal{C}_j)\rangle_P = \emptyset $$
	for all $i\neq j$ and $i,j\neq 0$, then given $y\in\mathbb{F}_q^n$, 
	\[
	\min_{c\in \mathcal{C}} d_P(c,y) = \sum_{i=1}^r \min_{c\in \mathcal{C}_i} d_{P}^{\pi_i}(\pi_i(c),\pi_i(y)).
	\]
\end{proposition}

\begin{IEEEproof}
	Note that if $c\in\mathcal{C}$, then $c=c_1+\cdots+c_r$ with $c_i\in\mathcal{C}_i$ and for every $y_i\in\mathbb{F}_q^{n_i}$,
	\[
	supp(y_i-c_i)\subset \langle supp(\mathcal{C}_i)\rangle=supp(V_i).
	\] 
	Then,
	\[
	d(y,c)=d(y_1,c_1)+\cdots+d(y_r,c_r),
	\]
	where $y=y_1+\cdots+y_r$ and $y_i\in\mathbb{F}_q^{n_i}$ for all $i\in [r]$. 
\end{IEEEproof}
%The proof of the next corollary follows straight from Propositions \ref{propo} and \ref{prop001}.
%\begin{corollary}\label{cool1}
%	If 
%	$$\langle supp(\mathcal{C}_i)\rangle_P \cap \langle supp(\mathcal{C}_j)\rangle_P = \emptyset $$
%	for all $i\neq j$ and $i,j\neq 0$, then given $y\in\mathbb{F}_q^n$, 
%	\[
%	\min_{c\in \mathcal{C}} d_P(c,y) = \sum_{i=1}^r \min_{c\in \pi_i(\mathcal{C}_i)} d_{P}^{\pi_i}(c,\pi_i(y)),
% \]
% where $\pi_i$ is the projection of $V_i$ into $\mathbb{F}_q^{n_i}$.
%\end{corollary}

Due to Proposition \ref{prop001}, if the ideals generated by each component are disjoint, syndrome decoding can be done independently in each component $\mathcal{C}_i$. Therefore, the number of cosets can be reduced from $q^{n-k}$ elements to $\sum_{i=1}^r q^{n_i-k_i}$ elements, where the last one is the sum of the cosets in each quotient $\mathbb{F}_q^{n_i}/\pi_i(\mathcal{C}_i^{\prime})$. More generally, if $r$ is a disjoint union of subsets $I_i$, i.e., $[r]=I_1 \sqcup \ldots \sqcup I_s$, and 
\[
\langle supp(\oplus_{i\in I_j} \mathcal{C}_i)\rangle_P \cap \langle supp(\oplus_{i\in I_l} \mathcal{C}_i) \rangle_P=\emptyset,
\]
for every $j\neq l$, then decoding can be separately done in each projection of $\oplus_{i\in I_j} \mathcal{C}_i$ into $\mathbb{F}_q^{N}$ where $N=\sum_{i\in I_j} n_i$.

Until now, in order to obtain the reductions, it was not necessary to change the syndrome decoding algorithm; we just performed it in a different (smaller) space. The hierarchical relation among elements of the poset will provide us a ``quasi-independent'' syndrome decoding algorithm that is performed by choosing first coordinates that hierarchically dominate others, therefore we will call this algorithm a \index{Leveled Syndrome Decoding}\textit{Leveled Syndrome Decoding}. 

Given two subsets $I,J\subset [n]$, we say that $I$ and $J$ are \textit{hierarchically related} if every element in $I$ is smaller than every element in $J$. Suppose $[r]$ is an ordered disjoint union of sets, $[r]=I_1 \sqcup \ldots \sqcup I_s$, such that $supp(\oplus_{i\in I_j} \mathcal{C}_i)$ is hierarchically related with $supp(\oplus_{i\in I_{j+1}}\mathcal{C}_i)$ for every $j\in\{1,\ldots,s-1\}$, so if $i_0\in supp(\oplus_{i\in I_{j_0}} \mathcal{C}_i)$, then $i_0\leqslant i$ for every $i\in supp(\oplus_{i\in I_l} \mathcal{C}_i)$ with $l>j_0$.
By using the well-known syndrome decoding algorithm, the leveled syndrome decoding algorithm is as follows: 
\bigskip


\textbf{Input:} $y=y_1+\cdots+y_s \in\mathbb{F}_q^n$ where $y_i\in \oplus_{j\in I_i} V_j$


\hspace{0.6cm}For each $i\in\{1,\ldots,s\}$ do

\hspace{0.9cm}Decode $\pi_{j\in I_i}(y_i)\in\mathbb{F}_q^{\sum_{j\in I_i} n_j}$ using syndrome ($d_P^{\pi_{j\in I_i}}$) outputting $c_i\in \pi_{j\in I_i}(\oplus_{j\in I_i} \mathcal{C}_j)$

\textbf{Output:} $c=\pi_{j\in I_1}^{-1}(c_1)+\cdots+\pi_{j\in I_s}^{-1}(c_s)$.
\begin{center}
	\hspace{0.3cm}Leveled Syndrome Decoding Algorithm 1.	
\end{center}


% \vspace{0.5cm}




% \vspace{0.5cm}
% \hrule
% \vspace{0.2cm}
% \noindent Leveled Syndrome Decoding Algorithm 1.
% \vspace{0.2cm}
% \hrule
% \vspace{0.2cm}
% \textbf{Input:} $y=y_1+\cdots+y_s \in\mathbb{F}_q^n$ where $y_i\in \oplus_{j\in I_i} V_j$
% \vspace{0.2cm}
% \hrule
% \vspace{0.2cm}
% \noindent For each $i\in\{1,\ldots,s\}$ do

% Decode $\pi_{j\in I_i}(y_i)\in\mathbb{F}_q^{\sum_{j\in I_i} n_j}$ using syndrome ($d_P^{\pi_{j\in I_i}}$) outputting $c_i\in \pi_{j\in I_i}(\oplus_{j\in I_i} \mathcal{C}_j)$

% \vspace{0.2cm}
% \hrule
% \vspace{0.2cm}
% \textbf{Output:} $c=\pi_{j\in I_1}^{-1}(c_1)+\cdots+\pi_{j\in I_s}^{-1}(c_s)$.
% \vspace{0.2cm}
% \hrule
% \vspace{0.5cm}
Furthermore, performing an ordered syndrome decoding from the higher level to the smaller ones, we can proceed as follows:

\bigskip


\textbf{Input:} $y=y_1+\cdots+y_s \in\mathbb{F}_q^n$ where $y_i\in \oplus_{j\in I_i} V_j$

\hspace{0.3cm}For $i=s$ to $1$, do

\hspace{0.6cm}If $\pi_{j\in I_i}(y_i)\in \oplus_{j\in I_i} \mathcal{C}_j$ do

\hspace{0.9cm}$c_i=\pi_{j\in I_i}(y_i)$;

\hspace{0.6cm}else do

\hspace{0.9cm}Decode $\pi_{j\in I_i}(y_i)\in\mathbb{F}_q^{\sum_{j\in I_i} n_j}$ using syndrome ($d_P^{\pi_{j\in I_i}}$) outputting $c_i\in \pi_{j\in I_i}(\oplus_{j\in I_i} \mathcal{C}_j)$;

\hspace{0.9cm}Go to Output;

\hspace{0.6cm}end if;

\hspace{0.3cm}end For;

\textbf{Output:} $c=\pi_{j\in I_i}^{-1}(c_i)+\pi_{j\in I_{i+1}}^{-1}(c_{i+1})+\cdots+\pi_{j\in I_s}^{-1}(c_s)$.


\begin{center}
	\hspace{0.3cm}Leveled Syndrome Decoding Algorithm 2.	
\end{center}


% \vspace{0.5cm}
% \hrule
% \vspace{0.2cm}
% \noindent Leveled Syndrome Decoding Algorithm 2.
% \vspace{0.2cm}
% \hrule
% \vspace{0.2cm}
% \textbf{Input:} $y=y_1+\cdots+y_s \in\mathbb{F}_q^n$ where $y_i\in \oplus_{j\in I_i} V_j$
% \vspace{0.2cm}
% \hrule
% \vspace{0.2cm}
% \noindent For $i=s$ to $1$, do

% \noindent \hspace{0.5cm}If $\pi_{j\in I_i}(y_i)\in \oplus_{j\in I_i} \mathcal{C}_j$ do

% \noindent \hspace{1cm}$c_i=\pi_{j\in I_i}(y_i)$;

% \noindent \hspace{0.5cm}else do

% \noindent \hspace{1cm}Decode $\pi_{j\in I_i}(y_i)\in\mathbb{F}_q^{\sum_{j\in I_i} n_j}$ using syndrome ($d_P^{\pi_{j\in I_i}}$) outputting $c_i\in \pi_{j\in I_i}(\oplus_{j\in I_i} \mathcal{C}_j)$;

% \noindent \hspace{1cm}Go to Output;

% \noindent \hspace{0.5cm}end if;

% \noindent end For;

% \vspace{0.2cm}
% \hrule
% \vspace{0.2cm}
% \textbf{Output:} $c=\pi_{j\in I_i}^{-1}(c_i)+\pi_{j\in I_{i+1}}^{-1}(c_{i+1})+\cdots+\pi_{j\in I_s}^{-1}(c_s)$.
% \vspace{0.2cm}
% \hrule
% \vspace{0.5cm}



The first algorithm was described in \cite{felix2012canonical} for the hierarchical poset case. The second one is also a minimum distance algorithm according to the poset metric $d_P$ (see the next proposition), but if there is an error in a particular level, the decoder outputs the null vector in the levels covered by the one where the error happened.  

\begin{proposition}
	Algorithm 2 determines a minimum distance decoder according to the metric $d_P$.
\end{proposition}

\begin{IEEEproof}
	Given $y\in\mathbb{F}_q^n$ and $c\in\mathcal{C}$, then
	\[
	d_P(y,c)=d_P^{\pi_{j\in I_i}}(\pi_{j\in I_i}(y),\pi_{j\in I_i}(c))
	\] 
	where $i$ is the largest integer such that $\pi_{j\in I_i}(y)\neq \pi_{j\in I_i}(c)$. Therefore, if $c^\prime\in\mathcal{C}$ satisfies
	\[
	d_P(y,c^\prime)=\min_{c\in\mathcal{C}} d_P(y,c),
	\]
	then $c^{\prime\prime}=c^\prime_s+c^\prime_{s-1}+\cdots+c^\prime_i$ also attains the minimum and this is the codeword returned by algorithm 2.
\end{IEEEproof}

Both the algorithms demand the storage of the lookup tables of each quotient $\mathbb{F}_q^{N}/\pi_{j\in I_i}(\oplus_{j\in I_i} \mathcal{C}_j)$ where $\sum_{j\in I_i} n_j$. The total number of elements we need to store is
\begin{equation}\label{am1}
\sum_{i=1}^s \prod_{j\in I_i} q^{n_j-k_j}.
\end{equation}
The difference between Algorithm 1 and 2 is that while the search in the Algorithm 1 is performed over all elements of the lookup table, the ordered procedure in Algorithm 2 stop the search in the first level where an error has occurred, i.e., if this happens in the level $i_0$, then the search is performed only over the lookup table of $\pi_{j\in I_{i_0}}(\oplus_{j\in I_{i_0}} \mathcal{C}_j)$ which has
\begin{equation}\label{am2}
\prod_{j\in I_{i_0}} q^{n_j-k_j}
\end{equation}
elements. Note that if the poset has only one level, the values of Expressions (\ref{am1}) and (\ref{am2}) coincide and are equal to $q^{n-k}$. However, the more the support of a $P$-decomposition of a code is partitioned into hierarchically related subsets,  the more we may transform factors in the product  (\ref{am1}) into parcels in expression (\ref{am2}).





%\section{Conclusion}
%{\color{red}colocar uma conclusao?}



% use section* for acknowledgment
\section*{Acknowledgment}


The authors would like to thank the S\~{a}o Paulo Research Foundation (Fapesp) for the financial support through grants 2013/25977-7 and 2016/01551-9. The second author would like to thank also CNPq, for the support through grant 303985/2014-3.


% Can use something like this to put references on a page
% by themselves when using endfloat and the captionsoff option.
\ifCLASSOPTIONcaptionsoff
  \newpage
\fi



    \bibliographystyle{plain} %mudar p IEEEtran no osx
    \bibliography{biblio}


%\begin{thebibliography}{1}

%\bibitem{IEEEhowto:kopka}
%H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus
%  0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999.

%\end{thebibliography}

% biography section
% 
% If you have an EPS/PDF photo (graphicx package needed) extra braces are
% needed around the contents of the optional argument to biography to prevent
% the LaTeX parser from getting confused when it sees the complicated
% \includegraphics command within an optional argument. (You could create
% your own custom macro containing the \includegraphics command to make things
% simpler here.)
%\begin{IEEEbiography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{mshell}}]{Michael Shell}
% or if you just want to reserve a space for a photo:
%
%\begin{IEEEbiography}{Jerry A. Pinheiro}
%Biography text here.
%\end{IEEEbiography}
%
%% if you will not have a photo at all:
%\begin{IEEEbiographynophoto}{Marcelo Firer}
%Biography text here.
%\end{IEEEbiographynophoto}

% insert where needed to balance the two columns on the last page with
% biographies
%\newpage



% You can push biographies down or up by placing
% a \vfill before or after them. The appropriate
% use of \vfill depends on what kind of text is
% on the last page and whether or not the columns
% are being equalized.

%\vfill

% Can be used to pull up biographies so that the bottom of the last one
% is flush with the other column.
%\enlargethispage{-5in}



% that's all folks
\end{document}



decomposicao_junho.bbl
\begin{thebibliography}{10}

\bibitem{alves2011standard}
Marcelo Muniz~S. Alves.
\newblock A standard form for generator matrices with respect to the
  niederreiter-rosenbloom-tsfasman metric.
\newblock In {\em Information Theory Workshop (ITW)}, pages 486--489. IEEE,
  2011.

\bibitem{alves2008error}
Marcelo Muniz~S. Alves, Luciano Panek, and Marcelo Firer.
\newblock Error-block codes and poset metrics.
\newblock {\em Advances in Mathematics of Communications}, 2(1):95--111, 2008.

\bibitem{extensiontheoremforfiniterings3}
Aleams Barra and Heide Gluesing-Luerssen.
\newblock Mac{W}illiams extension theorems and the local-global property for
  codes over {F}robenius rings.
\newblock {\em Journal of Pure and Applied Algebra}, 219(4):703 -- 728, 2015.

\bibitem{brualdi1995codes}
Richard~A Brualdi, Janine~Smolin Graves, and K~Mark Lawrence.
\newblock Codes with a poset metric.
\newblock {\em Discrete Mathematics}, 147(1):57--72, 1995.

\bibitem{deza2009encyclopedia}
Michel~Marie Deza and Elena Deza.
\newblock {\em Encyclopedia of distances}.
\newblock Springer, Berlin, 2009.

\bibitem{d2015packing}
Rafael Gregorio~Lucas D'Oliveira and Marcelo Firer.
\newblock The packing radius of a code and partitioning problems: The case for
  poset metrics on finite vector spaces.
\newblock {\em Discrete Mathematics}, 338(12):2143--2167, 2015.

\bibitem{felix2012canonical}
Luciano~Viana Felix and Marcelo Firer.
\newblock Canonical-systematic form for codes in hierarchical poset metrics.
\newblock {\em Advances in Mathematics of Communications}, 6(3):315--328, 2012.

\bibitem{gab}
Ernst Gabidulin.
\newblock A brief survey of metrics in coding theory.
\newblock {\em Mathematics of Distances and Applications}, pages 66--84, 2012.

\bibitem{golomb1969general}
S.~Golomb.
\newblock A general formulation of error metrics (corresp.).
\newblock {\em Information Theory, IEEE Transactions on}, 15(3):425--426, 1969.

\bibitem{ham}
Richard~W. Hamming.
\newblock Error detecting and error correcting codes.
\newblock {\em Bell System technical journal}, 29(2):147--160, 1950.

\bibitem{huffman2003fundamentals}
W.~Cary Huffman and Vera Pless.
\newblock {\em Fundamentals of error-correcting codes}.
\newblock Cambridge university press, 2003.

\bibitem{classification:macwilliamsidentity}
H.K. Kim and Dong~Yeol Oh.
\newblock A classification of posets admitting the {M}ac{W}illiams identity.
\newblock {\em IEEE Transactions on Information Theory}, 51(4):1424--1431,
  April 2005.

\bibitem{lee}
C.~Y. Lee.
\newblock Some properties of nonbinary error-correcting codes.
\newblock {\em IRE Transactions on Information Theory}, 4(2):77--82, 1958.

\bibitem{MachadoPinheiroFirer}
R.~Machado, J.~Pinheiro, and M.~Firer.
\newblock Characterization of metrics induced by hierarchical posets.
\newblock {\em IEEE Transactions on Information Theory}, PP(99):1--1, 2017.

\bibitem{niederreiter1991combinatorial}
Harald Niederreiter.
\newblock A combinatorial problem for vector spaces over finite fields.
\newblock {\em Discrete Mathematics}, 96(3):221--228, 1991.

\bibitem{niederreiter1992orthogonal}
Harald Niederreiter.
\newblock Orthogonal arrays and other combinatorial aspects in the theory of
  uniform point distributions in unit cubes.
\newblock {\em Discrete mathematics}, 106:361--367, 1992.

\bibitem{classification:schemes}
Dong~Yeol Oh.
\newblock Poset metrics admitting association schemes and a new proof of
  {M}acwilliams identity.
\newblock {\em Journal of the Korean Mathematical Society}, 50(5):917--931,
  2013.

\bibitem{panek2010classification}
Luciano Panek, Marcelo Firer, and Marcelo Muniz~Silva Alves.
\newblock Classification of niederreiter--rosenbloom--tsfasman block codes.
\newblock {\em Information Theory, IEEE Transactions on}, 56(10):5207--5216,
  2010.

\bibitem{panek2008groups}
Luciano Panek, Marcelo Firer, Hyun~Kwang Kim, and Jong~Yoon Hyun.
\newblock Groups of linear isometries on poset structures.
\newblock {\em Discrete Mathematics}, 308(18):4116--4123, 2008.

\bibitem{qureshiperfect}
Claudio Qureshi and Sueli~IR Costa.
\newblock On perfect q-ary codes in the maximum metric.
\newblock {\em Information Theory and Applications}, 2016.

\bibitem{ul}
Werner Ulrich.
\newblock Non-binary error correction codes.
\newblock {\em Bell System Technical Journal}, 46(6):1341--1388, 1957.

\end{thebibliography}
