Szorzatösszeg

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\neq 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'=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'-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ő.