m1_permutation.hlp

是一个经济学管理应用软件 很难找的 但是经济学学生又必须用到

{smcl}
{* 18mar2005}{...}
{cmd:help m1 permutation}
{hline}
{* index permutation matrix}{...}
{* index permutation vector}{...}

{title:Title}

{pstd}
{bf:[M-1] permutation -- An aside on permutation matrices and vectors}


{title:Syntax}
                          Permutation matrix     Permutation vector
        Action                 notation               notation
	{hline 65}
	permute rows            {it:B} = {it:P}{cmd:*}{it:A}           {it:B} = {it:A}{cmd:[}{it:p}{cmd:,.]}

        permute columns         {it:B} = {it:A}{cmd:*}{it:P}           {it:B} = {it:A}{cmd:[}.,{it:p}{cmd:]}

        unpermute rows          {it:B} = {it:P}{cmd:'}{it:A}           {it:B}={it:A} ; {it:B}{cmd:[}{it:p}{cmd:,.]} = {it:A}
							 or
						  {it:B} = {it:A}{cmd:[invorder(}{it:p}{cmd:),.]}

        unpermute columns       {it:B} = {it:A}{cmd:*}{it:P}{cmd:'}          {it:B}={it:A} ; {it:B}{cmd:[},.{it:p}{cmd:]} = {it:A}
							 or
						  {it:B} = {it:A}{cmd:[., invorder(}{it:p}{cmd:)]}
	{hline 65}

{pin}
A {it:permutation matrix} is an {it:n x n} matrix that is a row (or column)
permutation of the identity matrix.

{pin}
A {it:permutation vector} is a 1 {it:x} {it:n} or {it:n} {it:x} 1 vector 
of the integers 1 through {it:n}.

{pin}
The following permutation matrix and permutation vector are equivalent:

                     {c TLC}{c -}       {c -}{c TRC}                    {c TLC}{c -} {c -}{c TRC}
                     {c |} 0  1  0 {c |}                    {c |} 2 {c |}
               {it:P}  =  {c |} 0  0  1 {c |}     <==>    {it:p} =    {c |} 3 {c |}
                     {c |} 1  0  0 {c |}                    {c |} 1 {c |}
                     {c BLC}{c -}       {c -}{c BRC}                    {c BLC}{c -} {c -}{c BRC}

        Either can be used to permute the rows of 

                     {c TLC}{c -}          {c -}{c TRC}                 {c TLC}{c -}          {c -}{c TRC}
                     {c |} {it:a  b  c  d} {c |}                 {c |} {it:e  f  g  h} {c |}
               {it:A}  =  {c |} {it:e  f  g  h} {c |}   to produce    {c |} {it:i  j  k  l} {c |}
                     {c |} {it:i  j  k  l} {c |}                 {c |} {it:a  b  c  d} {c |}
                     {c BLC}{c -}          {c -}{c BRC}                 {c BLC}{c -}          {c -}{c BRC}

        and to permute the columns of 

	             {c TLC}{c -}       {c -}{c TRC}                    {c TLC}{c -}       {c -}{c TRC}
		     {c |} {it:m  n  o} {c |}                    {c |} {it:n  o  m} {c |}
                     {c |} {it:p  q  r} {c |}                    {c |} {it:q  r  p} {c |}
               {it:A}   = {c |} {it:s  t  u} {c |}      to produce    {c |} {it:t  u  s} {c |}
                     {c |} {it:v  w  x} {c |}                    {c |} {it:w  x  v} {c |}
	             {c BLC}{c -}       {c -}{c BRC}                    {c BLC}{c -}       {c -}{c BRC}


{title:Description}

{pstd}
Permutation matrices are a special kind of orthogonal matrix that, via
multiplication, reorder the rows or columns of another matrix.
Permutation matrices cast the reordering in terms of multiplication.

{pstd}
Permutation vectors also reorder the rows or columns of another matrix,
but they do it via subscripting.  This alternative method of achieving the same
end is, computerwise, more efficient, in that it uses less memory and less
computer time.

{pstd}
The relationship between the two is shown below.


{title:Remarks}

{pstd}
Remarks are presented under the headings

	{bf:1.  Permutation matrices}
	{bf:2.  How permutation matrices arise}
	{bf:3.  Permutation vectors}


    {title:1.  Permutation matrices}

{pstd}
A permutation matrix is a square matrix whose rows are a permutation of 
the identity matrix.  The following are the full set of all 2 {it:x} 2
permutation matrices:

		{c TLC}{c -}    {c -}{c TRC}
		{c |} 1  0 {c |}{right:(1)}
		{c |} 0  1 {c |}
		{c BLC}{c -}    {c -}{c BRC}

		{c TLC}{c -}    {c -}{c TRC}
		{c |} 0  1 {c |}{right:(2)}
		{c |} 1  0 {c |}
		{c BLC}{c -}    {c -}{c BRC}

{pstd}
Let {it:P} be a {it:n x n} permutation matrix.  If {it:n x m} matrix {it:A}
is premultiplied by {it:P}, the result is to reorder its rows.  For example,

             {it:P}       *       {it:A}        =       {it:PA}
	{c TLC}{c -}       {c -}{c TRC}     {c TLC}{c -}       {c -}{c TRC}       {c TLC}{c -}       {c -}{c TRC}
	{c |} 0  1  0 {c |}     {c |} 1  2  3 {c |}       {c |} 4  5  6 {c |}
	{c |} 0  0  1 {c |}  *  {c |} 4  5  6 {c |}   =   {c |} 7  8  9 {c |}{right:(3)}
	{c |} 1  0  0 {c |}     {c |} 7  8  9 {c |}       {c |} 1  2  3 {c |}
	{c BLC}{c -}       {c -}{c BRC}     {c BLC}{c -}       {c -}{c BRC}       {c BLC}{c -}       {c -}{c BRC}

{pstd}
Above, we illustrated the reordering using square matrix {it:A}, but {it:A} 
did not have to be square.

{p 4 4 2}
If {it:m x n} matrix {it:B} is postmultiplied by {it:P}, the result is to 
reorder its columns.  We illustrate using square matrix {it:A} again:

	     {it:A}       *       {it:P}        =       {it:AP}
	{c TLC}{c -}       {c -}{c TRC}     {c TLC}{c -}       {c -}{c TRC}       {c TLC}{c -}       {c -}{c TRC}
        {c |} 1  2  3 {c |}     {c |} 0  1  0 {c |}       {c |} 3  1  2 {c |}
        {c |} 4  5  6 {c |}  *  {c |} 0  0  1 {c |}   =   {c |} 6  4  5 {c |}{right:(4)}
        {c |} 7  8  9 {c |}     {c |} 1  0  0 {c |}       {c |} 9  7  8 {c |}
	{c BLC}{c -}       {c -}{c BRC}     {c BLC}{c -}       {c -}{c BRC}       {c BLC}{c -}       {c -}{c BRC}


{pstd}
Say that we reorder the rows of {it:A} by forming {it:PA}.  Obviously, we can
unreorder the rows by forming {it:P}^(-1){it:PA}.  Because permutation
matrices are orthogonal, their inverses are equal to their transpose.  Thus
the inverse of the permutation matrix (0,1,0\0,0,1\1,0,0) we have been using
is (0,0,1\1,0,0\0,1,0).  For instance, taking our results from (3)

             {it:P}{bf:'}      *      {it:PA}        =        {it:A}
	{c TLC}{c -}       {c -}{c TRC}     {c TLC}{c -}       {c -}{c TRC}       {c TLC}{c -}       {c -}{c TRC}
	{c |} 0  0  1 {c |}     {c |} 4  5  6 {c |}       {c |} 1  2  3 {c |}
	{c |} 1  0  0 {c |}  *  {c |} 7  8  9 {c |}   =   {c |} 4  5  6 {c |}{right:(3')}
	{c |} 0  1  0 {c |}     {c |} 1  2  3 {c |}       {c |} 7  8  9 {c |}
	{c BLC}{c -}       {c -}{c BRC}     {c BLC}{c -}       {c -}{c BRC}       {c BLC}{c -}       {c -}{c BRC}

{pstd}
Allow us to summarize:

{phang2}
    1.  A permutation matrix {it:P} is a square matrix whose rows are a
        permutation of the identity matrix.

{phang2}
    2.  {it:PA} = a row-permutation of {it:A}.

{phang2}
    3.  {it:AP} = a column-permutation of {it:A}

{phang2}
    4.  The inverse permutation is given by {it:P}'.

{phang2}
    5.  {it:P}'{it:PA} = {it:A}.

{phang2}
    6.  {it:APP}' = {it:A}.


    {title:2.  How permutation matrices arise}

{pstd}
Some of Mata's matrix functions implicitly permute the rows (or columns) of a
matrix.  For instance, the LU decomposition of matrix {it:A} is defined as

		{it:A} = {it:L}*{it:U}

{pstd}
where {it:L} is lower triangular and {it:U} is upper triangular.  For any
matrix {it:A}, one can solve for {it:L} and {it:U}, and Mata has a function
that will do that (see {bf:{help mf_lud:[M-5] lud()}}).  However, Mata's
function does not solve the problem as stated.  Instead, it solves

		{it:P}'{it:A} = {it:L}*{it:U}

{pstd}
where {it:P}' is a permutation matrix that Mata makes up!  Just to be clear,
Mata's function solves for {it:L} and {it:U}, but for a row permutation of
{it:A}, not {it:A} itself, although the function does tell you what
permutation it chose (the function returns {it:L}, {it:U}, and {it:P}).  The
function permutes the rows because, that way, it can produce a more accurate
answer.

{pstd}
You will sometimes read that a function engages in pivoting.  What that means
is that, rather than solving the problem for the matrix as given, it solves
the problem for a permutation of the original matrix, and the function chooses
the permutation in a way to minimize numerical roundoff error.  Functions that
do this invariably return the permutation matrix along with the other results,
because you are going to need it.

{pstd}
For instance, one use of LU decomposition is to calculate inverses.  If
{it:A} = {it:L}*{it:U} then {it:A}^(-1) = {it:U}^(-1)*{it:L}^(-1).
Calculating the inverses of triangular matrices is an easy problem, so one
recipe for calculating inverses is

{phang2}
1.  decompose {it:A} into {it:L} and {it:U},

{phang2}
2.  calculate {it:U}^(-1),

{phang2}
3.  calculate {it:L}^(-1),

{phang2}
4.  multiply the results together.