Sum of Traces of all Permutations of a Matrix

combinatoricsmatricespermutation-cyclespermutation-matricespermutations

I have a problem that reduces to finding the sum of the traces of all possible row permutations of a large matrix. For example if we had a 3×3 matrix, the possible row orderings would be (1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1), where the numbers represent the original row numbers. I want to find the sum of the Traces over all possible orderings.

I could calculate them all but that would scale at N!, which is too computationally expensive. Is there a way to simplify the problem? Or to approximate the answer without performing each computation?

Some extra information

The matrix represents probabilities so that all rows and columns sum to 1. And I know that the Trace of the original matrix is the largest term in the sum. (If any of that helps). Also, what I am actually trying to do is maximise the sum with respect to a parameter, lambda, which is used in a function to calculate the elements in the matrix. So if you want to transform the sum using an increasing function and maximise/calculate that instead then that would work too.

Best Answer

First of all, I claim that the sum of all order $n$ permutations matrices is equal to the matrix whose entries are all equal to $(n-1)!$. This is because for each $1\le i \le n$ and $1\le j\le n$, the number of permutations for which $\pi(i)=j$ is $(n-1)!$.

Another way of writing this constant matrix is $(n-1)!\def\1{{\bf1}}\1\1^T$, where $\1$ is a column vector of all ones.

Therefore, letting $B$ be any fixed $n\times n$ matrix, and $A_\pi$ be the permutations matrix corresponding to $\pi$, then \begin{align} \sum_{\pi\in S_n}\mathrm{tr}(A_\pi B) &=\mathrm{tr}\left(\left(\sum_{\pi}A_\pi\right)B\right) \\&=\mathrm{tr}\big((n-1)!\1\1^TB\big) \\&=(n-1)!\mathrm{tr}(\1^TB\1) \end{align} The last equality is the cyclic property of trace. Finally, $\mathrm{tr}(\1^TB\1)$ is the sum of the entries of $B$. Therefore, the sum of the traces of the permutations of a matrix is equal to $(n-1)!$ times the sum of the entries of that matrix.

Related Solutions

[Math] Number of distinct Arrays formed from swapping pairs

Duplicate but also unanswered

Here's a piece of c++ code i just wrote to help find and answer to this.

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    int n, m;
    cout << "Enter number of distinct numbers in array: ";
    cin >> n;
    vector<int> startNumbers;
    startNumbers.reserve(n);
    for (int i = 1; i < n + 1; ++i)
        startNumbers.push_back(i);
    vector<vector<int>> permutations;
    permutations.push_back(startNumbers);
    cout << "Enter number of swaps: ";
    cin >> m;
    for (int i = 0; i < m; ++i){
        vector<vector<int>> newPermutations;
        newPermutations.reserve(n*permutations.size());
        for (auto vec : permutations){
            for (int j = 0; j < n; ++j){
                for (int k = 0; k < n; ++k){
                    if (j != k){
                        auto tempVec = vec;
                        iter_swap(tempVec.begin() + j, tempVec.begin() + k);
                        newPermutations.push_back(tempVec);
                    }

                }

            }
        }
        sort(newPermutations.begin(), newPermutations.end());
        newPermutations.erase(unique(newPermutations.begin(), newPermutations.end()), newPermutations.end());
        newPermutations.shrink_to_fit();
        permutations = newPermutations;
    }
    cout <<"Number of distinct arrays: " << permutations.size() <<"\n";
    cout << "Distinct arrays: ";
    for (auto& p : permutations){
        cout << "[ ";
        for (auto& n : p){
            cout << n << " ";
        }
        cout << "] ";
    }
    cout << "\n";

    system("pause");
    return 0;
}

Notice this gets slow really fast.

Things to note for $N =$ numbers in array, $m =$ number of swaps:

maximum number of distinct arrays seems to be $\frac{N!}{2}$ and is reached at $m = N-2$ and stays at that value for bigger $m \geq N-2$
the corresponding OEIS-sequence

By checking out the paper mentioned in the OEIS article, you can find that the formula for calculating the number of half of the linearly inducible orderings of points in d-space is (Quote):

$$\frac{Q(n, d)}{2}= \sum_{k=0}^{d-1} \hspace{2pt}{}_{n}S_{k} = 1 + \sum_{2 \leq i \leq >d-1}{i} + \sum_{2 \leq i \leq j \leq d-1}ij + \text{ }... \text{ (d Terms)}$$

where ${}_{n}S_{k}$ is the sum of the possible products of numbers taken k at a time without repetition from the set $\{2, 3, ... ,n - 1 \}$.

I wrote a short program to calculate that formula:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int nSk(int n, int k){
    if (n < 2)
        return 1;
    if (k > n-2)
        return 0;
    vector<int> numbers;
    numbers.reserve(n - 2);
    for (int i = 0; i < n - 2; ++i){
        numbers.push_back(i + 2);
    }


    std::vector<bool> v(numbers.size());
    std::fill(v.end() - k, v.end(), true);
    int ret = 0;
    do {
        int tmpnum = 1;
        for (int j = 0; j < numbers.size(); ++j) {
            if (v[j])
            {
                tmpnum *= numbers[j];
            }
        }
        ret += tmpnum;
    } while (std::next_permutation(v.begin(), v.end()));
    return ret;
}

int main(){
    int n, d;
    cout << "enter n: ";
    cin >> n;
    cout << "ender d: ";
    cin >> d;
    int sum = 0;
    for (int k = 0; k < d; ++k){
        sum += nSk(n, k);
    }
    //sum *= 2;
    cout << "Q(n, d) =  "<< sum << endl;
    system("pause");
}

Entering $n=$ number of arrays and $d=$ number of swaps $+ 1$ gives you what you are looking for.

I have not figured out yet why the number of distinct arrays which can be formed by swapping exactly m times is related to the number of linearly inducible orderings of n points in d-space precisely, but will update as soon as i do.

Best Answer

Related Solutions

[Math] Number of distinct Arrays formed from swapping pairs

Related Question