SeedRandom[1];
nmax=4;

The original problem

matrix=Table[If[Abs[n-m]<2,n,0](*((nmax+1-n)*(nmax+1-m)*RandomReal[])/(n+m)*), {n,1,nmax},{m,1,nmax}];
matrix=(matrix+Transpose[matrix])/2;
matrix=matrix.matrix/Max[Flatten[matrix]];
matrix=DiagonalMatrix[Table[n,{n,1,nmax}]]+Table[0.1RandomReal[], {n,1,nmax},{m,1,nmax}];
matrix=matrix/Max[Flatten[matrix]];
MatrixForm[matrix]//N
eigenvals=Eigenvalues[matrix]//N
eigenvecs=Eigenvectors[matrix];

maxeigval=Take[eigenvals,(maxpos=Position[eigenvals,Max[eigenvals]][[1]])][[1]]
maxeigvec=Take[eigenvecs,maxpos][[1]]
eigenvals=Sort[eigenvals];

Finding the largest eigenvalue

maxrepeat=100;
allvals={};
vector=Table[RandomReal[],{n,1,nmax}];
vector=vector/Abs[vector.vector];
Do[
vector=matrix.vector;
eigvalguess=Power[Sqrt[vector.vector],1/irepeat];
Print[val={irepeat,maxeigval,eigvalguess,eigvalguess-maxeigval}];
AppendTo[allvals,val],
{irepeat,1,maxrepeat}
]
Show[
Plot[eigenvals,{ind,1,maxrepeat}],
ListPlot[Transpose[allvals][[3]]]
]

Not finding all eigenvalues

maxrepeat=50;
allvals={};
vectormat=Orthogonalize[Table[RandomReal[],{n,1,nmax},{m,1,nmax}]];
(*vector=vector/Abs[vector.vector];*)
Do[
vectormat=matrix.vectormat;
Do[
eigvalguess=Power[Sqrt[vectormat[[ivec]].vectormat[[ivec]]],1/irepeat];
Print[val={irepeat,ivec,maxeigval,eigenvals[[ivec]],eigvalguess,eigvalguess-eigenvals[[ivec]]}];
AppendTo[allvals,val],
{ivec,1,nmax}
],
{irepeat,1,maxrepeat}
]
Show[
Plot[eigenvals,{ind,1,maxrepeat*nmax}],
ListPlot[Transpose[allvals][[5]]]
]

Not finding all eigenvalues for another reason

maxrepeat=50;
allvals={};
vectormat=Orthogonalize[Table[RandomReal[],{n,1,nmax},{m,1,nmax}]];
(*vector=vector/Abs[vector.vector];*)
Do[
vectormat=matrix.vectormat;

Do[
vectormat[[ivec]]=vectormat[[ivec]]-
Sum[vectormat[[jvec]].vectormat[[ivec]]*vectormat[[jvec]]/(vectormat[[jvec]].vectormat[[jvec]]),{jvec,ivec-1,1,-1}],
{ivec,1,nmax}
];

Do[
eigvalguess=Power[Sqrt[vectormat[[ivec]].vectormat[[ivec]]],1/irepeat];
val={irepeat,ivec,maxeigval,eigenvals[[ivec]],eigvalguess,eigvalguess-eigenvals[[ivec]]};
(*Print[val];*)
AppendTo[allvals,val],
{ivec,1,nmax}
],
{irepeat,1,maxrepeat}
]
Print[Show[
Plot[eigenvals,{ind,1,maxrepeat*nmax}],
ListPlot[Transpose[allvals][[5]]]
]];
vectormat.vectormat

Finding all eigenvalues

maxrepeat=50;
allvals={};
vectormat=Orthogonalize[Table[RandomReal[],{n,1,nmax},{m,1,nmax}]];
magvec=Table[1.,{n,1,nmax}];
(*vector=vector/Abs[vector.vector];*)
Do[
vectormat=matrix.vectormat;

Do[
vectormat[[ivec]]=vectormat[[ivec]]-
Sum[vectormat[[jvec]].vectormat[[ivec]]*vectormat[[jvec]]/(vectormat[[jvec]].vectormat[[jvec]]),{jvec,ivec-1,1,-1}];
magvec[[ivec]]=magvec[[ivec]]*(norm=Sqrt[vectormat[[ivec]].vectormat[[ivec]]]);
vectormat[[ivec]]=vectormat[[ivec]]/norm,
{ivec,1,nmax}
];

Do[
eigvalguess=Power[magvec[[ivec]],1/irepeat];
val={irepeat,ivec,maxeigval,eigenvals[[ivec]],eigvalguess,eigvalguess-eigenvals[[ivec]]};
(*Print[val];*)
AppendTo[allvals,val],
{ivec,1,nmax}
],
{irepeat,1,maxrepeat}
]
Print[Show[
Plot[eigenvals,{ind,1,maxrepeat*nmax}],
ListPlot[Transpose[allvals][[5]]]
]];
vectormat.vectormat

Take[allvals,-4]

magvec
Log[magvec]