Search

In this work, we study the spectral property of generalized Sierpinski-type self-affine measures μ M , D on R 2 generated by an expanding integer matrix M ∈ M 2 ( Z ) with det ⁡ ( M ) ∈ 3 Z and a non-collinear integer digit set D = { ( 0 , 0 ) t , ( α 1 , α 2 ) t , ( β 1 , β 2 ) t } with α 1 β 2 − α 2 β 1 ∈ 3 Z . We give the sufficient and necessary conditions for μ M , D to be a spectral measure, i.e., there exists a countable subset Λ ⊂ R 2 such that E ( Λ ) = { e 2 π i 〈 λ , x 〉 : λ ∈ Λ } forms an orthonormal basis for L 2 ( μ M , D ) . This completely settles the spectrality of the self-affine measure μ M , D .

A novel color image encryption algorithm based on a cross 2D hyperchaotic map is proposed in this paper. The cross 2D hyperchaotic map is constructed using one nonlinear function and two chaotic maps with a cross structure. Chaotic behaviors are illustrated using bifurcation diagrams, Lyapunov exponent spectra, phase portraits, etc. In the color image encryption algorithm, the keys are generated using hash function SHA-512 and the information of the plain color image. First, the color plain image is converted to a combined bit-level matrix and permuted by the chaos-based row and column combined cycle shift scrambling method. Then, the scrambled integer matrix is diffused according to the selecting sequence which depends on the chaotic sequence. Last, decompose the diffusion matrix to get the encrypted color image. Simulation experiments and security evaluations show that the algorithm can encrypt the color image effectively and has good security to resist various kinds of attacks.

We describe a representation for periodic tilings of the plane by regular polygons. Our approach is to represent explicitly a small subset of seed vertices from which we systematically generate all elements of the tiling by translations. We represent a tiling concretely by a ( 2 + n ) × 4 integer matrix containing lattice coordinates for two translation vectors and n seed vertices. We discuss several properties of this representation and describe how to exploit the representation elegantly and efficiently for reconstruction, rendering, and automatic crystallographic classification by symmetry detection.

We construct a nonnegative integer matrix to evaluate the matrix of nonlinearity characteristics for the coordinate polynomials of a product of transformations of a binary vector space. The matrix of the characteristics of the transformation is defined by the degrees of nonlinearity of the derivatives of all coordinate functions in each input variable. The entries of the evaluation matrix are expressed in terms of the characteristics of the coordinate polynomials of the multiplied transformations. Calculation of the evaluation matrix is easier than calculating the exact values of the characteristics. The estimation method is extended to an arbitrary number of multiplied transformations. Computational examples are given that in particular show the accuracy of the obtained estimates and the domain of their nontriviality.

This short note extends a recent result (Bonifas et al, On sub-determinants and the diameter of polyhedra, Discrete Computational Geometry, 52, 2014) of an upper bound of the diameter of a convex polytope defined by an integer matrix to a similar upper bound of the diameter of a convex polytope defined by a real matrix. It also shows, by an example, that the new bound may be better than the ones of Bonifas et al., Comment: 7 pages

Generic-case approach to algorithmic problems was suggested by A. Miasnikov, I. Kapovich, P. Schupp and V. Shpilrain in 2003. This approach studies behavior of an algo-rithm on typical (almost all) inputs and ignores the rest of inputs. In this paper, we prove that the subset sum problems for the monoid of integer positive unimodular matrices of the second order, the special linear group of the second order, and the modular group are generically solvable in polynomial time.

Let $$\mu _{M, D}$$ be the self-affine measure generated by an expanding integer matrix $$M\in M_{2}(\mathbb {Z})$$ and an integer three-element digit set $$D=\{(0,0)^T, (\alpha ,\beta )^T,(\gamma ,\eta )^T\}$$ . In this paper, we show that if $$3\mid \det (M)$$ and $$3\not \mid \alpha \eta -\beta \gamma $$ , then $$L^2(\mu _{M,D})$$ has an orthogonal basis of exponential functions if and only if $$M^*\varvec{u}\in 3\mathbb {Z}^2$$ , where $$\varvec{u}=(\eta -2\beta ,\; 2\alpha -\gamma )^T$$ .

International audience; We rely on aggregate separation bounds for univariate polynomials to introduce novel worst-case separation bounds for the isolated roots of zero-dimensional, positive-dimensional, and overde- termined polynomial systems. We exploit the structure of the given system, as well as bounds on the height of the sparse (or toric) resultant, by means of mixed volume, thus establishing adaptive bounds. Our bounds improve upon Canny’s Gap theorem [9]. Moreover, they exploit sparseness and they apply without any assumptions on the input polynomial system. To evaluate the quality of the bounds, we present polynomial systems whose root separation is asymptotically not far from our bounds.We apply our bounds to three problems. First, we use them to estimate the bitsize of the eigenvalues and eigenvectors of an integer matrix; thus we provide a new proof that the problem has polynomial bit complexity. Second, we bound the value of a positive polynomial over the simplex: we improve by at least one order of magnitude upon all existing bounds. Finally, we asymptotically bound the number of steps of any purely subdivision-based algorithm that isolates all real roots of a polynomial system.

A matrix is Bohemian if its elements are taken from a finite set of integers. An upper Hessenberg matrix is normalized if all its subdiagonal elements are ones, and hollow if it has only zeros along the main diagonal. All possible determinants of families of normalized and hollow normalized Bohemian upper Hessenberg matrices are enumerated. It is shown that in the case of hollow matrices the maximal determinants are related to a generalization of Fibonacci numbers. Several conjectures recently stated by Corless and Thornton follow from these results.

As a non-linear precoding alternative to Tomlinson-Harashima precoding (THP), in this paper, so-called lattice reduction aided precoding (LRP) is considered as a crosstalk precompensation technique for downstream transmission in G.fast DSL networks. First, a practically achievable bit-rate expression for LRP is proposed in function of the precoder and integer matrix. The problem then consists of a joint precoder and integer matrix design in order to maximize the weighted sum-rate (WSR) under per-line power constraints. For a fixed integer matrix, zero-forcing (ZF) precoder matrix design simplifies to gain scaling optimization with complex gain scalars, for which a successive lower bound maximization method is presented. Additionally, it is established that the achievable ZF-LRP sum-rate is upper bounded by the achievable ZF-THP sum-rate at high SNR. For computing the optimal precoder matrix, on the other hand, an efficient method is developed by leveraging on the equivalence between the WSR maximization and the weighted sum of mean squared error (MSE) minimization, leading to a locally-optimal MMSE-LRP solution. Simulations with a measured G.fast cable binder are provided to compare the proposed LRP schemes with THP schemes.

As atomic operations, secure matrix-based computations using homomorphic encryption (HE) have attracted much attention in cloud-based machine learning. However, most existing secure matrix computation solutions that focus on HE schemes suffer efficiency loss as the size of the matrix, which greatly limits their applications in the big data environment. To address these issues, this paper proposes seIMC, an integer matrix computation scheme based on the Gentry-Sahai-Waters (GSW) scheme, to cope with privacy protection and secure computation of large-scale data. In detail, we translate the GSW scheme to encrypt an integer matrix modulo $q$ (i.e., a large positive integer), and homomorphically compute matrix addition and multiplication, which is a natural extension of HAO scheme. Besides, the correctness and security analysis of seIMC are shown, and complexity analysis is also given in this study. Furthermore, the proposed schemes are implemented, including public-key encryption and private-key encryption schemes. Compared with existing secure matrix computation schemes, the proposed scheme performs better in execution time. Finally, seIMC is applied to solve the problem of the number of ways in which any two participants make friends through $k$ steps in an encrypted social network. Experiments show that when the cloud server processes an integer matrix of 1000 people with a security level of 90, namely, 1 million data volumes, it only takes approximately 1.9 minutes for each homomorphic matrix multiplication. Hence, the practicality of the proposed seIMC in privacy protection under a big data environment is highly proven.

The self-affine measure $$\mu _{M,D}$$ corresponding to an expanding integer matrix $$M= diag[p_{1},p_{2},p_{3}]$$ and the digit set $$D=\left\{ 0, e_{1}, e_{2}, e_{3} \right\} $$ in the space $$\mathbb {R}^{3}$$ is supported on the spatial Sierpinski gasket, where $$e_{1},e_{2}, e_{3}$$ are the standard basis of unit column vectors in $$\mathbb {R}^{3}$$ and $$p_{1}, p_{2}, p_{3}\in \mathbb {Z}{\setminus } \{0, \pm 1\}$$. In the case $$p_{1}\in 2\mathbb {Z}$$ and $$p_{2}, p_{3}\in 2\mathbb {Z}+1$$, it is conjectured that all the four-element orthogonal exponentials in the Hilbert space $$L^{2}(\mu _{M,D})$$ are maximal in the class of exponential functions. This conjecture has been proved to be false by giving a class of the five-element (and later, the eight-element) orthogonal exponentials in $$L^{2}(\mu _{M,D})$$. In the present paper, we completely determine the maximal cardinality of $$\mu _{M,D}$$-orthogonal exponentials on the spatial Sierpinski gasket. The main result shows that (i) if $$p_{3}\ne \pm p_{2}$$, then for any $$l\in \mathbb {N}$$, there exist $$(2l+6)$$-element orthogonal exponentials in the Hilbert space $$L^{2}(\mu _{M,D})$$, which is also maximal in the class of exponential functions; (ii) if $$p_{3} = -p_{2}$$, then there exist at most eight mutually orthogonal exponential functions in $$L^{2}(\mu _{M,D})$$, where the number eight is the best upper bound.

Let M M be a 3 × 3 3\times 3 integer matrix each of whose eigenvalues is greater than 1 1 in modulus and let D ⊂ Z 3 \mathcal {D}\subset \mathbb {Z}^3 be a set with | D | = | det M | |\mathcal {D}|=|\det M| , called a digit set. The set equation M T = T + D MT = T+\mathcal {D} uniquely defines a nonempty compact set T ⊂ R 3 T\subset \mathbb {R}^3 . If T T has positive Lebesgue measure it is called a 3 3 -dimensional self-affine tile. In the present paper we study topological properties of 3 3 -dimensional self-affine tiles with collinear digit set, i.e., with a digit set of the form D = { 0 , v , 2 v , … , ( | det M | − 1 ) v } \mathcal {D}=\{0,v,2v,\ldots , (|\det M|-1)v\} for some v ∈ Z 3 ∖ { 0 } v\in \mathbb {Z}^3\setminus \{0\} . We prove that the boundary of such a tile T T is homeomorphic to a 2 2 -sphere whenever its set of neighbors in a lattice tiling which is induced by T T in a natural way contains 14 14 elements. The combinatorics of this lattice tiling is then the same as the one of the bitruncated cubic honeycomb, a body-centered cubic lattice tiling by truncated octahedra. We give a characterization of 3 3 -dimensional self-affine tiles with collinear digit set having 14 14 neighbors in terms of the coefficients of the characteristic polynomial of M M . In our proofs we use results of R. H. Bing on the topological characterization of spheres.

Trellises provide a graphical representation for the row space of a matrix. The product construction of Kschischang and Sorokine builds minimal conventional trellises from matrices in minimal span form. Koetter and Vardy showed that minimal tail-biting trellises can be obtained by applying the product construction to submatrices of a characteristic matrix. We introduce the unique reduced minimal span form of a matrix and we obtain an expression for the unique reduced characteristic matrix. Among new properties of characteristic matrices we prove that characteristic matrices are in duality if and only if they have orthogonal column spaces, and that the transpose of a characteristic matrix is again a characteristic matrix if and only if the characteristic matrix is reduced. These properties have clear interpretations for the unwrapped unit memory convolutional code of a tail-biting trellis, they explain the duality for the class of Koetter and Vardy trellises, and they give a natural relation between the characteristic matrix based Koetter–Vardy construction and the displacement matrix based Nori–Shankar construction. For a pair of reduced characteristic matrices in duality, one is lexicographically first in a forward direction and the other is lexicographically first in the reverse direction. This confirms a conjecture by Koetter and Vardy after taking into account the different directions for the lexicographical ordering.

Let $A$ be a $d$ by $n$ integer matrix. Gel'fand et al. proved that most $A$-hypergeometric systems have an interpretation as a Fourier--Laplace transform of a direct image. The set of parameters for which this happens was later identified by Schulze and Walther as the set of not strongly resonant parameters of $A$. A similar statement relating $A$-hypergeometric systems to exceptional direct images was proved by Reichelt. In this article, we consider a hybrid approach involving neighborhoods $U$ of the torus of $A$ and consider compositions of direct and exceptional direct images. Our main results characterize for which parameters the associated $A$-hypergeometric system is the inverse Fourier-Laplace transform of such a "mixed Gauss-Manin" system. In order to describe which $U$ work for such a parameter, we introduce the notions of fiber support and cofiber support of a D-module. If the semigroup ring of $A$ is normal, we show that every $A$-hypergeometric system is "mixed Gauss--Manin". We also give an explicit description of the neighborhoods $U$ which work for each parameter in terms of primitive integral support functions., Comment: We added conditions to parts (c) and (d) of the first lemma in the Normal Case section and added an example to show the necessity of these conditions. These parts were not used elsewhere in the paper, so all results still hold. We also added some remarks and fixed some typos

This letter considers simultaneous wireless information and power transfer (SWIPT) in multiple-input single-output broadcasting systems based on the integer forcing (IF) technique where multiple receivers are equipped with a power splitting circuit and able to harvest energy and decode information at the same time. The optimization problem that incorporates the beamforming matrix and IF coefficients matrix designs is formulated to minimize the transmit power at transmitter, while guaranteeing the achievable rate and harvested energy threshold of each receiver. To tackle the NP-hardness and non-convexity of the optimization problem, we propose an iterative algorithm consisting of two sub-problems. Simulation results provide the comparison of the performance of SWIPT systems with and without IF technique.

In this paper, we prove that each matrix in $$M_{m\times n}({\mathbb {Z}}_{\ge 0})$$ is uniformly column sign-coherent (Definition 2.2 (ii)) with respect to any $$n\times n$$ skew-symmetrizable integer matrix (Corollary 3.3 (ii)). Using such matrices, we introduce the definition of irreducible skew-symmetrizable matrix (Definition 4.1). Based on this, the existence of maximal green sequences for skew-symmetrizable matrices is reduced to the existence of maximal green sequences for irreducible skew-symmetrizable matrices.

Eigenvalues of graph-theoretical matrices often reflect structure properties of networks (graphs) meaningfully. In this paper, we explore inequalities for graph distance measures which are based on topological indices. Some of these indices are based on eigenvalues of graph-theoretical matrices. We here consider the adjacency matrix, the Laplacian matrix and signless Laplacian matrix. Besides proving the inequalities, we discuss the usefulness of these measures and state some conjectures.

The problem of general synthesis of optimal control system of mobile robot is considered. In the problem it is necessary to find a feedback control function such that a mobile robot can achieve the set terminal position from any point of area of initial conditions. The solution of this problem is a mathematical expression of control function. For solution of this problem Cartesian genetic programming (CGP) is used. CGP is one of symbolic regression methods. The methods of symbolic regression allow numerical with the help of computer to find analytical form of mathematical expression. CGP codes multi-dimension function in a form of integer matrix on the base of the sets of arguments and elementary functions. Every string of this matrix is a code of one call of a function. For search of optimal solution, a variation genetic algorithm is used that realizes the principle of small variation of basic solution. The algorithm searches for a mathematical expression of the feedback control function in the form of code and at the same time value of parametric vector that is one of arguments of this function. An example of numerical solution of the control system synthesis problem for mobile robot is presented. It is introduced a conception a space of machine made functions. In this space functions can’t have value is infinity, and all function can be presented in the form of Taylor’s series only with a finite number of members.

We present a Las Vegas randomized algorithm to compute the Smith normal form of a nonsingular integer matrix. For an A ∈ Zn×n, the algorithm requires O(n3(log n + log ||A||)2 (log n)2) bit operations using standard integer and matrix arithmetic, where ||A|| = maxij |Aij | denotes the largest entry in absolute value. Fast integer and matrix multiplication can also be used, establishing that the Smith form can be computed in about the same number of bit operations as required to multiply two matrices of the same dimension and size of entries as the input matrix.

We say that the system of equations $Ax = b$, where $A$ is an integer matrix and $b$ is a (non-zero) integer vector, is partition regular if whenever the integers are finitely coloured there is a monochromatic vector $x$ with $Ax = b.$ Rado proved that the system $Ax = b$ is partition regular if and only if it has a constant solution. Byszewski and Krawczyk asked if this remains true when the integers are replaced by a general (commutative) ring $R$. Our aim in this note is to answer this question in the affirmative. The main ingredient is a new 'direct' proof of Rado’s result.

The discrete cosine transform (DCT) is used widely in the area of image compression. Recently, the Discrete Tchebichef Transform (DTT) is reported to be superior to DCT in terms of coding performance. In this paper, DTT is presented first. Then a scheme of deriving the integer approximate DTT is introduced. The integer approximate DTT is used to compress a gray-scale image. Since the resulting integer approximate DTT matrix is not normal, we need to multiply a diagonal matrix to its left. When we use the integer matrix to perform the transform, the diagonal matrix have to be merged into the quantization process. We derive the equivalent quantization matrix and the inverse quantization matrix. Compared with JPEG and exact DTT, the integer approximated DTT shows a bit lower reconstructed image quality but with extreme low complexity.

The robust Chinese remainder theorem (CRT) has been recently proposed for robustly reconstructing a large nonnegative integer from erroneous remainders. It has found many applications in signal processing, including phase unwrapping, and frequency estimation under sub-Nyquist sampling. Motivated by the applications in multidimensional (MD) signal processing, in this article we propose the MD-CRT and robust MD-CRT for integer vectors. Specifically, by rephrasing the abstract CRT for rings in number-theoretic terms, we first derive the MD-CRT for integer vectors with respect to a general set of integer matrix moduli, which provides an algorithm to uniquely reconstruct an integer vector from its remainders, if it is in the fundamental parallelepiped of the lattice generated by a least common right multiple of all the moduli. For some special forms of moduli, we present explicit reconstruction formulae. Moreover, we derive the robust MD-CRT for integer vectors when the remaining integer matrices of all the moduli left divided by their greatest common left divisor (gcld) are pairwise commutative, and coprime. Two different reconstruction algorithms are proposed, and accordingly, two different conditions on the remainder error bound for the reconstruction robustness are obtained, which are related to a quarter of the minimum distance of the lattice generated by the gcld of all the moduli or the Smith normal form of the gcld.

We propose a new encoding algorithm for the simultaneous differential multidimensional scalar point multiplication algorithm d-MUL. Previous encoding algorithms are known to have major drawbacks in their efficient and secure implementation. Some of these drawbacks have been avoided in a recent paper in 2018 at a cost of losing the general functionality of the point multiplication algorithm. In this paper, we address these issues. Our new encoding algorithm takes the binary representations of scalars as input, and constructs a compact binary sequence and a permutation, which explicitly determines a regular sequence of group operations to be performed in d-MUL. Our algorithm simply slides windows of size two over the scalars and it is very efficient. As a result, while preserving the full generality of d-MUL, we successfully eliminate the recursive integer matrix computations in the originally proposed encoding algorithms. We also expect that our new encoding algorithm will make it easier to implement d-MUL in constant time. Our results can be seen as the efficient and full generalization of the one dimensional Montgomery ladder to arbitrary dimension., 12th International Conference on Cryptology in Africa, July 20 – 22, 2020, Cairo, Egypt, Series: Lecture Notes in Computer Science

Let 1 ≤ 2l ≤ m < d. A vector x ∈ ℤd is said to be l-sparse if it has at most l nonzero coordinates. Let an m × d matrix A be given. The problem of the recovery of an l-sparse vector x ∈ Zd from the vector y = Ax ∈ Rm is considered. In the case m = 2l, we obtain necessary conditions and sufficient conditions on the numbers m, d, and k ensuring the existence of an integer matrix A all of whose elements do not exceed k in absolute value which makes it possible to reconstruct l-sparse vectors in ℤd. For a fixed m, these conditions on d differ only by a logarithmic factor depending on k.

To any toric ideal I A , encoded by an integer matrix A, we associate a matroid structure called the bouquet graph of A and introduce another toric ideal called the bouquet ideal of A. We show how these objects capture the essential combinatorial and algebraic information about I A . Passing from the toric ideal to its bouquet ideal via the graph theoretic properties of the bouquet graph allows us to classify several cases. For example, on the one end of the spectrum, there are ideals that we call stable, for which bouquets capture the complexity of various generating sets as well as the minimal free resolution. On the other end of the spectrum lie toric ideals whose various bases (e.g., minimal generating sets, Grobner, Graver bases) coincide. Apart from allowing for classification-type results, bouquets provide a new way to construct families of examples of toric ideals with various interesting properties, such as robustness, genericity, and unimodularity. The new bouquet framework can be used to provide a characterization of toric ideals whose Graver basis, the universal Grobner basis, any reduced Grobner basis and any minimal generating set coincide.

We propose a new technique for the mitigation of fail-stop failures and/or silent data corruptions (SDCs) within linear, sesquilinear or bijective (LSB) operations on $M$ integer data streams ( $M\geq 3$ ). In the proposed approach, the $M$ input streams are linearly superimposed to form $M$ numerically entangled integer data streams that are stored in-place of the original inputs, i.e., no additional (aka. “checksum”) streams are used. An arbitrary number of LSB operations can then be performed in $M$ processing cores using these entangled data streams. The output results can be extracted from any $M-K$ entangled output streams by additions and arithmetic shifts, thereby mitigating $K$ fail-stop failures ( $K\leq \left\lfloor \frac{M-1}{2}\right\rfloor$ ), or detecting up to $K$ SDCs per $M$ -tuple of outputs at corresponding in-stream locations. Therefore, unlike other methods, the number of operations required for the entanglement, extraction and recovery of the results is linearly related to the number of the inputs and does not depend on the complexity of the performed LSB operations. Our proposal is validated within an Amazon EC2 instance (Haswell architecture with AVX2 support) via integer matrix product operations. Our analysis and experiments for fail-stop failure mitigation and SDC detection reveal that the proposed approach incurs 0.75 to 37.23 percent reduction in processing throughput in comparison to the equivalent error-intolerant processing. This overhead is found to be up to two orders of magnitude smaller than that of the equivalent checksum-based method, with increased gains offered as the complexity of the performed LSB operations is increasing. Therefore, our proposal can be used in distributed systems, unreliable multicore clusters and safety-critical applications, where robustness against failures and SDCs is a necessity.

Motivation Cancer is characterized by intra-tumor heterogeneity, the presence of distinct cell populations with distinct complements of somatic mutations, which include single-nucleotide variants (SNVs) and copy-number aberrations (CNAs). Single-cell sequencing technology enables one to study these cell populations at single-cell resolution. Phylogeny estimation algorithms that employ appropriate evolutionary models are key to understanding the evolutionary mechanisms behind intra-tumor heterogeneity. Results We introduce Single-cell Phylogeny Reconstruction (SPhyR), a method for tumor phylogeny estimation from single-cell sequencing data. In light of frequent loss of SNVs due to CNAs in cancer, SPhyR employs the k-Dollo evolutionary model, where a mutation can only be gained once but lost k times. Underlying SPhyR is a novel combinatorial characterization of solutions as constrained integer matrix completions, based on a connection to the cladistic multi-state perfect phylogeny problem. SPhyR outperforms existing methods on simulated data and on a metastatic colorectal cancer. Availability and implementation SPhyR is available on https://github.com/elkebir-group/SPhyR. Supplementary information Supplementary data are available at Bioinformatics online.

We generalize the $K$ matrix formulation to non-trivial non-Abelian families of 2+1D topological orders. Given a topological order $\mathcal C$, any topological order in the same non-Abelian family as $\mathcal C$ can be efficiently described by $\boldsymbol{a}=(a_I)$ where $a_I$ are Abelian anyons in $\mathcal C$, together with a symmetric invertible matrix $K$, $K_{IJ}=k_{IJ}-t_{a_I,a_J}$ where $k_{IJ}$ are integers, $k_{II}$ are even and $t_{a_I,a_J}$ are the mutual statistics between $a_I,a_J$. In particular, when $\mathcal C$ is a root whose rank is the smallest in the family, $K$ becomes an integer matrix. Our results make it possible to generate the data of large numbers of topological orders instantly., Comment: 6 pages

We consider new polynomially solvable cases of the well-known Quadratic Assignment Problem involving coefficient matrices with a special diagonal structure. By combining the new special cases with polynomially solvable special cases known in the literature we obtain a new and larger class of polynomially solvable special cases of the QAP where one of the two coefficient matrices involved is a Robinson matrix with an additional structural property: this matrix can be represented as a conic combination of cut matrices in a certain normal form. The other matrix is a conic combination of a monotone anti-Monge matrix and a down-benevolent Toeplitz matrix. We consider the recognition problem for the special class of Robinson matrices mentioned above and show that it can be solved in polynomial time.

It is proved that regularity of an interval matrix implies singularity of four related interval matrices. The result is used to prove that for each nonsingular point matrix A, either A or A − 1 can be brought to a singular matrix by perturbing only the diagonal entries by an amount of at most 1 each. As a consequence, the notion of a diagonally singularizable matrix is introduced.

In this paper, we investigate the transceiver design for multiple-input multiple-output visible light communication (VLC) systems that employ the integer-forcing (IF) lattice decoding technique. To facilitate the joint design of the transmitter precoder, the integer matrix and the receiver equalizer, we first give a necessary and sufficient condition for the integer matrix to be invertible over 1-D lattice. Based on this condition, we then propose a new method for choosing the integer matrix which achieves better performance than the existing lattice reduction method. Moreover, taking into account two typical constraints in VLC, we optimize transmit and receive matrices using the conditional gradient method or the projected gradient method. Finally, the integer matrix and the transmit and receive matrices are jointly optimized in an iterative manner. Simulation results are provided to demonstrate the performance improvement achieved by the proposed framework.

We introduce the notion of dual matrices of an infinite matrix A, which are defined by the dual sequences of the rows of A and naturally connected to the Pascal matrix P = [ ( i j ) ] ( i , j = 0 , 1 , 2 , … ) . We present the Cholesky decomposition of the symmetric Pascal matrix by means of its dual matrix. Decompositions of a Vandermonde matrix are used to obtain variants of the Lagrange interpolation polynomial of degree ≤n that passes through the n + 1 points ( i , q i ) for i = 0 , 1 , … , n .

The work considers an equivalence relation in the set of all n × m binary matrices. In each element of the factor-set generated by this relation, we define the concept of canonical binary matrix, namely the minimal element with respect to the lexicographic order. For this purpose, the binary matrices are uniquely represented by ordered n-tuples of integers. We have found a necessary and sufficient condition for an arbitrary matrix to be canonical. This condition could be the base for realizing recursive algorithm for finding all n × m canonical binary matrices and consequently for finding all bipartite graphs, up to isomorphism with cardinality of each part equal to n and m.

The problem of integer balancing of a four-dimensional matrix is studied. The elements of the inner part (all four indices are greater than zero) of the given real matrix are summed in each direction and each two- and three-dimensional section of the matrix; the total sum is also found. These sums are placed into the elements where one or more indices are equal to zero (according to the summing directions). The problem is to find an integer matrix of the same structure, which can be produced from the initial one by replacing the elements with the largest previous or the smallest following integer. At the same time, the element with four zero indices should be produced with standard rules of rounding-off. In the article the problem of finding the maximum multiple flow in the network of any natural multiplicity k is also studied. There are arcs of three types: ordinary arcs, multiple arcs and multi-arcs. Each multiple and multi-arc is a union of k linked arcs, which are adjusted with each other. The network constructing rules are described. The definitions of a divisible network and some associated subjects are stated. There are defined the basic principles for reducing the integer balancing problem of an l-dimensional matrix (l ≥ 3) to the problem of finding the maximum flow in a divisible multiple network of multiplicity k. There are stated the rules for reducing the four-dimensional balancing problem to the maximum flow problem in the network of multiplicity 5. The algorithm of finding the maximum flow, which meets the solvability conditions for the integer balancing problem, is formulated for such a network.

The generic matrix multiply (GEMM) routine comprises the compute and memory-intensive parts of many information retrieval, machine learning, and object recognition systems that process integer inputs. Therefore, it is of paramount importance to ensure that integer GEMM computations remain robust to silent data corruptions (SDCs), which stem from accidental voltage or frequency overscaling, or other hardware nonidealities. In this paper, we introduce a new method for SDC mitigation based on the concept of numerical packing. The key difference between our approach and all existing methods is the production of redundant results within the numerical representation of the outputs, rather than as a separate set of checksums. Importantly, unlike well-known algorithm-based fault tolerance approaches for GEMM, the proposed approach can reliably detect the locations of the vast majority of all possible SDCs in the results of GEMM computations. An experimental investigation of voltage-scaled integer GEMM computations for visual descriptor matching within state-of-the-art image and video retrieval algorithms running on an Intel i7-4578U 3 GHz processor shows that SDC mitigation based on numerical packing leads to comparable or lower execution and energy-consumption overhead in comparison with all other alternatives.

We consider the problem of determining whether two polynomial matrices can be transformed to one another by left multiplying with some nonsingular numerical matrix and right multiplying by some invertible polynomial matrix. Thus the equivalence relation arises. This equivalence relation is known as semiscalar equivalence. Large difficulties in this problem arise already for 2-by-2 matrices. In this paper the semiscalar equivalence of polynomial matrices of second order is investigated. In particular, necessary and sufficient conditions are found for two matrices of second order being semiscalarly equivalent. The main result is stated in terms of determinants of Toeplitz matrices.

Fillmore Theorem says that if A is a nonscalar matrix of order n over a field F and γ 1 , … , γ n ∈ F are such that γ 1 + ⋯ + γ n = tr A , then there is a matrix B similar to A with diagonal ( γ 1 , … , γ n ) . Fillmore's proof works by induction on the size of A and implicitly provides an algorithm to construct B . We develop an explicit and extremely simple algorithm that finish in two steps (two similarities), and with its help we extend Fillmore Theorem to integers (if A is integer then we can require B to be integer).

In this paper, we first investigate the matrix equation in a new fashion, where A, B, C, D and G are arbitrary matrices. Then, we establish some necessary and sufficient conditions for the existence of a solution of , where A, B are arbitrary matrices and C is a Hermitian matrix. In the special case when , we determine the general solution of , where A is an arbitrary matrix and C is a Hermitian matrix.

Integer datasets frequently appear in many applications in science and engineering. To analyze these datasets, we consider an integer matrix approximation technique that can preserve the original dataset characteristics. Because integers are discrete in nature, to the best of our knowledge, no previously proposed technique developed for real numbers can be successfully applied. In this study, we first conduct a thorough review of current algorithms that can solve integer least squares problems, and then we develop an alternative least square method based on an integer least squares estimation to obtain the integer approximation of the integer matrices. We discuss numerical applications for the approximation of randomly generated integer matrices as well as studies of association rule mining, cluster analysis, and pattern extraction. Our computed results suggest that our proposed method can calculate a more accurate solution for discrete datasets than other existing methods.

Matrices associated to oriented hypergraphs produce a connection between signed graphs and Hadamard matrices. The existence of a family of signed graphs that are switching equivalent to − K n and whose adjacency matrices sum to the zero matrix is shown to be equivalent to the existence of a Hadamard matrix. This equivalent problem is used to make explicit signed graph constructions which specialize to known Hadamard constructions.

We show how to compute the permanent of an n × n integer matrix modulo p k in time n k + O ( 1 ) if p = 2 and in time 2 n / exp ⁡ { Ω ( γ 2 n / p log ⁡ p ) } if p is an odd prime with k p n , where γ = 1 − k p / n . Our algorithms are based on Ryser's formula, a randomized algorithm of Bax and Franklin, and exponential-space tabulation. Using the Chinese remainder theorem, we conclude that for each δ > 0 we can compute the permanent of an n × n integer matrix in time 2 n / exp ⁡ { Ω ( δ 2 n / β 1 / ( 1 − δ ) log ⁡ β ) } , provided there exists a real number β such that | per A | ≤ β n and β ≤ ( 1 44 δ n ) 1 − δ .

We consider matrices over the (nonnegative) integers and the integers mod k, and representations of them as linear combinations of permutation matrices. In both instances we describe and compare se...

To generalize D-nilpotent matrices that play a role in study of Druzkowski maps, we introduce quasi-D-nilpotent matrices. A matrix A is called quasi-D-nilpotent if there exists a subspace V of diagonal matrices of codimension 1 such that DA is nilpotent for all . It is proved that a quasi-D-nilpotent matrix has few nonzero principal minors. We also determine irreducible quasi-D-nilpotent matrices and the Frobenius normal forms of quasi-D-nilpotent matrices with respect to permutation similarity.

As the matrix can compactly represent numeric data, simplify problem formulation and reduce time complexity, it has many applications in most of the scientific fields. For this purpose, some types of generalized rough sets have been connected with matrices. However, covering-based rough sets which play an important role in data mining and machine learning are seldom connected with matrices. In this paper, we define three composition operations of coverings and study their characteristic matrices; Moreover, the relationships between the characteristic matrices and covering approximation operators are investigated. First, for a covering, an existing matrix representation of indiscernible neighborhoods called the type-1 characteristic matrix of the covering is recalled and a new matrix representation of neighborhoods called the type-2 characteristic matrix of the covering is proposed. Second, considering the importance of knowledge fusion and decomposition, we define three types of composition operations of coverings. Specifically, their type-1 and type-2 characteristic matrices are studied. Finally, we also explore the representable properties of covering approximation operators with respect to any covering generated by each composition operation. It is interesting to find that three types of approximation operators, which are induced by each type of composition operation of coverings, can be expressed as the Boolean product of a coefficient matrix and a characteristic vector. These interesting results suggest the potential for studying covering-based rough sets by matrix approaches.

A doubly quasi-stochastic (DQS) matrix is said to be maximally (minimally) scaled if it cannot be diagonally scaled to another doubly quasi-stochastic matrix with larger (smaller) permanent. Motivated by a connection to the geometric measure of entanglement of certain symmetric states, we offer a series of results on the structures of the sets of n × n maximally scaled ( M a x S c n ) and minimally scaled ( M i n S c n ) DQS matrices. In particular, we offer a characterization of the set of n × n maximally scaled matrices, and use this characterization to show that these matrices form a convex set and that the n × n identity matrix is the element of M a x S c n with smallest permanent. We then show that real DQS matrices in M a x S c n or M i n S c n must satisfy certain spectral properties, and use these properties to show that all positive definite doubly stochastic matrices are minimally scaled. We finish with a bound on the permanent of any real matrix or Abelian group matrix in M i n S c n .

In this article, we present a sufficient condition for the existence of a unique positive definite solution of the non-linear matrix equation , where , (the set of all Hermitian positive definite matrices), are non-singular matrices and are order-preserving mappings. We give an example of a non-linear matrix equation of the above form (, A is a non-singular matrix, F is an order-preserving mapping), which is not solvable by previously known methods but solvable by using our new results.

Let A = PQT, where P and Q are two n × 2 complex matrices of full column rank such that QTP is singular. We solve the quadratic matrix equation AXA = XAX. Together with a previous paper devoted to the case that QTP is nonsingular, we have completely solved the matrix equation with any given matrix A of rank-two.

Let A = P Q T , where P and Q are two n × 2 complex matrices of full column rank such that det Q T P ≠ 0 and so 0 is a semisimple eigenvalue of A with multiplicity n − 2 . We solve the quadratic matrix equation A X A = X A X completely.