Fdtxjr

What would you call a finite collection of unordered objects that are not necessarily distinct?

Can I create an upright 7-foot × 5-foot wall with the Minor Illusion spell?

Can I use my Chinese passport to enter China after I acquired another citizenship?

In Star Trek IV, why did the Bounty go back to a time when whales were already rare?

Pronouncing Homer as in modern Greek

word describing multiple paths to the same abstract outcome

Simple recursive Sudoku solver

Have I saved too much for retirement so far?

Stereotypical names

Latex for-and in equation

When is separating the total wavefunction into a space part and a spin part possible?

Invariance of results when scaling explanatory variables in logistic regression, is there a proof?

Giant Toughroad SLR 2 for 200 miles in two days, will it make it?

What should I use for Mishna study?

A known event to a history junkie

Could solar power be utilized and substitute coal in the 19th century?

What was required to accept "troll"?

What does the "3am" section means in manpages?

Resetting two CD4017 counters simultaneously, only one resets

node command while defining a coordinate in TikZ

Is there an wasy way to program in Tikz something like the one in the image?

The One-Electron Universe postulate is true - what simple change can I make to change the whole universe?

Is there any significance to the Valyrian Stone vault door of Qarth?

Can I Retrieve Email Addresses from BCC?

Equivalence of codes defines a symmetric relation

Binary codes behaving differently from other codes?Knuth equivalence of unshufflesCycles “converging” to an infinite cycle?Permutation that gives a sequence of non-negative partial sumsBlocks in permutation group theory (D&F)Factorizations in the symmetric groupHow do I form a group of permutations and determine the multiplication table for the group?Generator polynomial of the sum of cyclic codesNumber of deranged indicesAn algorithm on $S_n$. What is the final permutation?

2

$begingroup$

Two codes $C_1, C_2 subseteq A^n$ are called equivalent (notation: $sim$) if there are permutations $pi in Sym(A)$ and $sigma_1, dots, sigma_n in S_n$ such that

$$C_2 = (sigma_1(a_pi(1)), dots, sigma_n(a_pi(n))) mid (a_1, dots, a_n ) in C_1$$

Intuitively, this means that we can permute the order of the symbols in our code words, and subsequently permute the alphabet $A$ on every single position on everyy word.

The text I'm reading mentions without proof that $sim$ defines an equivalence relation, but I do not succeed in proving this.

In particular, I'm stuck at showing that

$$C_1 sim C_2 implies C_2 sim C_1$$

I tried with a little example:

if we have the code $C_1 := 00000,01101,10110,11011 subseteq 0,1^5$ and we perform $pi = (12)(345)$ and $sigma_3 = sigma_4 = 1$, $sigma_1 = sigma_2 = sigma_5 neq 1$, then we get the code $C_2 = 11001,01111,10010,00100$

To get back to $C_1$, we have to apply $pi' = (21543)$ and $sigma_2' = sigma_3' = 1$ and $sigma_1' = sigma_4' = sigma_5' neq 1$. I don't see a relation between the permutations $pi, sigma_i$ and $pi', sigma_j$ that can help me.

How can I show that this relation is symmetric?

permutations equivalence-relations coding-theory

share|cite|improve this question

edited Mar 16 at 20:07

Math_QED

asked Mar 16 at 19:58

Math_QEDMath_QED

7,71131454

$endgroup$

add a comment | 

2

$begingroup$

Two codes $C_1, C_2 subseteq A^n$ are called equivalent (notation: $sim$) if there are permutations $pi in Sym(A)$ and $sigma_1, dots, sigma_n in S_n$ such that

$$C_2 = (sigma_1(a_pi(1)), dots, sigma_n(a_pi(n))) mid (a_1, dots, a_n ) in C_1$$

Intuitively, this means that we can permute the order of the symbols in our code words, and subsequently permute the alphabet $A$ on every single position on everyy word.

The text I'm reading mentions without proof that $sim$ defines an equivalence relation, but I do not succeed in proving this.

In particular, I'm stuck at showing that

$$C_1 sim C_2 implies C_2 sim C_1$$

I tried with a little example:

if we have the code $C_1 := 00000,01101,10110,11011 subseteq 0,1^5$ and we perform $pi = (12)(345)$ and $sigma_3 = sigma_4 = 1$, $sigma_1 = sigma_2 = sigma_5 neq 1$, then we get the code $C_2 = 11001,01111,10010,00100$

To get back to $C_1$, we have to apply $pi' = (21543)$ and $sigma_2' = sigma_3' = 1$ and $sigma_1' = sigma_4' = sigma_5' neq 1$. I don't see a relation between the permutations $pi, sigma_i$ and $pi', sigma_j$ that can help me.

How can I show that this relation is symmetric?

permutations equivalence-relations coding-theory

share|cite|improve this question

edited Mar 16 at 20:07

Math_QED

asked Mar 16 at 19:58

Math_QEDMath_QED

7,71131454

$endgroup$

add a comment | 

$begingroup$

Two codes $C_1, C_2 subseteq A^n$ are called equivalent (notation: $sim$) if there are permutations $pi in Sym(A)$ and $sigma_1, dots, sigma_n in S_n$ such that

$$C_2 = (sigma_1(a_pi(1)), dots, sigma_n(a_pi(n))) mid (a_1, dots, a_n ) in C_1$$

Intuitively, this means that we can permute the order of the symbols in our code words, and subsequently permute the alphabet $A$ on every single position on everyy word.

The text I'm reading mentions without proof that $sim$ defines an equivalence relation, but I do not succeed in proving this.

In particular, I'm stuck at showing that

$$C_1 sim C_2 implies C_2 sim C_1$$

I tried with a little example:

if we have the code $C_1 := 00000,01101,10110,11011 subseteq 0,1^5$ and we perform $pi = (12)(345)$ and $sigma_3 = sigma_4 = 1$, $sigma_1 = sigma_2 = sigma_5 neq 1$, then we get the code $C_2 = 11001,01111,10010,00100$

To get back to $C_1$, we have to apply $pi' = (21543)$ and $sigma_2' = sigma_3' = 1$ and $sigma_1' = sigma_4' = sigma_5' neq 1$. I don't see a relation between the permutations $pi, sigma_i$ and $pi', sigma_j$ that can help me.

How can I show that this relation is symmetric?

permutations equivalence-relations coding-theory

share|cite|improve this question

edited Mar 16 at 20:07

Math_QED

asked Mar 16 at 19:58

Math_QEDMath_QED

7,71131454

$endgroup$

share|cite|improve this question

edited Mar 16 at 20:07

Math_QED

asked Mar 16 at 19:58

Math_QEDMath_QED

7,71131454

share|cite|improve this question

edited Mar 16 at 20:07

Math_QED

asked Mar 16 at 19:58

Math_QEDMath_QED

7,71131454

asked Mar 16 at 19:58

Math_QEDMath_QED

7,71131454

asked Mar 16 at 19:58

Math_QEDMath_QED

7,71131454

1 Answer
1

active

oldest

votes

0

$begingroup$

Answering my own question:

It is easy to check that (show that the right side is contained in the left side and then use that both sides have equal finite order)

$$C_1 = (sigma^-1_pi^-1(1)(a_pi^-1(1))), dots, (sigma^-1_pi^-1(a_pi^-1(n)))mid (a_1, dots, a_n) in C_2$$

and the symmetry follows.

share|cite|improve this answer

answered 9 hours ago

Math_QEDMath_QED

7,71131454

$endgroup$

add a comment | 

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
);



);

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3150779%2fequivalence-of-codes-defines-a-symmetric-relation%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

0

$begingroup$

Answering my own question:

It is easy to check that (show that the right side is contained in the left side and then use that both sides have equal finite order)

$$C_1 = (sigma^-1_pi^-1(1)(a_pi^-1(1))), dots, (sigma^-1_pi^-1(a_pi^-1(n)))mid (a_1, dots, a_n) in C_2$$

and the symmetry follows.

share|cite|improve this answer

answered 9 hours ago

Math_QEDMath_QED

7,71131454

$endgroup$

add a comment | 

0

$begingroup$

Answering my own question:

It is easy to check that (show that the right side is contained in the left side and then use that both sides have equal finite order)

$$C_1 = (sigma^-1_pi^-1(1)(a_pi^-1(1))), dots, (sigma^-1_pi^-1(a_pi^-1(n)))mid (a_1, dots, a_n) in C_2$$

and the symmetry follows.

share|cite|improve this answer

answered 9 hours ago

Math_QEDMath_QED

7,71131454

$endgroup$

add a comment | 

$begingroup$

Answering my own question:

It is easy to check that (show that the right side is contained in the left side and then use that both sides have equal finite order)

$$C_1 = (sigma^-1_pi^-1(1)(a_pi^-1(1))), dots, (sigma^-1_pi^-1(a_pi^-1(n)))mid (a_1, dots, a_n) in C_2$$

and the symmetry follows.

share|cite|improve this answer

answered 9 hours ago

Math_QEDMath_QED

7,71131454

$endgroup$

share|cite|improve this answer

answered 9 hours ago

Math_QEDMath_QED

7,71131454

answered 9 hours ago

Math_QEDMath_QED

7,71131454

answered 9 hours ago

Math_QEDMath_QED

7,71131454