Szorzatösszeg

Sablon:Nincs forrás Szorzatösszegnek nevezzük egy gyűrű elemeiből képzett $a_1,\dots ,a_n$ és $b_1,\dots ,b_n(n\in \mathbb{N})$ véges sorozatok megfelelő tagjai szorzatának összegét, azaz a sorozatok tagjaiból képzett

$\sum _{i=1}^n{a}_i{b}_i=a_1{b}_1+\cdots +a_n{b}_n$

kifejezést.

Szorzatösszegek tulajdonságai

Rögzített $a_1,\dots ,a_n$ és $b_1,\dots ,b_n$ sorozatok permutációiból képezhető szorzatösszegek közül rendezett gyűrűben azoknak az értéke a legnagyobb, amelyeknek esetében a két sorozat permutációi egyformán rendezettek, és azoknak az értéke a legkisebb, amelyeknek esetében a két sorozat permutációi ellentétesen rendezettek.

Bizonyítás:

Tekintsük a $S=\sum _{i=1}^n{a}_i{b}_i=a_1{b}_1+\cdots +a_n{b}_n$ szorzatösszeget, és tegyük fel, hogy az $a_1,\dots ,a_n$ és $b_1,\dots ,b_n$ sorozatok nem egyformán rendezettek, azaz van olyan $i\ne j$ indexpár, amelyre $a_i<a_j$, de $b_i>b_j$. Képezzük ekkor a $b_1,\dots ,b_n$ sorozatnak azt a permutációját, amelyben $b_i$ és $b_j$ helyet cserél, és vizsgáljuk az ebből alkotott $S^{\prime }=a_1{b}_1+\cdots +a_i{b}_j+\cdots +a_j{b}_i+\cdots +a_n{b}_n$ szorzatösszeg és az eredeti szorzatösszeg különbségét:

$S^{\prime }-S=a_i{b}_j-a_i{b}_i+a_j{b}_i-a_j{b}_j=(a_j-a_i)(b_i-b_j)>0$

tehát ha a szorzatösszeg nem egyformán rendezett permutációkból készült, akkor mindig található nagyobb értékű szorzatösszeget előállító permutációpár.

Hasonló módon indokolható, hogy a legkisebb értékű szorzatösszeg éppen az ellentétesen rendezett permutációkból készíthető.