Mixing
Orthogonal block matrix made of (signed) permutation matrices
$begingroup$
Let ${P_1, cdots, P_n}$ be $n$ permutation matrices with size $n times n$.
I'd like to build a $n^2 times n^2$ matrix $P$ such that $P^top P=P P^top$ is a multiple of the identity, and structured as follows:
$$
P = begin{pmatrix}P_1,|&cdots&|,P_n\hline\ &R&\&&end{pmatrix},
$$
where the sign matrix $R in {pm 1}^{(n^2 - n)times n^2}$ completes the first $n$ rows of $P$.
My questions are:
- Is it easy to build $R$? What are common possibilities?
- Can $R$ be also made by $n times n$ blocks, each one being a permutation matrix multiplied by a $pm 1$?
- Can we relate these blocks to the $P_i$'s of the first block-row?
(Update) Here is a solution I found for $n = 4$, that could help to understand my question.
If ${P_1, cdots, P_4}$ are some permutation matrices of size $2 times 2$ (or of any square size bigger, actually), then the following matrix is unitary:
$$
P = begin{pmatrix}
P_1& P_2& P_3& P_4\
P_2&-P_1&-P_4& P_3\
P_4&-P_3& P_2&-P_1\
-P_3&-P_4&P_1&P_2
end{pmatrix}
$$
Above, the second row is achieved by locally flipping the blocks of the first row, with some sign change rule; the 3rd row is obtained from the 2nd by flipping pair of blocks (and some sign change rule); and the 4th is obtained from the first by again locally flipping block of the 3rd.
My feeling is that the construction above should generalize to any $n$ that is a power of 2. Is there some "butterfly" like method behind? Or, having a look the signs, would it be possible to obtain $P$ from some matrix product of the ${P_i}$'s and an Hadamard matrix (but how integrate the flipping of blocks inside)? Many thanks.
Any starting point would be very much appreciated.
Thank you,
Laurent
matrices reference-request permutations orthogonal-matrices block-matrices
asked Jan 30 at 9:55
Laurent JacquesLaurent Jacques
12
$endgroup$
add a comment |
$begingroup$
Let ${P_1, cdots, P_n}$ be $n$ permutation matrices with size $n times n$.
I'd like to build a $n^2 times n^2$ matrix $P$ such that $P^top P=P P^top$ is a multiple of the identity, and structured as follows:
$$
P = begin{pmatrix}P_1,|&cdots&|,P_n\hline\ &R&\&&end{pmatrix},
$$
where the sign matrix $R in {pm 1}^{(n^2 - n)times n^2}$ completes the first $n$ rows of $P$.
My questions are:
- Is it easy to build $R$? What are common possibilities?
- Can $R$ be also made by $n times n$ blocks, each one being a permutation matrix multiplied by a $pm 1$?
- Can we relate these blocks to the $P_i$'s of the first block-row?
(Update) Here is a solution I found for $n = 4$, that could help to understand my question.
If ${P_1, cdots, P_4}$ are some permutation matrices of size $2 times 2$ (or of any square size bigger, actually), then the following matrix is unitary:
$$
P = begin{pmatrix}
P_1& P_2& P_3& P_4\
P_2&-P_1&-P_4& P_3\
P_4&-P_3& P_2&-P_1\
-P_3&-P_4&P_1&P_2
end{pmatrix}
$$
Above, the second row is achieved by locally flipping the blocks of the first row, with some sign change rule; the 3rd row is obtained from the 2nd by flipping pair of blocks (and some sign change rule); and the 4th is obtained from the first by again locally flipping block of the 3rd.
My feeling is that the construction above should generalize to any $n$ that is a power of 2. Is there some "butterfly" like method behind? Or, having a look the signs, would it be possible to obtain $P$ from some matrix product of the ${P_i}$'s and an Hadamard matrix (but how integrate the flipping of blocks inside)? Many thanks.
Any starting point would be very much appreciated.
Thank you,
Laurent
matrices reference-request permutations orthogonal-matrices block-matrices
asked Jan 30 at 9:55
Laurent JacquesLaurent Jacques
12
$endgroup$
$begingroup$
Note that, forgetting the conditions on the entries of $R$, an answer to the question above should work also for any orthonormal matrices $P_1, cdots, P_n$, not only permutations, since in my example, the only property requested on the $P_i$'s is their orthonormality.
$endgroup$
– Laurent Jacques
Jan 31 at 9:34
$begingroup$
The structure of $P$ at n=4 above seems connected with the matrix multiplication table of the quaternion, and to Baumert-Hall matrix decomposition, as explained in "Decomposition of Hadamard matrices", by Morris Plotkin. So potentially, there are 48 other equivalent representations of the matrix $P$ above.
$endgroup$
– Laurent Jacques
Feb 1 at 8:06
$begingroup$
I had another try to find some references for the construction above and was more luck this time. It seems that the matrix P above is connected to "Hadamard Array Based Unitary Matrices", with scalar entries replaced by permutation matrices, see e.g., link.springer.com/content/pdf/10.1023/A:1008468827787.pdf (or busim.ee.boun.edu.tr/~sankur/SankurFolder/PBOT.ps if you want to skip the paywall)
$endgroup$
– Laurent Jacques
Feb 25 at 10:14
add a comment |
$begingroup$
Let ${P_1, cdots, P_n}$ be $n$ permutation matrices with size $n times n$.
I'd like to build a $n^2 times n^2$ matrix $P$ such that $P^top P=P P^top$ is a multiple of the identity, and structured as follows:
$$
P = begin{pmatrix}P_1,|&cdots&|,P_n\hline\ &R&\&&end{pmatrix},
$$
where the sign matrix $R in {pm 1}^{(n^2 - n)times n^2}$ completes the first $n$ rows of $P$.
My questions are:
- Is it easy to build $R$? What are common possibilities?
- Can $R$ be also made by $n times n$ blocks, each one being a permutation matrix multiplied by a $pm 1$?
- Can we relate these blocks to the $P_i$'s of the first block-row?
(Update) Here is a solution I found for $n = 4$, that could help to understand my question.
If ${P_1, cdots, P_4}$ are some permutation matrices of size $2 times 2$ (or of any square size bigger, actually), then the following matrix is unitary:
$$
P = begin{pmatrix}
P_1& P_2& P_3& P_4\
P_2&-P_1&-P_4& P_3\
P_4&-P_3& P_2&-P_1\
-P_3&-P_4&P_1&P_2
end{pmatrix}
$$
Above, the second row is achieved by locally flipping the blocks of the first row, with some sign change rule; the 3rd row is obtained from the 2nd by flipping pair of blocks (and some sign change rule); and the 4th is obtained from the first by again locally flipping block of the 3rd.
My feeling is that the construction above should generalize to any $n$ that is a power of 2. Is there some "butterfly" like method behind? Or, having a look the signs, would it be possible to obtain $P$ from some matrix product of the ${P_i}$'s and an Hadamard matrix (but how integrate the flipping of blocks inside)? Many thanks.
Any starting point would be very much appreciated.
Thank you,
Laurent
matrices reference-request permutations orthogonal-matrices block-matrices
asked Jan 30 at 9:55
Laurent JacquesLaurent Jacques
12
$endgroup$
Let ${P_1, cdots, P_n}$ be $n$ permutation matrices with size $n times n$.
I'd like to build a $n^2 times n^2$ matrix $P$ such that $P^top P=P P^top$ is a multiple of the identity, and structured as follows:
$$
P = begin{pmatrix}P_1,|&cdots&|,P_n\hline\ &R&\&&end{pmatrix},
$$
where the sign matrix $R in {pm 1}^{(n^2 - n)times n^2}$ completes the first $n$ rows of $P$.
My questions are:
- Is it easy to build $R$? What are common possibilities?
- Can $R$ be also made by $n times n$ blocks, each one being a permutation matrix multiplied by a $pm 1$?
- Can we relate these blocks to the $P_i$'s of the first block-row?
(Update) Here is a solution I found for $n = 4$, that could help to understand my question.
If ${P_1, cdots, P_4}$ are some permutation matrices of size $2 times 2$ (or of any square size bigger, actually), then the following matrix is unitary:
$$
P = begin{pmatrix}
P_1& P_2& P_3& P_4\
P_2&-P_1&-P_4& P_3\
P_4&-P_3& P_2&-P_1\
-P_3&-P_4&P_1&P_2
end{pmatrix}
$$
Above, the second row is achieved by locally flipping the blocks of the first row, with some sign change rule; the 3rd row is obtained from the 2nd by flipping pair of blocks (and some sign change rule); and the 4th is obtained from the first by again locally flipping block of the 3rd.
My feeling is that the construction above should generalize to any $n$ that is a power of 2. Is there some "butterfly" like method behind? Or, having a look the signs, would it be possible to obtain $P$ from some matrix product of the ${P_i}$'s and an Hadamard matrix (but how integrate the flipping of blocks inside)? Many thanks.
Any starting point would be very much appreciated.
Thank you,
Laurent
matrices reference-request permutations orthogonal-matrices block-matrices
matrices reference-request permutations orthogonal-matrices block-matrices
asked Jan 30 at 9:55
Laurent JacquesLaurent Jacques
12
asked Jan 30 at 9:55
Laurent JacquesLaurent Jacques
12
edited Feb 6 at 17:25
Laurent Jacques
asked Jan 30 at 9:55
Laurent JacquesLaurent Jacques
12
asked Jan 30 at 9:55
Laurent JacquesLaurent Jacques
12
asked Jan 30 at 9:55
Laurent JacquesLaurent Jacques
12
12
$begingroup$
Note that, forgetting the conditions on the entries of $R$, an answer to the question above should work also for any orthonormal matrices $P_1, cdots, P_n$, not only permutations, since in my example, the only property requested on the $P_i$'s is their orthonormality.
$endgroup$
– Laurent Jacques
Jan 31 at 9:34
$begingroup$
The structure of $P$ at n=4 above seems connected with the matrix multiplication table of the quaternion, and to Baumert-Hall matrix decomposition, as explained in "Decomposition of Hadamard matrices", by Morris Plotkin. So potentially, there are 48 other equivalent representations of the matrix $P$ above.
$endgroup$
– Laurent Jacques
Feb 1 at 8:06
$begingroup$
I had another try to find some references for the construction above and was more luck this time. It seems that the matrix P above is connected to "Hadamard Array Based Unitary Matrices", with scalar entries replaced by permutation matrices, see e.g., link.springer.com/content/pdf/10.1023/A:1008468827787.pdf (or busim.ee.boun.edu.tr/~sankur/SankurFolder/PBOT.ps if you want to skip the paywall)
$endgroup$
– Laurent Jacques
Feb 25 at 10:14
add a comment |
$begingroup$
Note that, forgetting the conditions on the entries of $R$, an answer to the question above should work also for any orthonormal matrices $P_1, cdots, P_n$, not only permutations, since in my example, the only property requested on the $P_i$'s is their orthonormality.
$endgroup$
– Laurent Jacques
Jan 31 at 9:34
$begingroup$
The structure of $P$ at n=4 above seems connected with the matrix multiplication table of the quaternion, and to Baumert-Hall matrix decomposition, as explained in "Decomposition of Hadamard matrices", by Morris Plotkin. So potentially, there are 48 other equivalent representations of the matrix $P$ above.
$endgroup$
– Laurent Jacques
Feb 1 at 8:06
$begingroup$
I had another try to find some references for the construction above and was more luck this time. It seems that the matrix P above is connected to "Hadamard Array Based Unitary Matrices", with scalar entries replaced by permutation matrices, see e.g., link.springer.com/content/pdf/10.1023/A:1008468827787.pdf (or busim.ee.boun.edu.tr/~sankur/SankurFolder/PBOT.ps if you want to skip the paywall)
$endgroup$
– Laurent Jacques
Feb 25 at 10:14
$begingroup$
Note that, forgetting the conditions on the entries of $R$, an answer to the question above should work also for any orthonormal matrices $P_1, cdots, P_n$, not only permutations, since in my example, the only property requested on the $P_i$'s is their orthonormality.
$endgroup$
– Laurent Jacques
Jan 31 at 9:34
$begingroup$
Note that, forgetting the conditions on the entries of $R$, an answer to the question above should work also for any orthonormal matrices $P_1, cdots, P_n$, not only permutations, since in my example, the only property requested on the $P_i$'s is their orthonormality.
$endgroup$
– Laurent Jacques
Jan 31 at 9:34
$begingroup$
The structure of $P$ at n=4 above seems connected with the matrix multiplication table of the quaternion, and to Baumert-Hall matrix decomposition, as explained in "Decomposition of Hadamard matrices", by Morris Plotkin. So potentially, there are 48 other equivalent representations of the matrix $P$ above.
$endgroup$
– Laurent Jacques
Feb 1 at 8:06
$begingroup$
The structure of $P$ at n=4 above seems connected with the matrix multiplication table of the quaternion, and to Baumert-Hall matrix decomposition, as explained in "Decomposition of Hadamard matrices", by Morris Plotkin. So potentially, there are 48 other equivalent representations of the matrix $P$ above.
$endgroup$
– Laurent Jacques
Feb 1 at 8:06
$begingroup$
I had another try to find some references for the construction above and was more luck this time. It seems that the matrix P above is connected to "Hadamard Array Based Unitary Matrices", with scalar entries replaced by permutation matrices, see e.g., link.springer.com/content/pdf/10.1023/A:1008468827787.pdf (or busim.ee.boun.edu.tr/~sankur/SankurFolder/PBOT.ps if you want to skip the paywall)
$endgroup$
– Laurent Jacques
Feb 25 at 10:14
$begingroup$
I had another try to find some references for the construction above and was more luck this time. It seems that the matrix P above is connected to "Hadamard Array Based Unitary Matrices", with scalar entries replaced by permutation matrices, see e.g., link.springer.com/content/pdf/10.1023/A:1008468827787.pdf (or busim.ee.boun.edu.tr/~sankur/SankurFolder/PBOT.ps if you want to skip the paywall)
$endgroup$
– Laurent Jacques
Feb 25 at 10:14
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3093319%2forthogonal-block-matrix-made-of-signed-permutation-matrices%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3093319%2forthogonal-block-matrix-made-of-signed-permutation-matrices%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Note that, forgetting the conditions on the entries of $R$, an answer to the question above should work also for any orthonormal matrices $P_1, cdots, P_n$, not only permutations, since in my example, the only property requested on the $P_i$'s is their orthonormality.
$endgroup$
– Laurent Jacques
Jan 31 at 9:34
$begingroup$
The structure of $P$ at n=4 above seems connected with the matrix multiplication table of the quaternion, and to Baumert-Hall matrix decomposition, as explained in "Decomposition of Hadamard matrices", by Morris Plotkin. So potentially, there are 48 other equivalent representations of the matrix $P$ above.
$endgroup$
– Laurent Jacques
Feb 1 at 8:06
$begingroup$
I had another try to find some references for the construction above and was more luck this time. It seems that the matrix P above is connected to "Hadamard Array Based Unitary Matrices", with scalar entries replaced by permutation matrices, see e.g., link.springer.com/content/pdf/10.1023/A:1008468827787.pdf (or busim.ee.boun.edu.tr/~sankur/SankurFolder/PBOT.ps if you want to skip the paywall)
$endgroup$
– Laurent Jacques
Feb 25 at 10:14