On the complexity of detecting positive eigenvectors of nonlinear cone maps

Lemmens, Bas; White, Lewis

doi:10.2140/involve.2019.12.141

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

On the complexity of detecting positive eigenvectors of nonlinear cone maps

Bas Lemmens and Lewis White

Vol. 12 (2019), No. 1, 141–150

DOI: 10.2140/involve.2019.12.141

Abstract

In recent work with Lins and Nussbaum, the first author gave an algorithm that can detect the existence of a positive eigenvector for order-preserving homogeneous maps on the standard positive cone. The main goal of this paper is to determine the minimum number of iterations this algorithm requires. It is known that this number is equal to the illumination number of the unit ball $B_{v}$ of the variation norm, $∥ x ∥_{v} : = max_{i} x_{i} - min_{i} x_{i}$ on $V_{0} : = {x \in ℝ^{n} : x_{n} = 0}$ . In this paper we show that the illumination number of $B_{v}$ is equal to $(\binom{n}{⌈ n ∕ 2 ⌉})$ , and hence provide a sharp lower bound for the running time of the algorithm.

Keywords

nonlinear maps on cones, positive eigenvectors, illumination problem, Hilbert's metric

Mathematical Subject Classification 2010

Primary: 47H07, 47H09

Secondary: 37C25

Milestones

Received: 29 August 2017

Revised: 21 November 2017

Accepted: 14 December 2017

Published: 31 May 2018

Communicated by Kenneth S. Berenhaut

Authors

Bas Lemmens
School of Mathematics, Statistics & Actuarial Science University of Kent Canterbury United Kingdom

Lewis White
School of Mathematics, Statistics & Actuarial Science University of Kent Canterbury United Kingdom

Vol. 12, No. 1, 2019