Thursday, April 8, 2021

Recent Questions - Mathematics Stack Exchange

Recent Questions - Mathematics Stack Exchange

How to change the description of a plane from parametrization to equation.

Posted: 08 Apr 2021 07:46 PM PDT

I have a doubt regarding ways to describe planes. I know this can be done, via equation and parametrizations. If I have the form of an equation say;

x+3y+z=3, I can turn this into a parametrization making x = 3-3y-z such that the parametrized form is

(3,0,0) + (-3,1,0)y + (-1,0,1)z

My issue is, I don't know how to turn a parametrization back to an equation. Is there any information on the topic, procedure. What is the terminology, I don't know how to properly look for this.

For example: if I give (1,2,1) + (-3,1,3)y + (0,1,2)z , How can I turn this back to a plane expression with only one equation?

Generalized eigenvalue problem with non-invertible matrices

Posted: 08 Apr 2021 07:45 PM PDT

Consider a generalized Eigenvalue problem A v = λ B v where A and B are noninvetible square matrices of the same dimension. It is easy to solve when B is invertible, but how to solve the generalized eigenvalue problem when B is non-invertible?

Proving inequality (induction?)

Posted: 08 Apr 2021 07:45 PM PDT

Let $a>0$, $n,p \in \mathbb{N}$, $p<n$

$\sqrt[\leftroot{-1}\uproot{2}n]{a^p} \leq 1+\frac{p}{n} (a-1)$

I tried to do it by induction, with the first step for $a=2, n=2, p=1$. $\sqrt{2^1} \leq 1+ \frac{1}{2}(2-1)$. However I do not know how to go on with the induction. Would appreciate help

Proof Verification: Sum of suprema

Posted: 08 Apr 2021 07:43 PM PDT

For $\nu=1, 2, ..., n$, let $X_\nu$ be set of real numbers. If there is a number $\xi$ such that $$ \sum_{\nu=1}^n x_\nu \leq \xi, $$ for any $x_\nu\in X_\nu$, then $$ \sum_{\nu=1}^n \sup X_\nu \leq \xi. $$

Proof. We proceed by induction on $n$. The statement evidently holds for $n=1$. Suppose that the statement holds for $n-1\geq0$. Fix an $x_n\in X_n$, we then have $$ \sum_{\nu=1}^{n-1} x_\nu \leq \xi-x_n $$ for any $x_\nu\in X_\nu$, $\nu=1, 2, ..., n-1$; hence $$ \sum_{\nu=1}^{n-1} \sup X_\nu \leq \xi-x_n,$$ or $$ x_n\leq \xi - \sum^{n-1}_{\nu=1}\sup X_\nu. $$ Since $x_n$ is arbitrary, $$ \sup X_n \leq \xi - \sum_{\nu=1}^{n-1} \sup X_\nu, $$ as was to be proved.

Let $\{x_n\}$, $\{y_n\}$, and $\{z_n\}$ be sequences of real numbers. Then $$ \limsup\limits_{n\rightarrow\infty} x_n+y_n+z_n\leq \limsup\limits_{n\rightarrow\infty}x_n+\limsup\limits_{n\rightarrow\infty}y_n+\limsup\limits_{n\rightarrow\infty}z_n. $$

Known properties of limit superior:

  1. If $x>\limsup\limits_{n\rightarrow\infty}x_n$, then $x>x_n$ for all sufficiently large $n$.
  2. If $x<\limsup\limits_{n\rightarrow\infty}x_n$, then $x<x_n$ for infinitely many $n$.
  3. If $x_n < y_n$ for all sufficiently large $n$, then $\limsup\limits_{n\rightarrow\infty}x_n\leq\limsup\limits_{n\rightarrow\infty}y_n$.

Proof. Observe that $\limsup [ x_n + c ] = \limsup x_n + c $ for any contant $c$. Let $\epsilon>0$. Then $$ x_k < \limsup x_n + \epsilon $$ and hence $$ x_k + y_k < y_k + \limsup x_n + \epsilon $$ for all sufficiently large $k$. Letting $k$ increase without limit, we obtain $$ \limsup [ x_n + y_n ] \leq \limsup x_n + \limsup y_n + \epsilon; $$ now let $\epsilon\rightarrow0$ so that $$ \limsup [ x_n + y_n ] \leq \limsup x_n + \limsup y_n. $$ Therefore $$ \limsup [x_n+y_n+z_n] \leq \limsup [x_n+y_n] + \limsup z_n \leq \limsup x_n + \limsup y_n + \limsup z_n.$$

A technicality in the Radon-Nikodym theorem

Posted: 08 Apr 2021 07:42 PM PDT

The Radon-Nikodym Theorem says:

If a measureable space $(S,\,\Sigma)$ admits $\sigma$-finite measures $\mu$ and $\nu \ll \mu $, there is a unique (up to sets of $\mu$-measure zero) $\Sigma$-measurable function $ f:S\rightarrow \left[\right.0,\,\infty \left.\right)$, such that, for any measurable set $ A\in \Sigma$, $$ \nu (A)\,=\,\int_{A}\,f\,d\mu\,\;. $$ Named the Radon-Nikodym derivative of $\nu$ with respect to $\mu$, the function $f$ is commonly written as $d\nu/d\mu$.

Question.

A function $\,S\longrightarrow\mathbb{R}\,$ is called Lebesgue-measurable iff the preimage of any open set from $\mathbb R$ is measurable in $(S,\,\Sigma)$.

Would it be right to say that the Radon-Nikodym derivative $f$ is Lebesgue-measurable?

A box contains tags marked 1, 2, . . . , n.

Posted: 08 Apr 2021 07:41 PM PDT

A box contains tags marked 1, 2, . . . , n. Two tags are chosen at random. Find the probability that the numbers on the tags will be consecutive integers if (a) the tags are chosen without replacement (b) the tags are chosen with replacement.

Can the functions in Gödel's Incompleteness proof be expressed as Gödel numbers?

Posted: 08 Apr 2021 07:40 PM PDT

I'm trying to understand the entirety of Gödel's incompleteness theorem, and Gödel's proof.

Going by this English translation Gödel defines 45 functions (relations) which build on each other to make the function of provability, there called $Bew(x)$, which returns a true if $x$ is a provable statement, and false if $x$ is an unprovable statement.

The symbols assigned Gödel numbers are $0, f, ¬, ∨, ∀, (, )$

Can each of the 45 functions actually be encoded as Gödel numbers?

Or are the functions merely manipulation and inspection that we do from the outside to create new Gödel numbers and statements?

My confusion is that many of the symbols in the functions $(\leq, \epsilon, \exists, \cdot, etc)$ are not simple logical statements. Much is made of the primitive recursion of these statements, but nothing is said about how to actually "write them out"

Can someone help me with this question

Posted: 08 Apr 2021 07:38 PM PDT

Can someone help find an example of a subset of R that has exactly n limit points, for n belongs to N

Solving a Nonlinear System derived from orthogonality of Direction Cosine Matrix

Posted: 08 Apr 2021 07:36 PM PDT

Say I have a Direction Cosine Matrix $[a]$ given by: $$ [a]= a_{ij}=cos(x_{i},x_{j}^{'})=cos(\vec{x},\vec{x}')= \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} $$ In other words, the entries $a_{ij}$ are the cosines of the angles between the axes of the old coordinate system, $x_i$, and the new coordinate system, $x_{j}^{'}$, after being transformed by $[a]$. In other words:

$$\vec{x}'=x_{j}^{'}=a_{ij}x_{i}=[a]\vec{x}$$

If the axes of $\vec{x}'$ are orthogonal, then I believe $[a]$ is orthogonal. Regardless, assuming that $[a]$ is orthogonal, the entries of $[a]$ are not independent. Since $[a]^{-1}=[a]^{T}$ for an orthogonal matrix and $[a]^{-1}[a]=[a][a]^{-1}=[I]$ for invertible $[a]$, then $[a]^{T}[a]=[a][a]^{T}=[I]$. This leads to 12 distinct equations: $$ a_{11}^2+a_{21}^2+a_{31}^2=1 $$ $$ a_{12}^2+a_{22}^2+a_{32}^2=1 $$ $$ a_{13}^2+a_{23}^2+a_{33}^2=1 $$ $$ a_{11}^2+a_{12}^2+a_{13}^2=1 $$ $$ a_{21}^2+a_{22}^2+a_{23}^2=1 $$ $$ a_{31}^2+a_{32}^2+a_{33}^2=1 $$

$$ a_{11}a_{12}+a_{21}a_{22}+a_{31}a_{32}=0 $$ $$ a_{11}a_{13}+a_{21}a_{23}+a_{31}a_{33}=0 $$ $$ a_{12}a_{13}+a_{22}a_{23}+a_{32}a_{33}=0 $$ $$ a_{11}a_{21}+a_{12}a_{22}+a_{13}a_{23}=0 $$ $$ a_{11}a_{31}+a_{12}a_{32}+a_{13}a_{33}=0 $$ $$ a_{21}a_{31}+a_{22}a_{32}+a_{23}a_{33}=0 $$ Is there a way to take these relations into account in the original matrix $[a]$? I am unsure how to go about this since it is a nonlinear system of equations. Is there a general way to go about such a problem?

Using finitely generated in proof (2).

Posted: 08 Apr 2021 07:33 PM PDT

I was reading the proof of $(c) \implies (a)$ i.e., (Given any submodule $M \subset N,$ there exists a unique submodule $M' \subset N$ such that $N = M \oplus M'$) implies ($N$ is a sum of simple modules) in the answer of the following question:

using finitely generated in proof.

But I did not get the idea of the proof. Could someone explain the idea of the proof to me or give a simpler proof, please?

Here is the proof given there:

Again, how about existence in $c)$ implying $a)$? I'll simply prove that every submodule of $N$ satisfies existence in $c)$ as well. Indeed, let $M_1 \subset M$ be submodules, let $M' \subset N$ be such that $M \oplus M'=N$. Let then $M''$ be such that $M' \oplus (M'+M_1)=N$. Let $\pi:N \rightarrow M$ be the projection with kernel $M'$. It's easy to check that $M = \pi(M'') \oplus M_1$.

Note also that every submodule of $N$ is the image of $N$ under some projection so is finitely generated. In particular, every sequence of submodules $(M_n)_n$ such that $M_n \subset M_{n+1}$ is stationary.

Let $(M_n)$ be a sequence of submodules such that $M_n \supset M_{n+1}$. Let $M_n=N_n \oplus M_{n+1}$. Then $\left(\bigoplus_{p \leq n}{N_p}\right)_n$ is a nondecreasing sequence of submodules of $N$ so is stationary, which implies that for $n$ large enough $N_n=0$, ie $M_n=M_{n+1}$ so $M_n$ is stationary.

From this, it follows that the set of nonzero submodules of $N$ has minimal elements (the simple submodules). Let $S$ be their sum, we can write $N=S \oplus S_1$ for some submodule $S_1$. Assume $S_1$ is nonzero: since every non-increasing/nondecreasing sequence of submodules of $S_1$ is stationary, $S_1$ contains a simple submodule $P$. But $P \subset S$ by definition of $S$, so $P \subset S\cap S_1 = \{0\}$, a contradiction. So $N=S$ is sum of simple modules.

Which law of polynomials does this follow from ? Any insight is appreciated

Posted: 08 Apr 2021 07:42 PM PDT

a(x-6)^4 + b(x-6)^3 + c(x-6)^2 + d(x-6) = 0

Without explicitly expanding the left side of the equation above, we can see that the left side has a ax^4 term. Because the right side has no x^4 term, this implies that a = 0. I'm confused how one can deduce this from that.

Prove that the midline of a trapezoid is equal to the line joining the midpoints of its diagonals plus the base.

Posted: 08 Apr 2021 07:29 PM PDT

Prove that the midline of a trapezoid is equal to the line joining the midpoints of its diagonals plus the base.

I tried forming triangles around the midsegments, and diagonal's midpoints but couldn't seem to come up with a way to show that the line connecting the diagonal's midpoints plus the smaller base equal the midline of the trapezoid.

The question is to be solved using vectors.

show that $Y={(P,L)∈ℙ^2×ℙ^2|P∈L}$ is a closed sub variety

Posted: 08 Apr 2021 07:25 PM PDT

Given this definition: A projective line in $ℙ^2(ℂ)$ is defined by $𝑎𝑥+𝑏𝑦+𝑐𝑧=0$ where $0≠(𝑎,𝑏,𝑐)∈ℂ^3$

I was asked to show that $Y={(P,L)∈ℙ^2×ℙ^2|P∈L}$ is a closed sub variety

I have no idea how to go about doing this, any help would be great

What is the largest number of bit operations that can be completed in one second, where each bit operation takes 10^(-9) seconds to complete?

Posted: 08 Apr 2021 07:53 PM PDT

The complete questions reads as follows:

What is the largest n for which one can solve within one second a problem using an algorithm that requires f(n) bit operations, where each bit operation is carried out in 10^(−9) seconds, with these functions f(n)?

I'm stuck trying to find this value for nlog(n). The answer for this problem is provided, but I'm having trouble replicating it.

Given answer: $3.96×10^7$

I'm struggling to get something better than $ \sqrt[\leftroot{-3}\uproot{3}n]{2^{10^{9}}}$. What can I do differently?

How to do the transformation in log operator?

Posted: 08 Apr 2021 07:30 PM PDT

I just see the equations, and can not understand the math behind this equation.

enter image description here

Any ideas? Thanks.

Find the kernel and range for the transformation

Posted: 08 Apr 2021 07:46 PM PDT

If linear transformation T(V1, V2*V3) =(V1, V2) Then find the column space and null space for the given transformation

Asterisk means product of the two elements

I do not understand how to do the following RING theory-proofing problem

Posted: 08 Apr 2021 07:50 PM PDT

Defined 𝑓: ℤ3 × ℤ3 → ℤ3 with 𝑓 ((𝑎, 𝑏)) = 𝑎 +3 𝑏. Determine if f is a homomorphism of the ring? If yes, prove it. If not, provide an example of a denial. I guess that isn't homomorphism and if that is true then i can't give a counter example.

Using induction to prove a natural number property

Posted: 08 Apr 2021 07:49 PM PDT

Suppose that the natural numbers are defined as:

$\mathrm{P} 1)$ $1 \in \mathbb{N}$
$\mathrm{P} 2) \forall n \in \mathbb{N}, f(n) \neq 1 ;$
$\mathrm{P} 3)$ $f$ is injective
$\mathrm{P} 4)$ A subset $A \subset \mathbb{N}$ satisfies:
a) $1 \in A$
b) $\forall n \in \mathbb{N}, n \in A \text { implies } f(n) \in A$

And now $f$ is defined as $f(1) =2 , f(f(1))=3 , f(f(f(1)))=4, ...$

And I want to prove that For any $n ∈ \mathbb{N}, n \neq 1$, show that there exists a unique $n' ∈ \mathbb{N}$, such that $n = f(n')$.

My attempt:

Let $P(n)$ denote that there exists a unique $n' ∈ \mathbb{N}$, such that $n = f(n')$ for any $n ∈ \mathbb{N}, n \neq 1$

Base case: suppose $n=2$, then there exists a unique $n'=1 ∈ \mathbb{N}$, such that $2 = f(1)$. by $P2)$, $1$ is unique.

Inductive: assume $P(n)$ true, show $P(n+1)$ true:

Denote $n+1$ as applying the successor function $f$, From $n = f(n')$, apply the successor function to both sides, that is: $f(n) = f(f(n'))$ $(*)$, using the induction hypothesis, the right side $f(f(n'))=f(n)$, so by $(*)$,$f(n)=f(n)$, since $f$ is injective, $P(n+1)$ is true.

So by induction, $P(n)$ is true.

Did I do this proof correctly? I feel like for the inductive step, not mentioning uniqueness is wrong. Any help is appreciated.

Show that the argument form with premises (p ∧ t) → (r ∨ s), q → (u ∧ t), u → p, and¬s and conclusion q → r is valid. (Is my solution correct?)

Posted: 08 Apr 2021 07:38 PM PDT

Here is my solution/proof

  1. (p ^ t) -> (r v s) //Premise

  2. q -> (u ^ t) // Premise

  3. u -> p // Premise

  4. ~s // Premise

  5. q -> u // Simplification of (2)

  6. q -> t // Simplification of (2)

  7. q -> p // Hypothetical Syllogism (3) (5)

  8. q -> (p^t) // Conjunction

  9. q -> (r v s) // Hypothetical Syllogism (1) (8)

  10. ~q v ( r v s) // Logical Equivalence, Conditional Statement

  11. ~q v ( s v r) // Commutativity

  12. ~q v r // Disjunctive Syllogism

  13. q -> r // Logical Equivalence

Thanks in advance to anyone who can point out any mistakes or suggestions! <3

How do I prove this biconditional logical equivalence using propositional equivalences? (Is my solution correct?)

Posted: 08 Apr 2021 07:52 PM PDT

How do I prove that $p\longleftrightarrow q \Longleftrightarrow (p\to q)\wedge(q\to p)$?

Is my solution/proof correct?

I have constructed a proof for this question, i'll start with the left hand side, namely p <-> q

  1. p <-> q // Premise
  2. (p^q) v ( ~p^~q) // Logical Equivalence (1)
  3. (~pv~q) ^ ( p v q) // Negation (2)
  4. (~pvq) ^ (p v q) // Double Negation (3)
  5. (p -> q) ^ (pvq) // Logical Equivalence (4)
  6. (p -> q) ^ (q v p) // Commutative (5)
  7. (p -> q) ^ (~q->p) // Logical Equivalence (6)
  8. (p -> q) ^ (q ->p) // Double Negation (7)

Therefore, (p->q) ^ (q -> p) is equal to its RHS (p->q) ^ (q -> p). Is my proof correct? Is there anything I can do to shorten it? Thanks so much.

Number of possible values of $4x-z$ if $x+y+z=20$

Posted: 08 Apr 2021 07:32 PM PDT

Given that $x, y,z$ are non negative integers such that $x+y+z=20$. If $S$ is the set of all possible values of $4x-z$.Find $n(S)$.

My try: By stars and bars number of non negative integer solutions of $x+y+z=20$ is $\binom{22}{2}=210$

Among these $210$ ordered triplets of $(x,y,z)$ we need to find number of possible values taken by $4x-z$.

Obviously the least value taken by $4x-z$ is $-20$ when $x=0,z=20$. The next value taken by $4x-z$ is $-19$ when $x=0,z=19$ and so on.

So once we fix $x=0$ ,since $z$ varies from $[0,20]$ number of values taken by $4x-z$ is $21$.

But when we fix $x=1$, we get some overlaps. For example when $x=1,z=18$ we have $4x-z=-14$ and this value has already been counted in the previous case when $x=0,z=14$.

So any way to count total number of values taken by $4x-z$ excluding overlaps?

Meaning of Divisibility in the definition of a relation

Posted: 08 Apr 2021 07:26 PM PDT

Consider {$ℝ+,≤$}, where "$≤$" defined as "a is divisible by b". Is {$ℝ+,≤$} a Partially Ordered Set (POSET) ?
While checking for antisymmetric property, a≤b : a is divisible by b

The axioms for a non-strict partial order state that the relation ≤ is reflexive, antisymmetric, and transitive. That is, for all a, b, and c in P, it must satisfy:

  1. a ≤ a (reflexivity: every element is related to itself).
  2. if a ≤ b and b ≤ a, then a = b (antisymmetry: two distinct elements cannot be related in both directions).
  3. if a ≤ b and b ≤ c, then a ≤ c (transitivity: if a first element is related to a second element, and, in turn, that element is related to a third element, then the first element is related to the third element).
 Does the above statement mean, we need to get the remainder as zero? My teacher said the definition of "divisibility" here is based on the concept of multiples and NOT on the concept of factors.

Can anyone please clarify this doubt? Please also prove that {$ℝ+,≤$} is NOT a POSET.

A four digit number multiple of $ 5 $ different numbers?

Posted: 08 Apr 2021 07:43 PM PDT

A boy imagined a four-digit multiple of $5$ with different digits. If the first digit is erased, the obtained number is multiple of $9$ . If the second digit of the imagined number is erased, the obtained number is multiple of $11$ . If the third digit of the imagined number is erased, the obtained number is multiple of $7$. What number a boy imagined?

I got number $ 1765 $ which satisfy all conditions is multiple of $5$..

$ \bullet $ If 1st digit erase , $ 765 \div9 = 85 $

$ \bullet $ If 2nd digit is erase , $ 165\div11 = 15 $

$ \bullet $ If 3rd digit removes , $ 175\div 7= 25 $

But i can't find the way to get the solution mathematical way...

Gain function based on Bézier curves

Posted: 08 Apr 2021 07:52 PM PDT

I'm looking for a gain function, for range 0-1, where the output goes from 0-1 but at different pace.

Sure there are plenty of Log, Squares, sigmoids, tanhs but I was looking for something more flexible, and the I thought of the Bézier curves, for example:

where four parameters allow almost any curve.

Especially useful are the ones where the second set of parameters are symmetric, where it covers logit, square logit, symlog, and all the possible intermediary curves.

enter image description here

i.e.

The Béziers for 4 points are: $$P(t) = (1−t)^3P_1 + 3(1−t)^2tP_2 +3(1−t)t^2P_3 + t^3P_4 \\ $$

So to make the gain function, I would need to express Y on base of Y, and as the point 1 in our case is (0,0), and point 4 is (1,1) and P2 and P3 will be our input parameters (as the cubic-bezier.com examples) . So I could write:

  • X = Xa*3(1−t)^2*t + Xb*(1−t)*t^2 + t^3
  • Y = Ya*3(1−t)^2*t + Yb*(1−t)*t^2 + t^3

Clear t in the first, substitute in the second, and we will have:

  • f(x) = y = (¿Xa,Xb,Ya,Yb?)·x

But this goes beyond my capabilities :_((

Can anybody help me?

I want to implement this either on excel, python, or desmos:

PD: sorry, I think I asked in wrong forum, I hope the math.stackexchange.com is the right one, I am not sure if I should delete this one.

Definite integral of arbitrary-base exponent is undefined

Posted: 08 Apr 2021 07:39 PM PDT

The integral of an arbitrary-base exponent can be given as $$\int_0^x a^{x_0} d{x_0} = \frac{a^x - 1}{\ln(a)}$$ by $a^{x_0} = e^{x_0 \ln a}$.

At $a = 1$ when $f(x) = a^x = 1$, the definite integral shown above should clearly be $F(x) = x$, but is instead undefined by $\frac{a^x-1}{\ln(a)}$.

How can the integral be evaluated to accurately represent the behavior of $f(x)$? I have tried rearranging terms and applying various properties of logarithms/exponents but have had no success.

I am more interested in closed form solutions as something like a Taylor approximation is trivial but not particularly useful when $x$ is large.

Circle geometry problem with 11 circles

Posted: 08 Apr 2021 07:45 PM PDT

enter image description here

In the diagram, eleven circles of four different sizes are drawn. Each circle labelled W has radius 1, each circle labelled X has radius 2, the circle labelled Y has radius 4, and the circle labelled Z has radius r. Each of the circles labelled W or X is tangent to three other circles. The circle labelled Y is tangent to all ten of the other circles. The circle labelled Z is tangent to three other circles. Determine positive integers s and t for which r = s/t.

I think cosine law bash might work, just not sure where to start with it.

Find ratio of areas of triangle formed by touch points to triangle formed by centers of three circles

Posted: 08 Apr 2021 07:48 PM PDT

Let $S_1:x^2+y^2+4y-1=0, S_2: x^2+y^2+6x+y+8=0; S_3: x^2+y^2-4x-4y-37=0$ touch each other. Let $P_1,P_2,P_3$ be their contact points and let $C_1,C_2,C_3$ be their centers. Find $\frac{\Delta P_1P_2P_3}{\Delta C_1C_2C_3}$

I can find the points P using radical axes formula, but this process is quite lengthy. Is there any property I can exploit for this question ?

What is the semilinear form for this poisson equation?

Posted: 08 Apr 2021 07:30 PM PDT

I am using finite element software to solve ODEs and PDEs. It requires the semilinear form. E.g When solving the poisson equation $$\nabla\cdot((1+u^2)\nabla u) = -f$$ the semilinear form $$\int_\Omega (1+u^2)\nabla u\cdot\nabla v - fvdx$$ is required.

What I would like to know is the semilinear form for the equation $$\nabla^2 u = -f(u)$$

Convergence of integral $\int_{17}^\infty \frac{(\ln{\ln{x})}\sin{(e^{ax}})}{x+e}$

Posted: 08 Apr 2021 07:37 PM PDT

For which $a\in\mathbb{R}$ does the integral $\int_{17}^\infty \frac{(\ln{\ln{x})}\sin{(e^{ax}})}{x+e}$ converge? I tried with substitution $t=e^{ax}$, but don't know how to do the rest?

Any help is welcome. Thanks in advance

"Distance" between two permutations?

Posted: 08 Apr 2021 07:46 PM PDT

I've been trying to find a 'good' definition of the "distance" between two permutations that matches my intuition. I found this post which gets part of the way to what I'm thinking about, but I don't think it gets there entirely. I'm very open to suggestions on distance metrics, but I came up with one that I'm not very attached to and would like some opinions.

The one I've thought would be helpful for me is based on a particular operation which I'm calling a "move" (I'm sure it has a real name, but I haven't found it while Googling), which I'm defining as a deletion followed by an insertion of the deleted element. For instance, if I have the sequence [4, 1, 2, 3] which I'm comparing to [1,2,3,4], I could delete 4 (at index 0) and insert 4 (at the end) and I would have performed 1 "move". In this way, the distance between [1,2,3,4] and [4,1,2,3] would be defined as 1.

Another example:

dist([1,2,3,4], [4,2,1,3]) = 2, because [4,2,1,3]->[4,1,2,3]->[1,2,3,4]

The reason I like this particular distance metric is because it doesn't penalize sublists which are simply in the wrong part in the sequence (but in the right order as a sublists). The thing I don't love about it is for longer lists, sometimes the answers don't intuitively match what I'm looking for - example:

a) dist([1,2,3,4,5,6,7,8], [5,6,7,8,1,2,3,4]) = 4  b) dist([1,2,3,4,5,6,7,8], [1,3,2,5,4,7,6,8]) = 3  c) dist([1,2,3,4,5,6,7,8], [8,7,6,5,4,3,2,1]) = 7

Intuitively, it seems like c and a should be "closer" to the left sequence than b, but this definition gives the opposite result.

At this point, the "distance" between two permutations is an ill defined concept to me, but I haven't found a metric that gives me an intuitive distance yet, so I'd love some opinions.

Edit:

For anyone who runs into this. The options people suggested below were great. The one I ended up deciding was best is the Kendall Tau Correlation (also see Kendall Tau distance). Although it doesn't generally forgive contiguous sequences which are grossly out of order, it has the fantastic property of giving negative correlations for reverse sequences and positive for forward sequences. It also gives some fairly intuitive answers overall (with the exception of not accounting for contiguity).

As an experiment, I also wanted to determine for a length 8 sequence (like what I've been using as examples), how much resolution does each measure give us? I.e., how many different distances does each option provide. So I ran all permutations of each of the discussed methods (with some minor modifications described below) and generated this histogram table. One final note of why Kendall Tau could be the overall winner is that you can actually weight the relative position exchanges, giving even more granularity in the distance result (as you'll see in the histograms).

histograms of different permutation distance methods

Kendall Tau is computed via the python, scipy.stats library (as is the Weighted Tau). Note that weighted tau with all 1 weights is the same as traditional tau. The documentation for the weighted function also suggests that, in general, a hyperbolic function for the weights can be preferable. I also show what a linear weighting looks like though (i.e. 1,2,3,4,5,6,7,8 as the weights).

Finally, Transposition Distance is the distance metric described in the original post I linked.

Cycle Rearrangement Distance is the distance metric suggested by David K, allowing for contiguous movements and counting how many moves of contiguous blocks are needed to get to a particular configuration.

L1 Distance is the sum of the absolute value of the subtraction of each element in each list. I.e. sum(|[1,2,3] - [3,2,1]|)=4.

L0 Distance (for lack of a better term) is the method described by Kanak without the extra diagonal.

As you can see from the image, even without the weighting, Kendall Tau gives far more potential distances and has far more resolution than the other methods. Although I can imagine circumstances where the others would be preferred, that is the one I will be going forward with.

Thanks for all the help!
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)