Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

Site Tag Cloud

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).

nLab > Latest Changes: Cayley distance

Bottom of Page

1 to 8 of 8

- CommentRowNumber1.
- CommentAuthorUrs
- CommentTimeApr 17th 2021
- PermaLink
Author: Urs
Format: MarkdownItexfor completeness, to go alongside *[[Kendall distance]]* <a href="https://ncatlab.org/nlab/revision/Cayley+distance/1">v1</a>, <a href="https://ncatlab.org/nlab/show/Cayley+distance">current</a>

for completeness, to go alongside Kendall distance

v1, current
- CommentRowNumber2.
- CommentAuthorUrs
- CommentTimeApr 18th 2021
- PermaLink
Author: Urs
Format: MarkdownItexadded statement and proof of Cayley's formula $$ d_C(\sigma_1, \sigma_2) \;=\; n - \left\vert Cycles\big( \sigma_1 \circ \sigma_2^{-1} \big) \right\vert $$ <a href="https://ncatlab.org/nlab/revision/diff/Cayley+distance/2">diff</a>, <a href="https://ncatlab.org/nlab/revision/Cayley+distance/2">v2</a>, <a href="https://ncatlab.org/nlab/show/Cayley+distance">current</a>

added statement and proof of Cayley’s formula
$<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msub><mi>d</mi> <mi>C</mi></msub><mo stretchy="false">(</mo><msub><mi>σ</mi> <mn>1</mn></msub><mo>,</mo><msub><mi>σ</mi> <mn>2</mn></msub><mo stretchy="false">)</mo><mspace width="0.27778em"/><mo>=</mo><mspace width="0.27778em"/><mi>n</mi><mo>−</mo><mrow><mo>|</mo><mi>Cycles</mi><mo maxsize="1.2em" minsize="1.2em">(</mo><msub><mi>σ</mi> <mn>1</mn></msub><mo>∘</mo><msubsup><mi>σ</mi> <mn>2</mn> <mrow><mo lspace="0.11111em" rspace="0em">−</mo><mn>1</mn></mrow></msubsup><mo maxsize="1.2em" minsize="1.2em">)</mo><mo>|</mo></mrow></mrow><annotation encoding="application/x-tex"> d_C(\sigma_1, \sigma_2) \;=\; n - \left\vert Cycles\big( \sigma_1 \circ \sigma_2^{-1} \big) \right\vert </annotation></semantics></math>$
diff, v2, current
- CommentRowNumber3.
- CommentAuthorUrs
- CommentTimeApr 18th 2021
- PermaLink
Author: Urs
Format: MarkdownItexadded pointer to: * [[M. A. Fligner]], [[J. S. Verducci]], Section 4 of: *Distance Based Ranking Models*, Journal of the Royal Statistical Society. Series B (Methodological) Vol. 48, No. 3 (1986), pp. 359-369 ([jstor:2345433](https://www.jstor.org/stable/2345433)) (one of the few references that I found so far which do at least consider the "Cayley distance kernel" $\exp(-d_C(-,-,))$ ) <a href="https://ncatlab.org/nlab/revision/diff/Cayley+distance/2">diff</a>, <a href="https://ncatlab.org/nlab/revision/Cayley+distance/2">v2</a>, <a href="https://ncatlab.org/nlab/show/Cayley+distance">current</a>
added pointer to:
- M. A. Fligner, J. S. Verducci, Section 4 of: Distance Based Ranking Models, Journal of the Royal Statistical Society. Series B (Methodological) Vol. 48, No. 3 (1986), pp. 359-369 (jstor:2345433)
(one of the few references that I found so far which do at least consider the “Cayley distance kernel” $<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>exp</mi><mo stretchy="false">(</mo><mo lspace="0.11111em" rspace="0em">−</mo><msub><mi>d</mi> <mi>C</mi></msub><mo stretchy="false">(</mo><mo lspace="0.11111em" rspace="0em">−</mo><mo>,</mo><mo lspace="0.11111em" rspace="0em">−</mo><mo>,</mo><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\exp(-d_C(-,-,))</annotation></semantics></math>$ )

diff, v2, current
- CommentRowNumber4.
- CommentAuthorUrs
- CommentTimeApr 18th 2021
- PermaLink
Author: Urs
Format: MarkdownItexalso added pointer to * [[Michael A. Fligner]], [[Joseph S. Verducci]] (eds.), *Probability Models and Statistical Analyses for Ranking Data* ([doi:10.1007/978-1-4612-2738-0](https://link.springer.com/book/10.1007/978-1-4612-2738-0)) which mentions the Cayley-distance kernel at least in the forword as the "only reasonable bi-invariant distance". <a href="https://ncatlab.org/nlab/revision/diff/Cayley+distance/3">diff</a>, <a href="https://ncatlab.org/nlab/revision/Cayley+distance/3">v3</a>, <a href="https://ncatlab.org/nlab/show/Cayley+distance">current</a>
also added pointer to
- Michael A. Fligner, Joseph S. Verducci (eds.), Probability Models and Statistical Analyses for Ranking Data (doi:10.1007/978-1-4612-2738-0)
which mentions the Cayley-distance kernel at least in the forword as the “only reasonable bi-invariant distance”.

diff, v3, current
- CommentRowNumber5.
- CommentAuthorUrs
- CommentTimeApr 19th 2021
- (edited Apr 19th 2021)
- PermaLink
Author: Urs
Format: MarkdownItexadded pointer to: * [[Persi Diaconis]], [[Phil Hanlon]], Section 4 of: *Eigen Analysis for Some Examples of the Metropolis Algorithm*, in Donald Richards (ed.) *Hypergeometric Functions on Domains of Positivity, Jack Polynomials, and Applications*, Contemporary Mathematics Vol. 138, AMS 1992 ([doi:10.1090/conm/138](http://dx.doi.org/10.1090/conm/138), [EFS NSF 392](https://statistics.stanford.edu/research/eigen-analysis-some-examples-metropolis-algorithm), [pdf](https://statweb.stanford.edu/~cgates/PERSI/papers/eigen-metalg.pdf)) <a href="https://ncatlab.org/nlab/revision/diff/Cayley+distance/4">diff</a>, <a href="https://ncatlab.org/nlab/revision/Cayley+distance/4">v4</a>, <a href="https://ncatlab.org/nlab/show/Cayley+distance">current</a>
added pointer to:
- Persi Diaconis, Phil Hanlon, Section 4 of: Eigen Analysis for Some Examples of the Metropolis Algorithm, in Donald Richards (ed.) Hypergeometric Functions on Domains of Positivity, Jack Polynomials, and Applications, Contemporary Mathematics Vol. 138, AMS 1992 (doi:10.1090/conm/138, EFS NSF 392, pdf)
diff, v4, current
- CommentRowNumber6.
- CommentAuthorUrs
- CommentTimeApr 19th 2021
- PermaLink
Author: Urs
Format: MarkdownItexadded pointer to: * Thaynara Arielly de Lima; Mauricio Ayala-Rincón, *Complexity of Cayley distance and other general metrics on permutation groups* ([doi:10.1109/ColombianCC.2012.6398020](https://doi.org/10.1109/ColombianCC.2012.6398020), [pdf](https://www.mat.unb.br/ayala/shortw4v2.pdf)) <a href="https://ncatlab.org/nlab/revision/diff/Cayley+distance/4">diff</a>, <a href="https://ncatlab.org/nlab/revision/Cayley+distance/4">v4</a>, <a href="https://ncatlab.org/nlab/show/Cayley+distance">current</a>
added pointer to:
- Thaynara Arielly de Lima; Mauricio Ayala-Rincón, Complexity of Cayley distance and other general metrics on permutation groups (doi:10.1109/ColombianCC.2012.6398020, pdf)
diff, v4, current
- CommentRowNumber7.
- CommentAuthorUrs
- CommentTimeApr 20th 2021
- PermaLink
Author: Urs
Format: MarkdownItexadded the example ([here](https://ncatlab.org/nlab/show/Cayley+distance#CayleyDistanceOnSym3)) of the Cayley distance function on $Sym(3)$ <a href="https://ncatlab.org/nlab/revision/diff/Cayley+distance/6">diff</a>, <a href="https://ncatlab.org/nlab/revision/Cayley+distance/6">v6</a>, <a href="https://ncatlab.org/nlab/show/Cayley+distance">current</a>

added the example (here) of the Cayley distance function on $<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>Sym</mi><mo stretchy="false">(</mo><mn>3</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">Sym(3)</annotation></semantics></math>$

diff, v6, current
- CommentRowNumber8.
- CommentAuthorUrs
- CommentTimeApr 24th 2021
- PermaLink
Author: Urs
Format: MarkdownItexI have made explicit ([here](https://ncatlab.org/nlab/show/Cayley+distance#CayleyDistancePreservedByInclusionOfSymmetricGroups)) the following immediate and elementary but important fact: Cayley distance is preserved under the canonical inclusions of [[symmetric groups]] $$ Sym(n) \overset{ i }{ \hookrightarrow } Sym(n+1) \hookrightarrow Sym(n+2) \hookrightarrow \cdots $$ in that $$ d_C( \sigma_1, \sigma_2 ) \; = \; d_C\big( i(\sigma_1), i(\sigma_2) \big) \,. $$ In other words, when regarding the [[metric space]] given by the set of permutations in $Sym(n)$ with their Cayley distance function between them * as an $(\mathbb{R}_{\geq 0}, \geq)$0-[[enriched category]], then the [[functors]] induced by the inclusions are [[fully faithful functor|fully faithful]] and hence are [[full subcategory]] inclusions. * as a [[matrix]], then the inclusions correspond to [[principal submatrices]]. <a href="https://ncatlab.org/nlab/revision/diff/Cayley+distance/14">diff</a>, <a href="https://ncatlab.org/nlab/revision/Cayley+distance/14">v14</a>, <a href="https://ncatlab.org/nlab/show/Cayley+distance">current</a>
I have made explicit (here) the following immediate and elementary but important fact:

Cayley distance is preserved under the canonical inclusions of symmetric groups
Sym(n)i↪Sym(n+1)↪Sym(n+2)↪⋯

in that
dC(σ1,σ2)=dC(i(σ1),i(σ2)).

In other words, when regarding the metric space given by the set of permutations in $<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>Sym</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">Sym(n)</annotation></semantics></math>$ with their Cayley distance function between them
- as an $<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo stretchy="false">(</mo><msub><mi>ℝ</mi> <mrow><mo>≥</mo><mn>0</mn></mrow></msub><mo>,</mo><mo>≥</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(\mathbb{R}_{\geq 0}, \geq)</annotation></semantics></math>$ 0-enriched category, then the functors induced by the inclusions are fully faithful and hence are full subcategory inclusions.
- as a matrix, then the inclusions correspond to principal submatrices.
diff, v14, current

1 to 8 of 8

nForum

Discussion Feed

Not signed in

Site Tag Cloud

nLab > Latest Changes: Cayley distance